Codeforces Round #381 (Div. 2)

A : 题意，你有n个copybooks,你需要把他凑成4的倍数，现在书店里有三种类型的copybooks可以选择，

a rubles 1 本 copybook， b rubles 2 本 copybooks, c rubles 3本 copybooks。

暴力枚举，把n凑成4的倍数

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long int ll;
 5 int main() {
 6     ll n, a, b, c;
 7     cin >> n >> a >> b >> c;
 8     int m = (4 - n%4)%4;
 9     long long int sum = 0;
10     if(m == 1) {
11         sum = min(a, 3*c);
12         sum = min(sum, b+c);
13     } else if(m == 2) {
14         sum = min(2*a, b);
15         sum = min(2*c, sum);
16     } else if(m == 3) {
17         sum = min(c, 3*a);
18         sum = min(sum, a+b);
19     }
20     cout << sum << endl;
21     return 0;
22 }

B：题意给一个长度为n的数组，代表花的权值，Little Alyona的妈妈给你了m种选择，你可以选择这个区间内所有的花，当然这些可以叠加，问你能取到的最大的权值是多少？

记录花权值的前缀和，对每次选择，如果这段区间的值>0,则选取这段区间

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long int ll;
 5 int a[102];
 6 int b[102];
 7 int main() {
 8     int n, m;
 9     scanf("%d%d", &n, &m);
10     for(int i = 1; i <= n; i++){
11         scanf("%d", &a[i]);
12         b[i] = b[i-1] + a[i];
13     }
14     int l, r, sum = 0;
15     for(int i = 1; i <= m; i++){
16         scanf("%d%d", &l, &r);
17         int ans = b[r] - b[l-1];
18         if(ans > 0) sum += ans;
19     }
20     printf("%d
", sum);
21     return 0;
22 }

C：题意定义mex为区间[l,r]内不能包括的最小的非负整数，让你构造一个长度为n的数组，使mex尽可能大

找到最小的区间长度，这就是mex了，不要问为什么，然后构造0 1 2 3 ~ mex-1 0 1 2 3 mex-1 的序列

你任取一端长度>= mex的序列，其答案最小为mex，那么直接可以对mex取模

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long int ll;
 5 
 6 int main() {
 7     int n, m;
 8     scanf("%d%d", &n, &m);
 9     int l, r, mod = n;
10     for(int i = 1; i <= m; i++){
11         scanf("%d%d", &l, &r);
12         if(r-l+1 < mod) mod = r-l+1;
13         //mod = min(r-l+1, mod);
14     }
15     printf("%d
0", mod);
16     for(int i = 1; i < n; i++){
17         printf(" %d", i%mod);
18     }
19     printf("
");
20 }

D：给你一颗树，每个节点都有权值，每条边都有距离，如果dis（v， u） <= a[u]，则v控制u

问你每个节点控制的点是多少个

直接建图遍历，在一条路径上的节点用二分找

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int>P;
const int MAXN = 2e5+5;
vector<P> s[MAXN];
int a[MAXN] = {}, sta[MAXN] = {},ans[MAXN] = {};
ll dis[MAXN]= {};
void dfs(int u, ll d, int id){
    sta[id] = u, dis[id] = d;
    int L = lower_bound(dis, dis+id+1, d-a[u])-dis;
    ans[sta[L-1]]--;
    ans[u]++;
    for(int i = 0; i < int(s[u].size()); i++){
        dfs(s[u][i].first, d+s[u][i].second, id+1);
        ans[u] += ans[s[u][i].first];
    }
}
int main() {
    int n, p, w;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 2; i <= n; i++) {
        scanf("%d%d", &p, &w);
        s[p].push_back(make_pair(i, w));
    }
    dis[0] = -1e9;
    dfs(1, 0, 1);
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]-1);
}