Noip2013題解-顧霆楓

1、Noip2013題解By GTFDay 1Circle考試當(dāng)天早上大腦出現(xiàn)了神一樣的變異，居然抽風(fēng)地拿著手機(jī)去看快速冪?？荚囋谑煜きh(huán)境時(shí)把它打了下來(lái)，題目一發(fā)下來(lái)我和我的小伙伴都驚呆了！第一題居然是快速冪！【問(wèn)題描述】 n 個(gè)小伙伴（編號(hào)從 0 到 n-1）圍坐一圈玩游戲。按照順時(shí)針?lè)较蚪o n 個(gè)位置編號(hào)，從0 到 n-1。最初，第 0 號(hào)小伙伴在第 0 號(hào)位置，第 1 號(hào)小伙伴在第 1 號(hào)位置，依此類推。 游戲規(guī)則如下：每一輪第 0 號(hào)位置上的小伙伴順時(shí)針走到第 m 號(hào)位置，第 1 號(hào)位置小伙伴走到第m+1號(hào)位置，依此類推，第n m號(hào)位置上的小伙伴走到第 0 號(hào)位置，第n-m+1 號(hào)位置上的

2、小伙伴走到第 1 號(hào)位置，第 n-1 號(hào)位置上的小伙伴順時(shí)針走到第m-1號(hào)位置。 現(xiàn)在，一共進(jìn)行了 10k輪，請(qǐng)問(wèn)x號(hào)小伙伴最后走到了第幾號(hào)位置。 【輸入】 輸入文件名為circle.in。 輸入共1行，包含 4個(gè)整數(shù)n、m、k、x，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。 【輸出】 輸出文件名為circle.out。 輸出共1行，包含 1個(gè)整數(shù)，表示10k輪后 x號(hào)小伙伴所在的位置編號(hào)。 【輸入輸出樣例】 circle.incircle.out10 3 4 5 5 【數(shù)據(jù)說(shuō)明】 對(duì)于30%的數(shù)據(jù)，0 < k < 7； 對(duì)于80%的數(shù)據(jù)，0 < k < 107； 對(duì)于100%的數(shù)

3、據(jù)，1 < n < 1,000,000，0 < m <n，1 x n，0 < k < 109?！绢}解】不難發(fā)現(xiàn)答案就是m+10kmod nO(log2k)的算法。因?yàn)?k109，算下來(lái)只有30！程序在下：#include <iostream>#include <cstdio>#include <cmath>#define LL long long#ifdef WIN32#define OTL "%I64d"#else#define OTL "%lld"#endifusing name

4、space std;LL n,m,k,x,ans;LL qm(LL a,LL b,LL m)LL r=1;LL bit=a;while (b!=0) if (b & 1 =1) r=r*bit%m;bit=bit*bit%m;b=b>>1;return r;int main()freopen("circle.in","r",stdin);freopen("circle.out","w",stdout);scanf(OTL OTL OTL OTL,&n,&m,&k,&

5、;x);ans=qm(10,k,n);ans=(m*ans)%n+x)%n;printf(OTL,ans);return 0;Match神奇地爆0了（其實(shí)也不神奇），后來(lái)才做出來(lái)?！締?wèn)題描述】 涵涵有兩盒火柴，每盒裝有n根火柴，每根火柴都有一個(gè)高度?，F(xiàn)在將每盒中的火柴各自排成一列，同一列火柴的高度互不相同，兩列火柴之間的距離定義為：i=1nai-bi2 ，其中ai表示第一列火柴中第i個(gè)火柴的高度，bi表示第二列火柴中第 i個(gè)火柴的高度。每列火柴中相鄰兩根火柴的位置都可以交換，請(qǐng)你通過(guò)交換使得兩列火柴之間的距離最小。請(qǐng)問(wèn)得到這個(gè)最小的距離，最少需要交換多少次？如果這個(gè)數(shù)字太大，請(qǐng)輸出這個(gè)最小交換

6、次數(shù)對(duì)99,999,997取模的結(jié)果。 【輸入】 輸入文件為match.in。 共三行，第一行包含一個(gè)整數(shù) n，表示每盒中火柴的數(shù)目。 第二行有n個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，表示第一列火柴的高度。 第三行有n個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，表示第二列火柴的高度。 【輸出】 輸出文件為match.out。 輸出共一行，包含一個(gè)整數(shù)，表示最少交換次數(shù)對(duì)99,999,997取模的結(jié)果。 【輸入輸出樣例1】 match.inmatch.out42 3 1 43 2 1 41【輸入輸出樣例說(shuō)明】最小距離是 0，最少需要交換 1 次，比如：交換第 1 列的前 2 根火柴或者交換第 2 列的

