ACM_JLINE.

CSP-J[1]

CSP
字数统计: 1.2k阅读时长: 6 min
2019/11/01 Share

计蒜客信息学国庆普及组模拟赛

题目质量真的可以

A 元音

题目：

输出元音个数（签到）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;

string s;
int ans;
int main(){
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' ||
            s[i] == 'o' || s[i] == 'u')
           ans++;
    }
    cout << ans << endl;
    return 0;
}

B 按位与

题目：

n 个数中两两按位与，输出最大。

题解：

贪心，从最高位算起。时间复杂度O(32 * n)。

代码：

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
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;
const int N = 200005;
int n;
int a[N], v[N];
int ans;
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }

    for(int i = 31; i >= 0; i--){
        int cnt = 0;
        for(int j = 1; j <= n; j++){
            if(v[j] == 0){
                if((1 << i) & a[j]){
                    cnt++;
                }
            }
        }
        if(cnt >= 2){
            for(int j = 1; j <= n; j++){
                if(((1 << i) & a[j]) == 0) v[j] = 1;
            }
            ans += (1 << i);
        }
    }
    printf("%d\n", ans);
    return 0;
}

C 买东西

题目：

每个商品有两个属性 ai， bi，买 x个 i商品收获的喜悦值是 x max(ai - x bi, 0)，最多可以买 m 个商品（一种商品可以多次购买），请问获得的喜悦值最大是多少。

题解：

当第i个商品已经买了x个时，再多买1个，可以算得喜悦值增加了 ai - bi - 2 x bi。

所以我们只要用一个优先队列，每次取出 ai - bi - 2 x bi中最大的，然后在ai - bi - 2 (x+1) bi，放出。操作m次即可。

代码：

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
#include <iostream>
#include <cstdio>
#include <queue>
#define ll long long
using namespace std;
const int N = 1e5 + 5;

int n, m;
int a[N], b[N];
ll ans;
struct node
{
    int id, x;
    ll sum;
     
};
bool operator < (const node &a, const node &b){
    return a.sum < b.sum;
}
priority_queue <node> q;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &a[i], &b[i]);
        q.push((node){i, 1, a[i] - b[i]});
    }

    while(m--){
        node tmp = q.top();q.pop();
        int i = tmp.id, tmp_x = tmp.x;
        ll tmp_sum = tmp.sum;
        ans += max((ll)0, tmp_sum);
        q.push((node){i, tmp_x + 1, a[i] - b[i] - (ll)2 * tmp_x * b[i]});
    }
    printf("%lld\n", ans);
    return 0;
}

D 图论

题目：

给你一张无向带权图，问任意两点间的路径最大值最小化是多少。

题解：

首先要求两点的那条路劲就一定是最小生成树的边构成的。

然后用倍增求mx数组，记录i向上跳2^j步路劲上最大值。

最后注意一下是不是同一个联通块的。

代码：

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
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 400005;

int n, m, Q;
struct node{
    int x, y, z;
}edge[N];
int fa[N];

int Next[N], head[N], ver[N], w[N], tot;

bool cmp(node a, node b){
    return a.z < b.z;
}

int find(int x){
    return fa[x] != x ? fa[x] = find(fa[x]) : x;
}

void add(int x, int y, int z){
    ver[++tot] = y; w[tot] = z;
    Next[tot] = head[x];
    head[x] = tot;
}

void Kruskal(){
    sort(edge + 1, edge + m + 1, cmp);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++){
        int fx = find(edge[i].x);
        int fy = find(edge[i].y);
        if(fx == fy) continue;
        fa[fx] = fy;
        add(edge[i].x, edge[i].y, edge[i].z);
        add(edge[i].y, edge[i].x, edge[i].z);
    }
}

queue <int> q;
int f[50005][25], d[N], mx[50005][25];
void bfs(){
    q.push(1); d[1] = 1;
    while(q.size()){
        int x = q.front(); q.pop();
        //cout << x << " ";
        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i];
            if(d[y]) continue;
            q.push(y);
            d[y] = d[x] + 1;
            f[y][0] = x;
            mx[y][0] = w[i];
            for(int j = 1; j <= 20; j++){
                f[y][j] = f[f[y][j-1]][j-1];
                mx[y][j] = max(mx[y][j-1], mx[f[y][j-1]][j-1]);
            }
        }
    }
}

int lca(int x, int y){
    int ans = 0;
    if(d[x] > d[y]) swap(x, y);
    for(int i = 20; i >= 0; i--){
        if(d[f[y][i]] >= d[x]) {
            ans = max(ans, mx[y][i]);
            y = f[y][i];
        }
    }
    if(x == y) return ans;
    for(int i = 20; i >= 0; i--){
        if(f[x][i] != f[y][i]){
            ans = max(ans, mx[x][i]);
            ans = max(ans, mx[y][i]);
            x = f[x][i];
            y = f[y][i];
        }
    }
    ans = max(ans, mx[x][0]);
    ans = max(ans, mx[y][0]);
    return ans;
}

int main(){
    scanf("%d%d%d", &n, &m, &Q);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);
    }

    Kruskal();
    bfs();
    for(int i = 1; i <= Q; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        if(find(x) == find(y))
        printf("%d\n", lca(x, y));
        else printf("-1\n");
    }
    return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/11/01/计蒜客普及组1/

发表日期：November 1st 2019, 3:17:00 pm

更新日期：November 1st 2019, 3:22:02 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 计蒜客信息学国庆普及组模拟赛
    1. 1.1. A 元音
    2. 1.2. B 按位与
    3. 1.3. C 买东西
    4. 1.4. D 图论
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路