Codeforces Round #821 (Div. 2)

助人度己

A. Consecutive Sum

• 对于 i ∈ [1,n] , i\%k 相同的是一个集合的数，取每个集合的最大值放置在 [1,k] 即为答案。
  

Code
const int N = 2e5 + 5;
ll a[N];
ll c[N];
int main() {
        IO;
        int T;
        cin >> T;
        while(T -- ) {
                int n, k;
                cin >> n >> k;
                for (int i = 0; i < n; i ++ ) {
                        c = 0;
                        cin >> a;
                }
                for (int i = 0; i < n; i ++ ) {
                        c[i%k] = max(c[i%k], a);
                }
                ll sum = 0;
                for (int i = 0; i < k; i ++ ) sum += c;
                cf(sum);
        }
        return 0;
}
B. Rule of League

• 当 x,y 都不为 0 时，无解。
  

证明：如果 x,y 都大于 0 ，意味着每个人都要至少赢一次，那么总共赢的轮数至少为 n 轮，而只有 n-1 轮游戏，所以这种情况无解。

• 当 x,y 都为 0 时，无解。
  

证明：如果 x,y 都等于 0 ，意味着每个人都没有赢， 显然不合理。

• 有一个为 0 时：
  

假设 x 非 0 ：
由于每个人要么赢 0 次，要么赢 x 次，而总共只有 n-1 轮，所以只能当 x|(n-1) 时，才可成立。
构造时，只需要等间距 x 的选取 \frac{n-1}{x} 个人，让他们连续赢 x 轮。
y 非 0 同理。
Code
int main() {
        // IO;
        int T;
        cin >> T;
        while(T -- ) {
                int n, x, y;
                cin >> n >> x >> y;
                if(x == 0 && y == 0) {
                        cf("-1");
                }
                else {
                        if(x == 0) {
                                if((n-1)%y == 0) {
                                        for (int i = 2; i <= n; i += y) {
                                                int k = y;
                                                while(k -- ) cout << i << ' ';
                                        }
                                        cout << endl;
                                }
                                else cf("-1");
                        }
                        else if(y == 0) {
                                if((n-1)%x == 0) {
                                        for (int i = 2; i <= n; i += x) {
                                                int k = x;
                                                while(k -- ) cout << i << ' ';
                                        }
                                        cout << endl;
                                }
                                else cf("-1");
                        }
                        else puts("-1");
                }
        }
        return 0;
}
C. Parity Shuffle Sorting

• 选择 l,r 会有以下几种情况：
  

偶+偶 与 奇+奇 ，会使得 a_l:=a_r ， a_l 与之前的奇偶性不变。
奇+偶 与 偶+奇 ，会使得 a_r:=a_l ， a_r 与之前的奇偶性改变，与 a_l 的奇偶性保持一致。
故有这样一种构造方案使得所有数都变为 a_n ：
考虑当 a_1 与 a_n 奇偶性一致时，可重复用 a_n 去操作 i∈[1,n-1] 中与 a_n 奇偶性一致的 a_i ，
然后再利用 a_1 去操作 i∈[2,n-1] 中与 a_1 奇偶性相反的 a_i ，然后所有数都会与 a_n 相同了。
当 a_1 与 a_n 奇偶性相反时，
只需要对 a_1,a_n 先使用一次 奇+偶 操作 或者 偶+奇 操作， a_1 与 a_n 的奇偶性就保持一致，剩下的和上面方法同理。
Code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5 + 5;
int a[N];
int check(int x, int y) {
        int val = (x+y)%2;
        return val;
}
int main() {
        int T;
        cin >> T;
        while(T -- ) {
                int n;
                cin >> n;
                for (int i = 1; i <= n; i ++) cin >> a;
                if(n == 1) {
                        cout << "0" << '\n';
                        continue;
                }
                vector<PII> v;
                if(check(a[1], a[n])) {
                        a[n] = a[1];
                        v.push_back({1, n});
                }
                for (int i = 1; i <= n-1; i ++ ) {
                        if(!check(a, a[n]) && a != a[n]) {
                                v.push_back({i, n});
                                a = a[n];
                        }
                }
                for (int i = 2; i <= n-1; i ++ ) {
                        if(check(a[1], a)) {
                                v.push_back({1, i});
                                a = a[1];
                        }
                }
                // puts("##");
                // for (int i = 1; i <= n; i ++ ) cout << a << ' ';
                // cout << endl;
                cout << v.size() << '\n';
                for (auto [x,y]:v) cout << x << ' ' << y << '\n';
        }
        return 0;
}
D1. Zero-One (Easy Version)