7、前 2 根火柴?！据斎胼敵鰳永?】match.inmatch.out41 3 4 21 7 2 42【輸入輸出樣例說(shuō)明】 最小距離是 10，最少需要交換 2 次，比如：交換第 1 列的中間 2 根火柴的位置，再交換第2列中后2根火柴的位置。 【數(shù)據(jù)范圍】 對(duì)于10%的數(shù)據(jù)， 1 n 10； 對(duì)于30%的數(shù)據(jù)，1 n 100； 對(duì)于60%的數(shù)據(jù)，1 n 1,000； 對(duì)于100%的數(shù)據(jù)，1 n 100,000，0 火柴高度 231 1?！绢}解】對(duì)距離公式化簡(jiǎn)得：(ai-bi)2=(ai2-2aibi+bi2)=ai2+bi2-2aibi要求(ai-bi)2最小，就只需要aibi最大即可。這里有個(gè)

8、貪心，當(dāng)a1<a2<<an，b1<b2<<bn時(shí)，aibi最大。證明如下：若存在a>b,c>d,且ac+bd<ad+bc，則a(c-d)<b(c-d),則a<b，與a>b矛盾，所以若a>b,c>d，則ac+bd>ad+bc將此式子進(jìn)行推廣：當(dāng)a1<a2<a3<.<an ,b1<b2<.<bn的情況下aibi最大，即(ai-bi) 2最小。然后，將兩個(gè)序列分別排序，確定每對(duì)數(shù)的對(duì)應(yīng)關(guān)系，明顯，同時(shí)移動(dòng)兩個(gè)序列中的數(shù)等效于只移動(dòng)一個(gè)序列中的數(shù)，那么，我們就保持一個(gè)序列

9、不動(dòng)，然后根據(jù)另外那個(gè)序列中的數(shù)對(duì)應(yīng)的數(shù)的位置，重新定義一個(gè)數(shù)組，求逆序?qū)€(gè)數(shù)，就是答案。求逆序?qū)Ψ椒ǎ?. 歸并排序2. 把數(shù)組掃一遍，順序把每個(gè)數(shù)加入BIT或者是線段樹(shù)等數(shù)據(jù)結(jié)構(gòu)中，同時(shí)查詢比這個(gè)數(shù)大的數(shù)有幾個(gè)，加入答案。復(fù)雜度 : O(nlog2n)Code：#include<cstdio>#include<algorithm>#include<cstring>using namespace std; #define MAXN 100010#define lowbit(x)(x)+1)&x)#define MAX 99999997&#

10、160;struct saver    int v,t;saver aMAXN,bMAXN; bool cmp(saver x,saver y)    return x.v<y.v; int n,rMAXN,ans=0;int tMAXN; void Add(int x)for(int i=x;i<=n;i+=lowbit(i) ti+;int Sum(int x)    int rec=0;    for(;x;x-=lowbit(

11、x) rec+=tx;    return rec; int main()    scanf("%d",&n);    for(int i=0;i+<n;) scanf("%d",&ai.v),ai.t=i;    for(int i=0;i+<n;) scanf("%d",&bi.v),bi.t=i;    sort(a+1,a+n+1,c

12、mp),sort(b+1,b+n+1,cmp);    for(int i=0;i+<n;) rai.t=bi.t;    for(int i=n;i;i-) ans+=Sum(ri),Add(ri),ans%=MAX;    printf("%dn",ans);    return 0;Truck這道題跟Running有相同之處，我居然沒(méi)有看出來(lái)。話說(shuō)倍增還沒(méi)弄明白，最大生成樹(shù)也僅僅是會(huì)打?？磥?lái)得惡補(bǔ)一下了?！締?wèn)題描述】 A 國(guó)有n座城市，編號(hào)從1

13、到n，城市之間有 m條雙向道路。每一條道路對(duì)車輛都有重量限制，簡(jiǎn)稱限重?，F(xiàn)在有 q輛貨車在運(yùn)輸貨物，司機(jī)們想知道每輛車在不超過(guò)車輛限重的情況下，最多能運(yùn)多重的貨物。 【輸入】 輸入文件名為truck.in。 輸入文件第一行有兩個(gè)用一個(gè)空格隔開(kāi)的整數(shù) n，m，表示 A 國(guó)有 n 座城市和 m 條道路。 接下來(lái)m行每行3個(gè)整數(shù)x、y、z，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，表示從x 號(hào)城市到y(tǒng)號(hào)城市有一條限重為z的道路。注意：x不等于y，兩座城市之間可能有多條道路。 接下來(lái)一行有一個(gè)整數(shù) q，表示有q輛貨車需要運(yùn)貨。 接下來(lái) q 行，每行兩個(gè)整數(shù) x、y，之間用一個(gè)空格隔開(kāi)，表示一輛貨車需要從 x 城市

