4c题目的小积累

ACM

记录一些忽视的小细节

最短路维护多个属性的问题

题目

L2-001. 紧急救援

AC代码

注意最短路径的条数的维护，一开始我想错了.way[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2+10;
const int INF = 1e9+10;
vector<int> G[maxn];
int n, m, s, t;
int pre[maxn];
int weight[maxn];
int way[maxn];
int dis[maxn];
bool vis[maxn];
int w[maxn][maxn];
int max_weight[maxn];
void dfs(int s){
    for(int i=0; i<maxn; i++) dis[i] = INF;
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<n; i++) max_weight[i] = 0;
    dis[s] = 0;
    max_weight[s] = weight[s];
    way[s] = 1;
    for(int i=0; i<n; i++){
        int min_dis = INF;
        int u = -1;
        for(int j=0; j<n; j++){
            if(!vis[j]&&dis[j]<min_dis){
                u = j;
                min_dis = dis[j];
            }
        }
        vis[u] = true;
        if(u == -1) return;
        for(int j=0; j<G[u].size(); j++){
            int v = G[u][j];
            if(!vis[v]){
                if(dis[v]>dis[u]+w[u][v]){
                    dis[v] = dis[u]+w[u][v];
                    way[v] = way[u];//这里需要注意一下
                    pre[v] = u;
                    max_weight[v] = max_weight[u]+weight[v];
                }
                else if(dis[v] == dis[u]+w[u][v]){
                    way[v] += way[u];//这里更新的时候需要注意一下
                    if(max_weight[v]<max_weight[u]+weight[v]){
                        pre[v] = u;
                        max_weight[v] = max_weight[u]+weight[v];
                    }
                }
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d%d%d", &n, &m, &s, &t)){
        for(int i=0; i<n; i++) G[i].clear();
        memset(way, 0, sizeof(way));
        for(int i=0; i<n; i++) pre[i] = i;
        for(int i=0; i<n; i++){
            scanf("%d", &weight[i]);
        }
        int u, v, wei;
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &wei);
            G[u].push_back(v);
            G[v].push_back(u);
            w[u][v] = w[v][u] = wei;
        }
        dfs(s);
        printf("%d %d\n", way[t], max_weight[t]);
        stack<int> path;
        while(!path.empty()){
            path.pop();
        }
        int temp = t;
        while(temp!=s){
            path.push(temp);
            temp = pre[temp];
        }
        path.push(s);
        int len = path.size();
        for(int i=0; i<len-1; i++){
            int temp = path.top();
            path.pop();
            printf("%d ", temp);
        }
        temp = path.top();
        path.pop();
        printf("%d\n", temp);
    }
    return 0;
}

模拟整除

然后积累一下怎么模拟加法和减法吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
char ans[1001];
int main()
{
    int n, len=1;
    int pos = 0, num=1;
    scanf("%d", &n);
    while(len++){
        if(pos||num/n){
            ans[pos++] = num/n+'0';
        }
        num %= n;
        if(num == 0){
            ans[pos] = '\0';
            printf("%s %d", ans, len-1);
            break;
        }
        num = num*10+1;
    }
    return 0;
}

优先队列重新定义运算符号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
struct Node{
    string name;
    int top;
    friend bool operator < (Node a, Node b){
        return a.top>b.top;
    }
};
priority_queue<Node> pq;
int main()
{
    return 0;
}

树状数组求中值，二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
    while(left < right) {
        mid = (left + right) / 2;
        if(getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        if(str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        } else if(str[1] == 'o') {
            if(!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if(!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

前序到后续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <vector>
using namespace std;
bool isMirror;
vector<int> pre;
vector<int> post;
void getpost(int root, int tail) {
    if(root > tail) return ;
    int i = root + 1, j = tail;
    if(!isMirror) {
        while(i <= tail && pre[root] > pre[i]) i++;
        while(j > root && pre[root] <= pre[j]) j--;
    } else {
        while(i <= tail && pre[root] <= pre[i]) i++;
        while(j > root && pre[root] > pre[j]) j--;
    }
    if(i - j != 1) return ;
    getpost(root + 1, j);///左
    getpost(i, tail);///右
    post.push_back(pre[root]);
}
int main() {
    int n;
    scanf("%d", &n);
    pre.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &pre[i]);
    getpost(0, n - 1);
    if(post.size() != n) {
        isMirror = true;
        post.clear();
        getpost(0, n - 1);
    }
    if(post.size() == n) {
        printf("YES\n%d", post[0]);
        for(int i = 1; i < n; i++)
            printf(" %d", post[i]);
    } else {
        printf("NO");
    }
    return 0;
}

#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n;
double z;
double r;
int val[maxn];
vector<int> child[maxn];
double sum = 0;
void solve(int u, double z){
    if(val[u]) {
        sum += val[u]*z;
        return ;
    }
    for(int i=0; i<child[u].size(); i++){
        solve(child[u][i], z*r);
    }
}
void init(){
    memset(val, 0, sizeof(val));
    for(int i=0; i<maxn; i++) child[i].clear();
}
int main()
{
    cin>>n>>z>>r;
    r = (100-r)/100.0;
    init();
    for(int i=0; i<n; i++){
        int k;
        cin>>k;
        if(k == 0){
            int temp;
            cin>>temp;
            val[i] = temp;
            continue;
        }
        else{
            for(int j=0; j<k; j++){
                int temp;
                cin>>temp;
                child[i].push_back(temp);
            }
        }
    }
    solve(0, z);
    //cout<<sum<<endl;
    long long ans = sum;
    printf("%lld\n", ans);
    return 0;
}

建堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int heap[maxn];
int n;
void downadjust(int low, int high){
    int i=low, j=low*2;
    while(j<=high){
        if(j+1<=high&&heap[j]<heap[j+1]) j++;
        if(heap[i]<heap[j]){
            swap(heap[i], heap[j]);
            i=j;
            j = i*2;
        }
        else break;
    }
    return ;
}
void creatheap(){
    for(int i=n/2; i>=1; i--){
        creatheap(i, n);
    }
}
void upadjust(int low, int high){
    int i = high, j=i/2;
    while(j>=low){
        if(heap[j]<heap[i]){
            swap(heap[j], heap[i]);
            i=j;
            j=i/2;
        }
        else break;
    }
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>heap[i];
    }
    
    return 0;
}
# 最长上升序列
``` c++
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int d[maxn];
int g[maxn];
const int INF = 1e9;
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++)cin>>d[i];
    for(int i=0; i<=n; i++) g[i]= INF;
    for(int i=0;i<n; i++){
        int k=lower_bound(g+1,g+n+1, d[i])-g;
        g[k] = d[i];
        d[i] = k;
    }
    for(int i=0; i<n; i++){
        cout<<d[i]<<" ";
    }
    cout<<endl;
    return 0;
}

```

未解决的问题

本文标题:4c题目的小积累

文章作者:Babydragon

发布时间:2018-03-08, 15:04:11

最后更新:2018-03-31, 09:20:53

原始链接:http://baolintian.github.io/2018/03/08/4c题目的小积累/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 最短路维护多个属性的问题
    1. 1.1. 题目
    2. 1.2. AC代码
  2. 2. 模拟整除
  3. 3. 优先队列重新定义运算符号
  4. 4. 树状数组求中值，二分
  5. 5. 前序到后续
  6. 6. 建堆
  7. 7. 未解决的问题
{{ live2d() }}