歷年藍(lán)橋杯省賽b組真題試題-資料下載頁
2025-03-24 23:24本頁面
【正文】 =1表示i能夠用兩個(gè)完全平方數(shù)相加而得。intn。voidinit(){for(inti=0i*i=ni++)for(intj=0j*j=nj++)if(i*i+j*j=n)mpt[i*i+j*j]=1。}intmain(){intflag=false。scanf(%d,amp。n)。init()。for(inti=0i*i=ni++){for(intj=0j*j=nj++){if(mpt[ni*ij*j]==0)continue。//如果剩下的差用兩個(gè)完全平方數(shù)不能組合出來就不繼續(xù)for(intk=0k*k=nk++){inttemp=ni*ij*jk*k。doublel=sqrt((double)temp)。if(l==(int)l){printf(%d%d%d%d\n,i,j,k,(int)l)。flag=true。break。}}if(flag)break。}if(flag)break。}return0。}（9）交換瓶子有N個(gè)瓶子，編號(hào) 1 ~ N，放在架子上。比如有5個(gè)瓶子：2 1 3 5 4要求每次拿起2個(gè)瓶子，交換它們的位置。經(jīng)過若干次后，使得瓶子的序號(hào)為：1 2 3 4 5對(duì)于這么簡(jiǎn)單的情況，顯然，至少需要交換2次就可以復(fù)位。如果瓶子更多呢？你可以通過編程來解決。輸入格式為兩行：第一行: 一個(gè)正整數(shù)N（N10000）, 表示瓶子的數(shù)目第二行：N個(gè)正整數(shù)，用空格分開，表示瓶子目前的排列情況。輸出數(shù)據(jù)為一行一個(gè)正整數(shù)，表示至少交換多少次，才能完成排序。例如，輸入：53 1 2 5 4程序應(yīng)該輸出：3再例如，輸入：55 4 3 2 1程序應(yīng)該輸出：2題解：這道題目就是典型的貪心題了。從最左邊的那個(gè)下標(biāo)開始，往右邊找最小的數(shù)字。然后從次左邊的那個(gè)下標(biāo)開始，找剩余右邊的最小的數(shù)字然后交換。這樣的復(fù)雜度是O(n*n)。會(huì)超時(shí)。因?yàn)檫@個(gè)題目的編號(hào)是1~n；所以可以用兩個(gè)數(shù)組，一個(gè)存輸入的數(shù)組，一個(gè)標(biāo)識(shí)該數(shù)應(yīng)該是在第幾個(gè)位置。然后直接一個(gè)循環(huán)，include cmathinclude iostreamusing namespace std。const int maxn=1e5+10。int main(){ int num[maxn],bb[maxn]。 int n,sum=0。 cinn。 for(int i=1。i=n。++i) { cinnum[i]。 bb[num[i]]=i。 } for(int i=1。i=n。++i) { if(num[i]==i) continue。 else if(num[i]!=i) { if(i==num[num[i]]) swap(num[i],num[num[i]]),++sum。 else sum+=2。 } } coutsum。 return 0。}//這個(gè)代碼可能還有點(diǎn)BU
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1