14、運(yùn)輸貨物到y(tǒng)城市，注意：x不等于y。 【輸出】 輸出文件名為truck.out。 輸出共有 q 行，每行一個(gè)整數(shù)，表示對(duì)于每一輛貨車，它的最大載重是多少。如果貨車不能到達(dá)目的地，輸出-1。 【輸入輸出樣例】 ruck.out4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3 3 -1 3 【數(shù)據(jù)說(shuō)明】 對(duì)于30%的數(shù)據(jù)，0 <n < 1,000，0 < m < 10,000，0 < q < 1,000； 對(duì)于60%的數(shù)據(jù)，0 < n < 1,000，0 < m < 50,000，0 < q&

15、lt; 1,000； 對(duì)于100%的數(shù)據(jù)， 0 < n < 10,000，0 < m < 50,000，0 < q< 30,000， 0 z 100,000?！绢}解】首先，我們可以確定貪心的正確性，我們先把邊按權(quán)值從大到小排序，然后依次加入圖中，如果該邊的起末點(diǎn)不在同一連通塊中，那么就把邊加入，否則不加處理，很明顯，這樣生成的圖，兩點(diǎn)之間要么沒(méi)有路徑，要么唯一一條路徑中權(quán)值的最小值最大。所以，我們只要先跑一次最大生成樹(shù)，然后在求點(diǎn)對(duì)之間的樹(shù)上路徑最小值就可以了。#include <cstdio>#include <algorithm>

16、#include <cstring> using namespace std; #define maxn 10010#define maxm 50010#define maxq 30010#define maxd 20#define clear(x) memset(x,0,sizeof(x)#define addedge(s,t,d) add(s,t,d),add(t,s,d)#define inf 0x7fffffff struct saver int s,t,d; eMAXM; bool cmp(saver x,saver y) return x.d>y.d; int f

17、atherMAXN,n,m,q,QMAXQ2; int Find(int x) int i,j=x; for (i=x;fatheri;i=fatheri) ; while (fatherj) int k=fatherj; fatherj=i; j=k; return i;int upMAXNMAXD,MinMAXNMAXD,hMAXN;bool fMAXN; struct edge edge *next; int t,d; edge () next=NULL; *headMAXN; void Add(int s,int t,int d) edge *p=new(edge); p->t=

18、t,p->d=d,p->next=heads; heads=p; void BuildTree(int v) fv=false; for (edge *p=headv;p;p=p->next) if (fp->t) upp->t0=v,Minp->t0=p->d,hp->t=hv+1; BuildTree(p->t); int Move(int &v,int H) int rec=inf; for (int i=MAXD-1;i>=0;i-) if (hupvi>=H) rec=min(rec,Minvi); v=upv

