Codeforces Round #786 (Div. 3) 比赛总结
比赛信息
- 比赛名称：Codeforces Round #786 (Div. 3)
- 比赛地址：Codeforces
题目解析与总结
C - 无限替换
这是一道简单的构造题，需要注意分类讨论。
题目描述
给定T组测试数据，每组包含两个字符串S和T。字符串S仅由字符'a'构成，字符串T由小写字母构成，两字符串长度均小于50。允许的操作是每次将S中的一个'a'替换为T。问最终可以得到多少种不同的字符串S'？如果可以无限生成不同的字符串，返回-1。
解题思路
- 如果T中包含字符'a'且长度大于1，则答案为-1。
- 如果T为单个字符'a'，则答案为1。
- 如果T中不包含字符'a'，则答案为\(2^{len(S)}\)。
参考代码
void solve() {
string s, t; cin >> s >> t;
if (t == "a") cout << 1 << "\n";
else if (t.find('a') != string::npos) cout << -1 << "\n";
else cout << (1LL << s.size()) << "\n";
}
D - A-B-C 排序
这道题最初看起来很难，但实际上只需通过简单的规律即可解决。
题目描述
给定T组测试数据，每组包含三个数组A、B和C。数组A初始包含N个元素，数组B和C为空。允许的操作是每次将A的最后一个元素插入到B的中间位置，或者将B的中间元素插入到C的末尾位置。问经过若干次操作后，数组C是否可以是非递减序列。
解题思路
通过观察可以发现，对于奇数长度的A，其元素会按照特定顺序进入C。利用这一规律，可以将问题转化为判断排序后的A是否为非递减序列。
参考代码
void solve() {
int n; cin >> n;
vector<int> a(n), b(n);
for(int i=0; i> a[i];
b = a;
sort(b.begin(), b.end());
if(n%2==1){
if(a[0]!=b[0]) {cout << "NO\n"; return;}
for(int i=1; i E - 破墙
这是一道涉及分类讨论的题目。
题目描述
有N堵墙，每堵墙都有一定的生命值。每次攻击可以选择其中一堵墙，该墙及其相邻的墙会受到相应的伤害。问至少需要多少次攻击才能使任意两堵墙的生命值降至0以下。
解题思路
可以通过选择相邻的两堵墙或生命值最小的两堵墙进行攻击，并计算所需最小的攻击次数。
参考代码
void solve(){
int n; cin >> n;
vector<int> walls(n);
for(auto &w: walls) cin >> w;
int result = INT_MAX;
for(int i=1;iF - 桌面重新排列
这是一道需要处理大量查询的题目，可以采用线段树或规律的方法来解决。
题目描述
有一个N*M的二维网格，每个位置可以放置一个图标或为空。每次操作可以将某个位置的图标移除或添加。问每次操作后，使得网格变为有序状态需要的最少操作次数。
解题思路
可以将二维网格视为一维数组进行处理，并通过维护当前有序区域的边界来快速计算每次操作后的结果。
参考代码
void solve(){
int n, m, q; cin >> n >> m >> q;
vector<char> grid(n*m);
int iconCount = 0;
for(auto &c: grid){
cin >> c;
if(c=='*') iconCount++;
}
int ans = 0;
for(int i=0; i> x >> y;
x--; y--;
int pos = x*m + y;
if(grid[pos]=='.'){
iconCount++;
if(grid[iconCount-1]=='*') ans--;
if(pos>=iconCount) ans++;
grid[pos]='*';
} else {
if(grid[iconCount-1]=='*') ans++;
iconCount--;
if(pos>=iconCount) ans--;
grid[pos]='.';
}
cout << ans << "\n";
}
}
