Educational Codeforces Round 152 (Rated for Div. 2)（A~D）---Day12
前言：DSU教学局？E也是DSU
1849A - Morning Sandwich
题意：给定a个面包，b个奶酪，c个火腿。规定三明治从上到下为面包、奶酪/火腿、面包、奶酪/火腿....面包组成。求最多能叠多少层。
思路：层数由面包决定，所取面包 = 奶酪 + 火腿 + 1。因此层数为min(a,b + c + 1) * 2 - 1
void solve()
{int a , b ,c;cin>>a>>b>>c;cout<1849B - Monsters
题意：给了n个怪物的血量和你的攻击力k。每次攻击选择当前血量最高的怪物，怪物血量降为0及以下时死亡。求怪物死亡顺序。
思路：当有怪物血量大于k时，会优先攻击此怪物，最终怪物血量都小于等于k。此时，血量越大的怪物越早死亡。因此假设怪物血量%k = x，那么他在死亡前的血量就是x。由此可得，当怪物血量%k = 0 时，它将是最早一批死亡的怪物。当怪物血量%k != 0 时，剩余血量越高的怪物越早死亡。照此来排序即可。
int cmp1(pl a, pl b){if(a.x != b.x){return a.x > b.x;}else{return a.y < b.y;}
}
void solve()
{int n , k;cin>>n>>k;pl ans[n + 5];for(int i = 1 ; i <= n ; i ++){int num;cin>>num;int l = (num - 1) % k;ans[i].x = l;ans[i].y = i;}sort(ans+1 , ans + n + 1 , cmp1);for(int i = 1 ; i <= n ; i++){cout<1849C - Binary String Copying
题意：给定一个01串s。共进行m次操作，每次操作给定数字 L 和 R 在原串上对[L,R]范围内的串进行从小到大排序。求m次操作中共产生了多少个不同的串。
思路：例子 0011100110011，对于[1,5] 和[1,3]操作而言，他们其实是一样的，因为[4,5]这个区间上都是1，那么排序之后仍然都是1。同样的，对于[1,8]和[2,8]操作而言，也是一样的，因为[1,1]是0，那么排序之后仍然是0。因此可以得到结论：当L落在了连续的0上面时，无论L取那一位，其结果都是一样的；当R落在了连续的1上面时，无论R取哪一位，结果也都是一样的。另外还有特殊的情况：例如[1,7]与[1,9]，他们的结果也是一样的。对于[1,7]来说，虽然R落在了0上面，但0之后跟了连续的1，那么排完序之后也是一样的。同理，例如[3,5]和[1,5]，其结果也是一样的。此时虽然L落在了1上面，但是由于1前面就是0，排序之后不会有影响。综上：共有4种情况：1、当L落在了连续的0之上，那么L取这区间内的任意值结果都一样。2、当R落在了连续的1之上，那么R取这区间内的任意值结果都一样。3、如果L落在了1上面，且刚好L-1的位置上是0，那么L落在L-1之前连续的0上面结果都是一样的。4、如果R落在了0上面，且刚好R+1的位置上是1，那么R落在之后连续的1上面的结果也都是一样的。连续的问题可以用DSU来解决，然后用set来存答案，最后还需要特判一下刚好等于原串的情况。
void solve()
{int n , m;cin>>n>>m;DSU dsu(n +5);setans;string s;cin>>s;s = " " + s;for(int i = 2; i < (int)s.size() ; i ++){int l = s[i - 1] - '0';int r = s[i] - '0';if(l == r){dsu.merge(i - 1 , i);}}int f = 0;int l , r;for (int i = 0; i < m; i++) {cin >> l >> r;if(s[l] == '0'){l = dsu.find(l);}else if(l - 1 > 0 && s[l - 1] == '0'){l = dsu.find(l - 1);}if(s[r] == '1'){r = dsu.find(r);}else if(r + 1 <= n && s[r + 1] == '1'){r = dsu.find(r + 1);}if (dsu.same(l, r)) {f = 1;continue;}else if (s[l]=='0' && s[r]=='1' && dsu.same (dsu.find(l), dsu.find (dsu.find (r) - 1))){f = 1;continue;}ans.insert ({ l, r });}
/* for(auto t : ans){cout< 1849D - Array Painting
题意：给定一个长度为n的数组，其值仅为0，1，2。起初，每个数的颜色都是红色，你可以进行一下操作：1、花费1金币使得这个数变为蓝色。2、选择一个蓝色的大于0的数，并选择与之相邻的数，将其变为蓝色，同时自身数减一。求最少需要多少金币使得所有数都是蓝色。
思路：分析一下可得：当一个0的左右两边都是0时，它必须要花费1金币才能使得其变为蓝色。因此，若存在连续的0，只需要保留2个，其他都花费1金币使其变为蓝色。这样做可以减少数组量。当存在连续的非0序列时，若所有数都是1，那么花费金币使得第一个1变成蓝色，其他都可以通过相邻的数变为蓝色，同时可以把序列右边的0变为蓝色。如果花费金币使得最后一个1变为蓝色，其他都变为蓝色，同时将序列左边的0变为蓝色。因此这个序列可以用一个1来替代（例如001111110 跟0010是一样的）；如果有一个数是2，那么只需要将这个数变为蓝色，其他都相互传递变为蓝色，同时可以将序列两边的0都变成1，此时可以进行合并，将整个序列变成2（例如00112111211100跟00200是一样的）。简化过程可以用DSU或者直接另建一个数组，然后再遍历数组，每个非0的都花费1金币。然后根据贪心思想，先对左边的0处理然后再对右边的0处理。处理过的0不需要话金币，没处理过的需要花1金币。最终再遍历一遍求金币数即可。
DSU(队友的写法）:
void solve ()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];st[i] = a[i] != 0;r[i] = i;maxx[i] = a[i];}DSU dsu (n);for (int i = 2; i <= n; i++) {if (a[i] != 0 && a[i - 1] != 0) {dsu.merge (i - 1, i);}}for (int i = 1; i <= n; i++) {if (dsu.p[i] == i) {if (a[i] == 0) continue;else ans++;if (maxx[i] == 1) {if (i - 1 > 0 && !st[i - 1]) {st[i - 1] = true;}else {st[r[i] + 1] = true;}}else if (maxx[i] == 2) {st[i - 1] = true;st[r[i] + 1] = true;}}}for (int i = 1; i <= n; i++) {if (!st[i]) ans++;}cout << ans << endl;}直接建数组：
void solve()
{int n;cin>>n;int a[n + 5];for(int i = 0 ; i < n ; i ++){cin>>a[i];}vectorans;int cnt0 = 0 , cntmax = 0;int cost = 0;for(int i = 0 ; i < n ; i++){if(a[i] == 0){if(cntmax != 0){ans.pb(cntmax);cntmax = 0;}if(cnt0 == 2){cost++;continue;}cnt0++;ans.pb(a[i]);}else{cnt0 = 0;cntmax = max(cntmax,a[i]);}}if(cntmax != 0){ans.pb(cntmax);}bool isv[ans.size()];memset(isv,false,sizeof isv);for(int i = 0; i < ans.size() ; i ++){if(ans[i] != 0){if(i - 1 >= 0 && isv[i - 1] == false){isv[i - 1] = true;ans[i] --;}if(ans[i]){if(i + 1 < ans.size()){isv[i + 1] = true;}}}}for(int i = 0; i < ans.size() ; i ++){if(!isv[i]){cost++;}}cout< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！