19、i; return rec; int Query(int u,int v) if (Find(u)!=Find(v) return -1; int rec=inf; if (hu!=hv) rec=hu>hv?Move(u,hv):Move(v,hu); if (u=v) return rec; for (int i=MAXD-1;i>=0;i-) if (upui!=upvi) rec=min(rec,min(Minui,Minvi); u=upui,v=upvi; rec=min(rec,min(Minu0,Minv0); return rec;int main()  

20、;   clear(father),clear(head),clear(up);    scanf("%d%d",&n,&m);    for (int i=0;i<m;i+) scanf("%d%d%d",&ei.s,&ei.t,&ei.d);    sort(e,e+m,cmp);    for (int i=0;i<m;i+) if (Find(ei.s)!=

21、Find(ei.t)         fatherFind(ei.s)=Find(ei.t);        AddEdge(ei.s,ei.t,ei.d);        memset(f,true,sizeof(f);for (int i=0;i+<n;)if (fi)hi=0,BuildTree(i),Mini0=inf,upi0=i;    for (i

22、nt i=0;i+<MAXD-1;)         for (int j=0;j+<n;)             upji=upupji-1i-1;            Minji=min(Minji-1,Minupji-1i-1);     

23、;          scanf("%d",&q);    while (q-)         int u,v;        scanf("%d%d",&u,&v);        printf("%d

24、n",Query(u,v);        return 0;Day 2Block十分鐘解決的題?！締?wèn)題描述】 春春幼兒園舉辦了一年一度的“積木大賽”。今年比賽的內(nèi)容是搭建一座寬度為n的大廈，大廈可以看成由n塊寬度為1的積木組成，第i塊積木的最終高度需要是hi。在搭建開(kāi)始之前，沒(méi)有任何積木（可以看成n塊高度為 0 的積木）。接下來(lái)每次操作，小朋友們可以選擇一段連續(xù)區(qū)間L,R，然后將第L塊到第R塊之間（含第 L 塊和第 R 塊）所有積木的高度分別增加1。小M是個(gè)聰明的小朋友，她很快想出了建造大廈的最佳策略，使得建造所需的操作次

25、數(shù)最少。但她不是一個(gè)勤于動(dòng)手的孩子，所以想請(qǐng)你幫忙實(shí)現(xiàn)這個(gè)策略，并求出最少的操作次數(shù)。 【輸入】 輸入文件為block.in輸入包含兩行，第一行包含一個(gè)整數(shù)n，表示大廈的寬度。第二行包含n個(gè)整數(shù)，第i個(gè)整數(shù)為hi 。 【輸出】 輸出文件為block.out僅一行，即建造所需的最少操作數(shù)?！据斎胼敵鰳永?block.inblock.out52 3 4 1 25 【樣例解釋】其中一種可行的最佳方案，依次選擇1,5 1,3 2,3 3,3 5,5【數(shù)據(jù)說(shuō)明】 對(duì)于 30%的數(shù)據(jù)，有1 n 10；對(duì)于 70%的數(shù)據(jù)，有1 n 1000；對(duì)于 100%的數(shù)據(jù)，有1 n 100000，0 hi 1000

26、0?！绢}解】分治：找到min(hi)，答案加上它，全體減去它，再在左邊和右邊重復(fù)這么做。#include <iostream>#include <cstdio>#include <cmath>#define LL long long#ifdef WIN32#define OTL "%I64d"#else#define OTL "%lld"#endifLL n,h100050,ans;LL block(int l, int r) if (l=r) return hl; int i,j,k; LL result=0; k=

27、l; for (i=l+1;i<=r;i+) if (hi<hk) k=i; result+=hk; for (i=l;i<=r;i+) hi-=result; if (k-1>=l) result+=block(l,k-1); if (k+1<=r) result+=block(k+1,r); return result;int main() freopen("block.in","r",stdin); freopen("block.out","w",stdout); scanf(O

28、TL,&n); int i; for (i=1;i<=n;i+) scanf(OTL,&hi); ans=block(1,n); printf(OTL,ans); return 0;詳見(jiàn)Code：Flower考場(chǎng)上想得太復(fù)雜了。DP怎么樣都超時(shí)【問(wèn)題描述】 花匠棟棟（我很想吐槽）種了一排花，每株花都有自己的高度?；▋涸介L(zhǎng)越大，也越來(lái)越擠。棟棟決定把這排中的一部分花移走，將剩下的留在原地，使得剩下的花能有空間長(zhǎng)大，同時(shí)，棟棟希望剩下的花排列得比較別致。具體而言，棟棟的花的高度可以看成一列整數(shù)g1, g2, , gn。設(shè)當(dāng)一部分花被移走后，剩下的花的高度依次為g1, g2,

29、, gn，則棟棟希望下面兩個(gè)條件中至少有一個(gè)滿足：條件 A：對(duì)于所有的i，g2i> g2i1，且g2i> g2i+1；條件 B：對(duì)于所有的i，g2i< g2i1，且g2i< g2i+1。注意上面兩個(gè)條件在n = 1時(shí)同時(shí)滿足，當(dāng)n > 1時(shí)最多有一個(gè)能滿足。請(qǐng)問(wèn)，棟棟最多能將多少株花留在原地?！据斎搿?輸入文件為 flower .in。輸入的第一行包含一個(gè)整數(shù)n，表示開(kāi)始時(shí)花的株數(shù)。第二行包含n個(gè)整數(shù)，依次為h1, h2, , hn，表示每株花的高度?！据敵觥?輸出文件為 flower .out。輸出一行，包含一個(gè)整數(shù)n，表示最多能留在原地的花的株數(shù)?！据斎胼敵鰳?/p>

30、例】 block.inblock.out55 3 2 1 23 【輸入輸出樣例說(shuō)明】有多種方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分別為 5、1、2，滿足條件 B?！緮?shù)據(jù)說(shuō)明】 對(duì)于 20%的數(shù)據(jù)，n 10；對(duì)于 30%的數(shù)據(jù)，n 25；對(duì)于 70%的數(shù)據(jù)，n 1000，0 hi 1000；對(duì)于 100%的數(shù)據(jù)，1 n 100,000，0 hi 1,000,000，所有的hi 隨機(jī)生成，所有隨機(jī)數(shù)服從某區(qū)間內(nèi)的均勻分布。【題解】有一種神奇的方法叫找拐點(diǎn)：從h2掃到hn-1，如果它不是拐點(diǎn)就刪去它，計(jì)數(shù)器減一。貌似這個(gè)方法小學(xué)上信息培訓(xùn)班時(shí)就講過(guò)，沒(méi)看出來(lái)真可惜，如果加了這

31、100分就一等獎(jiǎng)了。O(n)搞定。#include <iostream>#include <cstdio>#include <cmath>#define LL long long#ifdef WIN32#define OTL "%I64d"#else#define OTL "%lld"#endifusing namespace std;LL N;LL V100050,Left100050,Right100050;void init()scanf(OTL,&N);for(int i=1;i<=N;i+)sc

32、anf(OTL,&Vi);Lefti=i-1;Righti=i+1;void solve()LL ans=N;for(int i=2;i<N;i+)if(VLefti>=Vi&&Vi>=VRighti)|(VLefti<=Vi&&Vi<=VRighti)ans-;RightLefti=Righti;LeftRighti=Lefti;printf(OTL,ans);int main()init();solve();return 0;Puzzle很明顯，這樣的題目是不可能在考場(chǎng)上AC的?！締?wèn)題描述】 小 B 最近迷上了華容道，可

33、是他總是要花很長(zhǎng)的時(shí)間才能完成一次。于是，他想到用編程來(lái)完成華容道：給定一種局面， 華容道是否根本就無(wú)法完成，如果能完成， 最少需要多少時(shí)間。小 B 玩的華容道與經(jīng)典的華容道游戲略有不同，游戲規(guī)則是這樣的：1. 在一個(gè) n*m 棋盤上有 n*m 個(gè)格子，其中有且只有一個(gè)格子是空白的，其余 n*m-1個(gè)格子上每個(gè)格子上有一個(gè)棋子，每個(gè)棋子的大小都是 1*1 的；2. 有些棋子是固定的，有些棋子則是可以移動(dòng)的；3. 任何與空白的格子相鄰（有公共的邊）的格子上的棋子都可以移動(dòng)到空白格子上。游戲的目的是把某個(gè)指定位置可以活動(dòng)的棋子移動(dòng)到目標(biāo)位置。給定一個(gè)棋盤，游戲可以玩 q 次，當(dāng)然，每次棋盤上固定的

34、格子是不會(huì)變的， 但是棋盤上空白的格子的初始位置、 指定的可移動(dòng)的棋子的初始位置和目標(biāo)位置卻可能不同。第 i 次玩的時(shí)候， 空白的格子在第 EXi 行第 EYi 列，指定的可移動(dòng)棋子的初始位置為第 SXi 行第 SYi列，目標(biāo)位置為第 TXi 行第 TYi 列。假設(shè)小 B 每秒鐘能進(jìn)行一次移動(dòng)棋子的操作，而其他操作的時(shí)間都可以忽略不計(jì)。請(qǐng)你告訴小 B 每一次游戲所需要的最少時(shí)間，或者告訴他不可能完成游戲?！据斎搿?輸入文件為 puzzle.in。第一行有 3 個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，依次表示 n、m 和 q；接下來(lái)的 n 行描述一個(gè) n*m 的棋盤，每行有 m 個(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，每個(gè)整數(shù)描述棋盤上一個(gè)格子的狀態(tài)，0 表示該格子上的棋子是固定的，1 表示該格子上的棋子可以移動(dòng)或者該格子是空白的。接下來(lái)的 q 行，每行包含 6 個(gè)整數(shù)依次是 EXi、EYi、SXi、SYi、TXi、TYi，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，表示每次游戲空白格子的位置，指定棋子的初始位置和目標(biāo)位置?！据敵觥?輸出文件名為 puzzle.out。輸出有 q 行，每行包含 1 個(gè)整數(shù)，表示每次游戲所需要的最少時(shí)間，如果某次游戲無(wú)法完成目標(biāo)