題目鏈接：點擊查看

題目大意：給出一個字符串s，問能否通過重組其字母順序，從而滿足：若字符串下標從1開始，對于每一個質數下標，滿足

題目分析：其實在紙上稍微寫寫畫畫就能看出個大概的規律，當字符串的長度比較大的時候，對于每個質數的倍數，都會包含2、3等比較小的倍數，所以當前質數及其倍數下標的字母一定和2、3質數及其倍數下標的字母相同，我們可以歸為一個集合中去，也就是說這個集合中的下標的字母都是相同的才行，有一些特例就是有一些質數下標比較大，大于了len/2，所以它就處于了一個單獨的集合中，換句話說，這個大質數下標對應的字母是隨便一個就行，所以我們用并查集亂搞，那個最大的集合篩選出來就行了，對應著原字符串s中出現次數最多的字母，其他的位置隨便放就好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;int num[30],f[N],mark[N],cnt[N];char ans[N];bool is_pri(int x) {if(x<2)return false;for(int i=2;i*i<=x;i++)if(x%i==0)return false;return true; }int find(int x) {return x==f[x]?x:f[x]=find(f[x]); }void merge(int x,int y)//x->y {int xx=find(x);int yy=find(y);if(xx!=yy){f[xx]=yy;cnt[yy]+=cnt[xx];} }void init() {for(int i=1;i<N;i++)f[i]=i;memset(mark,-1,sizeof(mark)); } int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();string s;cin>>s;int n=s.size();for(int i=0;i<n;i++)num[s[i]-'a']++;int mmax=*max_element(num,num+26);//原字符串中最大有mmax個相同的字母for(int i=1;i<=n;i++){if(!is_pri(i))//當前數字不是素數，直接跳過continue;for(int j=1;j*i<=n;j++){if(mark[j*i]!=-1)//當前數字被標記過，則將當前素數與之前素數合并merge(mark[j*i],i);else//當前數字沒被標記過，將當前數字與當前素數合并，并且將標記指向為當前素數{merge(j*i,i);mark[j*i]=i;cnt[i]++;}}}int mx=*max_element(cnt,cnt+N);//新字符串需要mx個相同的字母if(mx>mmax)puts("NO");else{int ch;//哪個字母可以填在相同位置 for(int i=0;i<26;i++){if(mx<=num[i]){ch=i;num[i]-=mx;break;}}int pos=find(2);//哪個位置需要填字母ch puts("YES");for(int i=1;i<=n;i++){if(find(i)==pos)ans[i]='a'+ch;else{for(int j=0;j<26;j++){if(num[j]){num[j]--;ans[i]='a'+j;break;}}}}puts(ans+1);}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 123A prime permutation(并查集，水题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。