http://poj.org/problem?id=3087

設(shè):s1={A1,A2,A3,...Ac}

s2={Ac+1,Ac+2,Ac+3,....A2c}

則

合在一起成為

Ac+1,A1,Ac+2,A2......A2c,Ac

經(jīng)過一次轉(zhuǎn)換之后變成

s1={Ac+1,A1,Ac+2.....}

s2={...A2c,Ac}

對(duì)應(yīng)之前,每個(gè)數(shù)的序號(hào)發(fā)生的變化是

+1,+2,+3....-c,-c+1,.....

把整個(gè)數(shù)鏈想成環(huán),也相當(dāng)于是:

+1,+2,+3....+c,+c+1,.......

例如A1,由A1->A2->A4->A7....c次之后必然回到A1

所以整個(gè)串經(jīng)過一定次數(shù)的變換一定會(huì)回到最初狀態(tài),只需判斷在回到最初狀態(tài)之前有沒有得到目標(biāo)狀態(tài)即可

?

#include <cstdio>//a=(a+c+1)%(2*c) #include <cstring> using namespace std; const int maxn=1002; int c; char s1[maxn],s2[maxn],aim[maxn],org[maxn],tmp[maxn]; void shuffle(){for(int i=0;i<c;i++){tmp[2*i]=s2[i];tmp[2*i+1]=s1[i];}tmp[2*c]=0; } int main(){int T;scanf("%d",&T);for(int ti=1;ti<=T;ti++){scanf("%d%s%s%s",&c,s1,s2,aim);shuffle();strcpy(org,tmp);int ans=1;if(strcmp(tmp,aim)==0){printf("%d 1\n",ti);continue;}bool fl=false;while(strcmp(org,tmp)!=0||ans==1){strncpy(s1,tmp,c);strncpy(s2,tmp+c,c);shuffle();ans++;if(strcmp(tmp,aim)==0){fl=true;printf("%d %d\n",ti,ans);break;}}if(!fl)printf("%d -1\n",ti);}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/xuesu/p/4338159.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3087 Shuffle'm Up 线性同余,暴力 难度:2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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