題意 ：

• 給一長(zhǎng)度為n的字符串，進(jìn)行以下操作，將所有字符都變成字符c ：取一個(gè)整數(shù)$1<=i<=n$，令所有不被i整除的j有s[j] == c，求最小操作次數(shù)

思路 ：

• 如果s全為c，輸出0
• 如果最后一位為c，輸出1 n
• 如果最后一位不為c，從2開始枚舉，考慮是否有一個(gè)數(shù)能將所有字符改為c，優(yōu)化枚舉方案，用類似于埃氏篩的思想，考慮當(dāng)前這個(gè)數(shù)的所有倍數(shù)在字符串中所對(duì)應(yīng)的字符是否不是c，如果有的話這個(gè)數(shù)就不合理，這樣的復(fù)雜度是$O(nlogn)$，可以過(guò)
• 如果有這樣的數(shù) 輸出 1 x
• 如果沒有 輸出 2 ，取一個(gè)非n因數(shù)的任意數(shù)（比如$n?1$，就不需要枚舉了）和n

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #define endl '\n'using namespace std;typedef long long ll;void solve() {int n;char c;string s;cin >> n >> c >> s;bool flag = true;for (int i = 0; i < n; i ++ )if (s[i] != c){flag = false;break;}if (flag){cout << 0 << endl;return ;}if (s[n - 1] == c){cout << 1 << endl << n << endl;return ;}for (int i = 2; i <= n; i ++ ){bool ok = true;for (int j = i; j <= n; j += i)if (s[j - 1] != c){ok = false;break;}if (ok){cout << 1 << endl << i << endl;return ;}}cout << 2 << endl << n - 1 << ' ' << n << endl; }int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int _ = 1;cin >> _;while (_ -- ){solve();}return 0; }

• 優(yōu)化 ：考慮證明結(jié)論 n的后一半數(shù)中，存在某個(gè)值不在下標(biāo)序列中，則這個(gè)值可以作為答案。充分性顯然成立，必要性考慮n的前一半數(shù)如果作為答案，則一定有一個(gè)它的倍數(shù)屬于n的后一半數(shù)，且不在下標(biāo)序列中
• 上述所有情況都不滿足時(shí)，輸出n和n-1即可消除所有數(shù)

總結(jié)

以上是生活随笔為你收集整理的Make Them Equal 埃氏筛法（1200）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。