题解 CF1594C Make Them Equal
智子
2021-10-09 22:18:59
## 题意
输入一个整数 $n$ ,一个字符 $c$ 和一个长度为 $n$ 的字符串 $s$。
选择若干个数 $x$,对于 $s$ 的第 $i$ 个字符 $s_i$,如果 $i$ 不能被 $x$ 整除,$s_i$ 就会被替换为 $c$。
求最少的操作次数和任意一种方案。
## 思路
本题的关键是,不论 $s$ 的内容如何,答案最多只为 $2$。因为选取了 $n$ 和 $n - 1$ 后肯定会将 $s$ 的所有字符全部变成 $c$,所以只需要考虑是否只需要一步就能解决问题即可,如果不能就直接输出 `2 ` 和 `n n - 1`。
对于只需要一步的情况,直接枚举即可,复杂度 $O(n \ln n)$。
## 代码
```cpp
#include<iostream>
using namespace std;
const int MAXN = 300000 + 5;
char c, s[MAXN];
int n, m;
int main() {
int T;
cin >> T;
while(T--) {
cin >> n >> c >> (s + 1);
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(s[i] != c) {
cnt++;
}
}
if(cnt == 0) {
cout << 0 << endl;
continue;
}
int ans = 0;
bool p = false;
for(int i = 1; i <= n; i++) {
bool flag = true;
for(int j = i; j <= n; j += i) {
if(s[j] != c) {
flag = false;
}
}
if(flag) {
ans = i;
p = true;
break;
}
}
if(p) {
cout << 1 << endl;
cout << ans << endl;
} else {
cout << 2 << endl;
cout << n << " " << n - 1 << endl;
}
}
return 0;
}
```