Codeforces Round 1020 (Div. 3)
目录
A. Dr. TC
题目：
代码：
无注释版：
有注释版：
B. St. Chroma
题目：编辑
代码：
无注释版：
有注释版：
C. Cherry Bomb
题目：编辑
代码：
无注释版：
有注释版：
A. Dr. TC
题目：
代码：
无注释版：
#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n;cin>>n;string s;cin>>s;int cnt=0;for(int i=0;i<n;i++){if(s[i]=='1') cnt++;}if(cnt==n&&n==1){cout<<0<<"\n";}else cout<<cnt*(n-1)+(n-cnt)<<"\n";}
} 有注释版：
#include<bits/stdc++.h> // 引入所有标准库，适合竞赛中简化书写
using namespace std;int main(){ios::sync_with_stdio(0); // 提高输入输出效率cin.tie(0);cout.tie(0);int t;cin >> t; // 输入测试用例个数while(t--){int n;cin >> n; // 输入字符串长度（也是网格的行列数）string s;cin >> s; // 输入原始二进制字符串 sint cnt = 0; // 统计 s 中 '1' 的个数for(int i = 0; i < n; i++){if(s[i] == '1') cnt++; // 统计 '1' 的总数量}// 特判：如果 s 中只有一个字符，并且是 '1'if(cnt == n && n == 1){cout << 0 << "\n"; // 翻转之后变成 '0'，没有 '1'，所以输出 0}else{// 核心公式：cnt * (n - 1) + (n - cnt)cout << cnt * (n - 1) + (n - cnt) << "\n";}}
}
B. St. Chroma
题目：
代码：
无注释版：
#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n,x;cin>>n>>x;if(n==1){cout<<"0\n";continue;}if(x>=n){for(int i=0;i<n;i++){cout<<i<<" ";}cout<<"\n";continue;}for(int i=0;i<x;i++){cout<<i<<" ";}for(int i=n-1;i>x;i--){if(i!=x) cout<<i<<" ";}cout<<x<<"\n";}
} 有注释版：
#include<bits/stdc++.h> // 引入标准库中的所有头文件，常用于竞赛编程中简化书写
using namespace std;int main(){ios::sync_with_stdio(0); // 关闭 cin 和 scanf 的同步，加快输入输出速度cin.tie(0); // 取消 cin 和 cout 的绑定，加快输出速度cout.tie(0); // 通常没必要写，但可以确保输出也不会因为 cin 而阻塞int t; // 表示测试用例的个数cin >> t;while(t--){ // 遍历每个测试用例int n, x; // n 是排列的长度，x 是喜欢的颜色cin >> n >> x;if(n == 1){ // 如果排列长度是 1cout << "0\n"; // 唯一可能的排列是 [0]，对应 mex 为 0continue;}if(x >= n){// 如果喜欢的颜色 x 大于等于 n，那最大 mex 也不会达到 x// 所以不管怎么排，x 不可能出现// 但题目说希望最大化出现次数，此时直接输出升序排列即可for(int i = 0; i < n; i++){cout << i << " ";}cout << "\n";continue;}// 接下来是关键构造逻辑：x < n 的情况// 为了让颜色 x 尽可能多地出现在 mex 中// 我们可以先输出 0 到 x-1，使得 mex 到 x 时要等很久for(int i = 0; i < x; i++){cout << i << " ";}// 接着我们从 n-1 到 x+1 倒着输出（跳过 x）for(int i = n - 1; i > x; i--){if(i != x) cout << i << " ";}// 最后输出 xcout << x << "\n";// 为什么这样能让颜色 x 出现次数最多？// 因为前 x 个数都在前面排好，mex 会等到缺 x 才变成 x// 此时往后加的数字都比 x 大，不会影响 mex，直到最后加上 x，mex 才会进到 x+1}
}
C. Cherry Bomb
题目：
代码：
无注释版：
#include<bits/stdc++.h>
using namespace std;
int a[200010],b[200010];
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int n,k;cin>>n>>k;int ma=0;int mi=INT_MAX;for(int i=1;i<=n;i++){cin>>a[i];ma=max(a[i],ma);mi=min(a[i],mi);}map<int,int> mp;mp.clear();for(int i=1;i<=n;i++){cin>>b[i];if(b[i]!=-1){mp[b[i]+a[i]]++;}}//cout<<mp.size()<<"\n";if(mp.size()>1){cout<<0<<"\n";continue;}if(mp.size()==1){int x;for(auto i:mp){x=i.first;}if(x<ma||x-mi>k){cout<<0<<"\n";}else{cout<<1<<"\n";}}if(mp.size()==0){cout<<k-(ma-mi)+1<<"\n";continue;}}
} 有注释版：
#include<bits/stdc++.h> // 引入所有标准库，适合竞赛编程
using namespace std;// 定义全局数组，大小 2e5+10，足够容纳题目所给范围
int a[200010], b[200010];int main(){ios::sync_with_stdio(0); // 提高输入输出效率cin.tie(0);cout.tie(0);int t;cin >> t; // 读取测试用例数量while(t--){int n, k;cin >> n >> k; // 读取数组长度 n 和 最大值限制 kint ma = 0; // 用来记录数组 a 中的最大值int mi = INT_MAX; // 用来记录数组 a 中的最小值for(int i = 1; i <= n; i++){cin >> a[i]; // 读取数组 ama = max(a[i], ma); // 维护最大值mi = min(a[i], mi); // 维护最小值}map<int, int> mp; // 用于统计所有已知 a[i] + b[i] 的和mp.clear(); // 虽然 map 是新建的，这行可以省略for(int i = 1; i <= n; i++){cin >> b[i]; // 读取数组 bif(b[i] != -1){mp[b[i] + a[i]]++; // 只统计不是 -1 的元素，记录和}}// 如果存在多种不同的和，那么无法确定唯一的互补 xif(mp.size() > 1){cout << 0 << "\n"; // 无法构成互补，输出 0continue;}if(mp.size() == 1){int x;for(auto i : mp){x = i.first; // 唯一的 x = a[i] + b[i]}// 检查这个 x 是否合法：// - x 必须 ≥ a 中最大值（否则 b[i] = x - a[i] 会 < 0）// - b[i] = x - a[i] 要 ≤ k，所以 x - mi ≤ k → x ≤ mi + k → x - mi > k 不合法if(x < ma || x - mi > k){cout << 0 << "\n"; // 超出限制}else{cout << 1 << "\n"; // 唯一合法的互补数组}}if(mp.size() == 0){// 所有 b[i] 都是 -1 的情况，没有任何约束条件// 那么我们可以任选 x，使得所有 x - a[i] ∈ [0, k]// 也就是：x ∈ [max(a[i]), min(a[i]) + k]// 所以答案是 (k - (ma - mi) + 1)，即区间长度cout << k - (ma - mi) + 1 << "\n";continue;}}
}