程序員進(jìn)階之算法練習(xí)(三十八)Codeforces

1、程序員進(jìn)階之算法練習(xí)（三十八）Codeforces正文AlexandaRhombus題目鏈接題目大意：給出一個整數(shù)n,下面給出當(dāng)n=1、2、3的圖:fl=1計算第n個圖，需要多少個方格組成。輸入：一個整數(shù)兇（1W兇W100）輸出：需要的方格數(shù)量。Examplesinput1output1input2output5input3output13題目解析：等差數(shù)列，1、3、5、2n-1;兩個等差數(shù)列，減去一個多余的2n-1,于是有:個等差數(shù)列和sum:(1+(2n-1)xn/2最終得到ans=2xsum-(2n-1)=2nA2-2n+1。intn;cinn;cout2*n*n-2*n+1endl;N

2、ickandArray題目鏈接題目大意：有一個數(shù)組=兇1,兇2,，可以對任意數(shù)進(jìn)行下面的操作:=一兇兇一1;每個數(shù)可以操作任意次；要求最后的乘積（1兇2）最大。輸入：第一行，（1冬兇冬10人5）第二行，n個整數(shù)；兇1,兇2,，兇（-10A6WW10A6）輸出：行，使得乘積最大的n個整數(shù)（兇1,兇2,兇）Examplesinput42222output-3-3-3-3input10output0題目解析：題目的要求是乘積最大，但是數(shù)字有很多，最終的乘積肯定會很大。再來看看題目的操作，其實就是x=-x-1;如果操作兩次呢？X=-（-x-1）-1=x+1-1=x;操作兩次是變回x，那么可以知道對于每

3、個數(shù)字只有1個選擇：要么不操作，要么操作一次?；仡^來看看乘積最大的要求，先不考慮正負(fù)的問題，要使得乘積最大，自然是每個數(shù)字越大越好。容易知道，乘積對于負(fù)數(shù)有一個負(fù)負(fù)得正的作用，那么要使得乘積最大要滿足兩個條件：1、所有的數(shù)字里不會出現(xiàn)單數(shù)的負(fù)數(shù)，否則結(jié)果一定是負(fù)數(shù)；2、每個數(shù)字要盡可能的大；分析這個操作x=-x-1,容易知道對于正數(shù)，當(dāng)X操作一次之后，絕對值是+1；對于負(fù)數(shù)，當(dāng)X操作一次之后，絕對值是-1;綜上，我們可以先將所有的數(shù)字全部變?yōu)樨?fù)數(shù)，這樣可以使得絕對值最大。但是因為可能會出現(xiàn)單數(shù)的負(fù)數(shù)，此時我們需要選擇一個負(fù)數(shù)變?yōu)檎麛?shù)，通過推導(dǎo)，我們會選擇負(fù)數(shù)中絕對值最大的那個變?yōu)樨?fù)數(shù)。推導(dǎo)：先

4、假設(shè)有兩個正整數(shù)x和y,并且xy。(x-1)y=xy-yx(y-1)=xy-x因為xy，所以有(x-1)yn;intindex=-1;for(inti=0;iai;if(ai=0)ai=-ai-1;if(index=-1)index=i;elseif(aiaindex)index=i;if(n%2)aindex=-aindex-1;for(inti=0;in;+i)coutai;ValeriyaandDeque題目鏈接題目大意：有一個數(shù)組a,長度為n;現(xiàn)在有一個操作，從數(shù)組最前面(a0,a1)拿出兩個數(shù)字假設(shè)是x,y;如果x=y,則把x放在數(shù)組的最前面，把y放在數(shù)組的最前面；問這個操作進(jìn)行若干

5、次之后，拿出來的數(shù)字x、y是什么；輸入：第一行，兩個整數(shù)兇and兇(2W兇冬10人5,0W兇W310人5),分別表示數(shù)組長度和詢問次數(shù);接下來有n個整數(shù)，兇1,兇2,兇兇，where兇兇(0W兇兇冬10人9)接下來有q行，每行一個整數(shù)兇兇,(1W兇兇W10T8)輸出：對于q個詢問，每個輸出一行，一行有兩個整數(shù)x、y;Examplesinput5323451210output122352樣例解釋：原始數(shù)組是1,2,3,4,5,在每次操作之前，數(shù)字的樣子：（每次操作都是拿出前兩個）1,2,3,4,52.3.4.5.13.4.5.1.24.5.1.2.35.1.2.3.45.2.3.4.15.3.4

6、.1.25.4.1.2.35.1.2.3.45,2,3,4,1題目解析：題目的樣例已經(jīng)很明顯闡述了一個規(guī)律：若干次之后，數(shù)組中最大值會始終占據(jù)第一位。根據(jù)題目的其他描述，每次拿出來的A、B兩個數(shù)字，在數(shù)組最大值放置在第一位之后，剩余的1n-1的位置會不斷輪換。為了實現(xiàn)簡單，我們不去記錄他最大值是什么。直接按照題目要求操作n次，記錄其中每次操作的值；此時數(shù)組的最大值就會在最左邊，接下來的操作會使得1n-1數(shù)組開始循環(huán)。對于q次詢問，每次先看詢問值mj是否小于n，是的話可以直接用原來存儲的值；否則就直接取余，再從1n-1找到下一個值。為了實現(xiàn)方便，這里n次的模擬可以使用雙端隊列deque來輔助實現(xiàn)

7、。lidn,t;cinnt;dequeq;for(inti=0;ik;q.push_back(k);for(inti=1;ib)q.pushront(a);q.push_back(b);elseq.pushront(b);q.push_back(a);for(inti=0;ik;if(kn)coutansk.firstansk.secondendl;else-k;k=k%(n-1);coutr0rk+1nm;for(inti=0;in;+i)vectort(m);a.push_back(t);“=0;bottomX=n-1,bottomY=m-1;topDir=1;bottomDir=-1;b

8、oolisBottom=0;while(ans.size()n*m)if(isBottom)/jumpbottomans.push_back(make_pair(bottomX,bottomY);bottomY+=bottomDir;if(bottomY=m)bottomY=m-1;bottomX-;bottomDir=-bottomDir;elseans.push_back(make_pair(topX,topY);topY+=topDir;if(topY=m)topY=m-1;topX+;topDir=-topDir;isBottom=!isBottom;for(inti=0;in*m;+i)printf(%d%dn,ansi.first+1,ansi