大意：
有一个 01 串 s

• 操作：选择两个索引 l,r ,如果 l+1=r ,花费 x 的代价对 s_i,s_j 翻转，否则花费 y 的代价。
  

问变成目标串 t 的最小花费。
思路：
对于串 s,t 不同位置的个数要保证为偶数，否则无解。
证明：因为每次操作会让两个(偶数个)位置翻转，所以不可能使得最后有奇数个位置翻转。
由于限制了 x\ge y ,所以应该优先选择距离大于 1 的，
设不同位置的个数有 len 个，
当 len>2 时，总是可以全部利用花费 y 的操作完成任务。
当 len=2 ,需要特判是否两个位置相邻，如果不相邻，用 y 操作，否则有两种方法：1.选择一个不是这两位置的第三者，使用它分别两次操作相邻的两个位置进行操作 y ，即可翻转，2.选择一次 x 操作。
Code
int main() {
        IO;
        int T;
        cin >> T;
        while(T -- ) {
                int n;
                cin >> n;
                ll x, y;
                cin >> x >> y;
                string s1, s2;
                cin >> s1 >> s2;
                vector<int>ve;
                for (int i = 0; i < n; i ++ ) {
                        if(s1 != s2) {
                                ve.push_back(i);
                        }
                }
                if(ve.size()%2 == 1) {
                        cf("-1");
                        continue;
                }
                ll res = 0;
                if(ve.size()==2 && ve[1]-ve[0] == 1)
                res = min(x, y*2);
                else res = y * ve.size() / 2;
                cf(res);
        }
        return 0;
}
D2. Zero-One (Hard Version)

与 D1 问题不同的是，没有限制  x\le y .

• 区间DP
  

定义 dp(i,j) 表示 s[i,j] 变成目标串 t[i,j] 的最小花费。
共有四种转移：

• dp(i,j)=dp(i,j-2)+calc(j-1,j)
  
• dp(i,j)=dp(i+1,j-1)+calc(i,j)
  
• dp(i,j)=dp(i+2,j)+calc(i,i+1)
  

最后一种容易忘掉，也就是 D1 的策略，当区间长度 >2 时，全部用 y 操作。

• dp(i,j)=\frac{j-i+1}{2} \cdot y
  

去四者 min 即可。
Code
ll x, y;
vector<int>ve;
string s1, s2;
ll dp[5005][5005];
ll calc(int a, int b) {
        int pos = ve-ve[a];
        if(pos == 1)
                return min(x, y*2);
        else
                return min(x*pos, y);
}
int main() {
        IO;
        int T;
        cin >> T;
        while(T -- ) {
                ve.clear();
                int n;
                cin >> n >> x >> y;
                cin >> s1 >> s2;
                for (int i = 0; i < n; i ++ ) {
                        if(s1 != s2) {
                                ve.push_back(i);
                        }
                }
                int len = ve.size();
                if(len%2 == 1) {
                        cf("-1");
                        continue;
                }
               
                for (int k = 2; k <= len; k += 2 ) {
                        for (int i = 0; i+k-1 < len; i ++ ) {
                                int j = i+k-1;
                                if(k == 2) dp[j] = calc(i, j);
                                else
                                dp[j] = min({dp[i+1][j-1]+calc(i,j), dp[i+2][j]+calc(i,i+1), dp[j-2]+calc(j-1,j), y*len/2});
                        }
                }
                cf(dp[0][len-1]);
        }
        return 0;
}

一个洋葱圈

前排支持下了哦~

我就是砖家

我也顶起出售广告位