歷年藍橋杯省賽b組真題試題-資料下載頁
2025-03-24 23:24本頁面
【正文】 =1表示i能夠用兩個完全平方數(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。//如果剩下的差用兩個完全平方數(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個瓶子，編號 1 ~ N，放在架子上。比如有5個瓶子：2 1 3 5 4要求每次拿起2個瓶子，交換它們的位置。經(jīng)過若干次后，使得瓶子的序號為：1 2 3 4 5對于這么簡單的情況，顯然，至少需要交換2次就可以復位。如果瓶子更多呢？你可以通過編程來解決。輸入格式為兩行：第一行: 一個正整數(shù)N（N10000）, 表示瓶子的數(shù)目第二行：N個正整數(shù)，用空格分開，表示瓶子目前的排列情況。輸出數(shù)據(jù)為一行一個正整數(shù)，表示至少交換多少次，才能完成排序。例如，輸入：53 1 2 5 4程序應該輸出：3再例如，輸入：55 4 3 2 1程序應該輸出：2題解：這道題目就是典型的貪心題了。從最左邊的那個下標開始，往右邊找最小的數(shù)字。然后從次左邊的那個下標開始，找剩余右邊的最小的數(shù)字然后交換。這樣的復雜度是O(n*n)。會超時。因為這個題目的編號是1~n；所以可以用兩個數(shù)組，一個存輸入的數(shù)組，一個標識該數(shù)應該是在第幾個位置。然后直接一個循環(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。}//這個代碼可能還有點BU
電大資料相關推薦
鄂ICP備17016276號-1