Codeforces Round #600 (Div. 2)

C - Sweets Eating

基本思路:对于每个i,选出最小的前i个值,越大的值放在越前面,即可得到最小的penalty

假设dp[i]表示前i个元素能获得的最小penalty,那么dp[i + m] = dp[i] + sum[1 : i+m],即[i+1, i+m]放在第一天,其他的以此往后移一天

Codeforces Round #600 (Div. 2)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e5+7;
 5 const ll mod = 998244353;
 6 #define afdafafafdafaf y1;
 7 int ar[maxn], n, m;
 8  
 9 ll p[maxn], s[maxn];
10 int main()
11 {
12     scanf("%d%d", &n, &m);
13     for(int i=1;i<=n;i++)scanf("%d", ar+i);
14     sort(ar+1, ar+n+1);
15     for(int i=1;i<=n;i++)p[i] = p[i-1] + ar[i];
16     //for(int i=1;i<=n;i++)printf("%lld%c", p[i], i==n?'\n' : ' ');
17     for(int i=1;i<=m;i++){
18         ll ins = i, x = p[i];
19         while(ins <= n){
20             s[ins] = x;
21             ins += m;
22             if(ins <= n)x += p[ins];
23         }
24     }
25     for(int i=1;i<=n;i++)printf("%lld%c", s[i], i==n?'\n' : ' ');
26     return 0;
27 }
View Code

 

D - Harmonious Graph

边排序+并查集

Codeforces Round #600 (Div. 2)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e5+7;
 5 const ll mod = 998244353;
 6 #define afdafafafdafaf y1;
 7 int ar[maxn], n, m;
 8  
 9 pair<int,int> p[maxn];
10 int f[maxn];
11 int findx(int x){
12     return f[x] == x ? x : f[x] = findx(f[x]);
13 }
14 int main()
15 {
16     scanf("%d%d", &n, &m);
17     for(int i=1;i<=n;i++)f[i] = i;
18     for(int i=1;i<=m;i++){
19         int a,b;scanf("%d%d", &a, &b);
20         if(a > b)swap(a, b);
21         p[i].first = a;
22         p[i].second = b;
23         a = findx(a);
24         b = findx(b);
25         f[a] = b;
26     }
27     sort(p + 1, p + m + 1);
28     int pa = 0, pb = 0;
29     p[m+1].first = int(1e9);
30     //cout<<p[m+1].first<<'\n';
31     int ans=0;
32     for(int i=1;i<=m+1;i++){
33         //cout<<"i = " << i << ' ' << p[i].first<<" "<<p[i].second<<"\n";
34         if(p[i].first > pb){
35             int x = pa;
36             //cout<<pa<<" "<<pb<<"\n";
37             for(int j=pa+1;j<=pb;j++){
38                 x = findx(x);
39                 int y = j;
40                 y = findx(y);
41                 if(x != y){
42                     f[x] = y;
43                     ans++;
44                 }
45             }
46             pa = p[i].first;
47             pb = p[i].second;
48         }
49         else{
50             pb = max(pb, p[i].second);
51         }
52     }
53     printf("%d\n", ans);
54     return 0;
55 }
View Code

 

E - Antenna Coverage

按照每个区间的头尾排序

正序遍历,求出覆盖前i个节点所需要的最小花费,答案即que(m)

因为两段如果要相接的话,前一段的头一定在后一段的头的前面,所以可以证明排序后正序遍历是正确的。

(比赛的时候求了前后缀,遍历相加,所以代码里是que_l,忽略即可

Codeforces Round #600 (Div. 2)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e5+7;
 5 const ll mod = 998244353;
 6 #define afdafafafdafaf y1;
 7 int ar[maxn], n, m;
 8  
 9 int x[maxn], s[maxn], l[maxn], r[maxn];
10 ll lp[maxn], rp[maxn];
11 pair<int,int> p[maxn];
12 int lmn[maxn << 2], rmn[maxn << 2];
13 void set_l(int x, int val){
14     while(x > 0){
15         if(val >= lmn[x])break;
16         lmn[x] = min(lmn[x], val);
17         x -= x & (-x);
18         //cout<<"x_set = " << x << '\n';
19     }
20 }
21 int que_l(int x){
22     if(x == 0)return 0;
23     int ans = m;
24     while(x <= m){
25         ans = min(ans, lmn[x]);
26         x += x & (-x);
27         //cout<<"x_que = " << x << '\n';
28     }
29     return ans;
30 }
31  
32 int main()
33 {
34     scanf("%d%d", &n, &m);
35     for(int i=1;i<=n;i++)scanf("%d%d", x + i, s + i);
36     for(int i=1;i<=n;i++){
37         int a = x[i], b = s[i];
38         p[i].first = max(1, a - b);
39         p[i].second = min(m, a + b);
40     }
41     sort(p+1, p+n+1);
42     for(int i=1;i<=n;i++){
43         l[i] = p[i].first;
44         r[i] = p[i].second;
45     }
46     for(int i = 0; i < (maxn << 2); i++)lmn[i] = rmn[i] = m;
47     set_l(0, 0);
48     for(int i=1;i<=n;i++){
49         int a = l[i], b = r[i], ins = 0;
50         while(a >= 1 || b <= m){
51             int l_a = que_l(a - 1);
52             set_l(b, l_a + ins);
53             if(a == 1 && b == m)break;
54             if(a > 1)a--;
55             if(b < m)b++;
56             ins++;
57         }
58     }
59     printf("%d\n", que_l(m));
60     return 0;
61 }
View Code

 

F - Cheap Robot

不会

上一篇:webdriver 控制浏览器操作


下一篇:Max-age和Expires的区别