貌似是之前现场做的ABC。C开始没补。
C题，现在想了一会就会写了。并查集维护为一个root的，它们的颜色变成这个集合中颜色最多的那个颜色即可。
F题，题意是选定一个数字，其他数都变成不大于原来那个数的一个整数倍的数，求最大的所有数的和。做法的话，举个例子就能明白了。比如说当前选定的是5，那么5~9的数都变成5，10~14中的数都变成10...依次类推。那么只要能够快速的求出每个范围内需要求的数字的话就能够在nlogn的复杂度下求解了。那么考虑前缀和优化即可。cnt[i]用来表示1~i有多少个数字，那么i~j有多少个数字即cnt[j]-cnt[i-1]。具体见代码：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 #include <set> 6 #include <map> 7 #include <string> 8 #include <vector> 9 using namespace std; 10 const int N = 200000 + 5; 11 typedef long long ll; 12 13 int cnt[N]; 14 bool vis[N]; 15 16 int main() 17 { 18 int n; 19 cin >> n; 20 for(int i=1;i<=n;i++) 21 { 22 int x; 23 scanf("%d",&x); 24 cnt[x]++; 25 vis[x] = 1; 26 } 27 for(int i=1;i<N;i++) cnt[i] += cnt[i-1]; 28 ll ans = 0; 29 for(int i=1;i<N;i++) 30 { 31 if(vis[i] == 0) continue; 32 ll temp = 0; 33 for(int j=i;j<N;j+=i) temp += (ll)j*(cnt[min(j+i-1, N-1)]-cnt[j-1]); // j~j+i-1 34 ans = max(ans, temp); 35 } 36 cout << ans << endl; 37 return 0; 38 }
D题，很有意思的题目。题意是有n个单词，每个单词都由一些不超过c的数字组成。如果旋转1圈的话，那么所有单词的所有数字都+1，如果本来就是c的话就变成1。问最少需要旋转几圈使得n个单词的字典序非降。做法是依次考虑前后两个单词，它们能够使得题意满足的情况下的转几圈的一个区间。最后只要能够找出一个区间使得有n-1个区间相交在这里即可。然后发现是可以从左到右单点扫描的，那么用差分标记即可。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 #include <set> 6 #include <map> 7 #include <string> 8 #include <vector> 9 using namespace std; 10 const int N = 500000 + 5; 11 typedef long long ll; 12 13 vector<int> word[N]; 14 int d[(int)1e6+100]; 15 void update(int l,int r) {d[l]++;d[r+1]--;} 16 17 int main() 18 { 19 int n,c; 20 cin >> n >> c; 21 for(int i=1;i<=n;i++) 22 { 23 int sz; 24 scanf("%d",&sz); 25 for(int j=1;j<=sz;j++) 26 { 27 int temp; 28 scanf("%d",&temp); 29 word[i].push_back(temp); 30 } 31 } 32 for(int i=1;i<n;i++) 33 { 34 int j,x,y; 35 int len = min(word[i].size(), word[i+1].size()); 36 for(j=1;j<=len;j++) 37 { 38 x = word[i][j-1]; 39 y = word[i+1][j-1]; 40 if(x != y) break; 41 } 42 if(j == len+1 && word[i].size() > word[i+1].size()) 43 { 44 puts("-1"); 45 return 0; 46 } 47 int L, R; 48 if(x < y) update(0, c - y), update(c + 1 - x, c - 1); 49 else if(x > y) update(c + 1 - x, c - y); 50 else update(0, c - 1); 51 } 52 int sum = 0; 53 for(int i=0;i<c;i++) 54 { 55 sum += d[i]; 56 if(sum == n-1) return 0*printf("%d ",i); 57 } 58 puts("-1"); 59 return 0; 60 }
E题，不会dp的方法。用的是反向递推的方法。题意和分析见代码：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 using namespace std; 6 const int N = 2e5 + 5; 7 8 int a[N]; 9 10 int main() 11 { 12 int n; 13 cin >> n; 14 for(int i=1;i<=n;i++) scanf("%d",a+i),a[i]+=a[i-1]; 15 int ans = a[n]; 16 /* 17 题意：双方每次至少从左边拿两个合并成一个新的数，并且得到新的这个数的分数值。 18 双方都要自己的分数尽量的比对方高。 19 问双方都没有操作失误的情况下，先拿的人能够得到的和对方的分数相差的最大值是多少。 20 ans表示上一个操作者的最优答案。 21 因为最后一个数字肯定是最后一个人拿的，那么倒着递推答案即可。 22 注意，i不能到1是因为第一次最少拿两个来合并。 23 */ 24 for(int i=n-1;i>1;i--) ans = max(ans, a[i]-ans); 25 cout << ans << endl; 26 return 0; 27 }