Noip-2013-提高组-解题报告

Noip2013提高组解题报告--ByGreenCloudSDay1:第一题：转圈游戏（快速幂）根据题目，答案明显是(x+10^km)modn，化简一下，就成了(x+m(10^kmodn)modn)modn,所以，只需要求出10^kmodn即可，可以使用快速幂来求解,复杂度O(logk)。（另一个算法，设f(i)=10^imodn,则f(i)=f(i-1)*10modn,然后求出f(i)的循环节，复杂度O(n)）代码(C++)：#includecstdio#includecstringintk;longlongans;intn,m,x;longlongExp(inty){if(!y)return1;if(y==1)return10%n;if(y&1){return(((Exp(y1)*Exp(y1))%n)*10)%n;}elsereturn(Exp(y1)*Exp(y1))%n;}intmain(){scanf(%d%d%d%d,&n,&m,&k,&x);ans=Exp(k);ans*=m;ans%=n;ans+=x;ans%=n;printf(%lld,ans);return0;}第二题：火柴排队（贪心+逆序对）对距离公式化简得：∑(ai-bi)^2=∑(ai^2-2aibi+bi^2)=∑ai^2+∑bi^2-2∑aibi要求∑(ai-bi)^2最小，就只需要∑aibi最大即可。这里有个贪心，当a1a2…an,b1b2..bn时，∑aibi最大。证明如下：若存在ab,cd,且ac+bdad+bc，则a(c-d)b(c-d),则ab，与ab矛盾，所以若ab,cd，则ac+bdad+bc将此式子进行推广：当a1a2a3...an,b1b2...bn的情况下∑aibi最大，即∑(ai-bi)^2最小。然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，那么，我们就保持一个序列不动，然后根据另外那个序列中的数对应的数的位置，重新定义一个数组，求逆序对个数，就是答案。例如：对于数据：423143214先排序:12341234保持序列1不动，那么序列2中的3就对应序列1中的2位置，2就对应序列1中的1位置，1就对应序列1中的3位置，4就对应序列1中的4位置，那么重定义数组为：2134这个序列的逆序对为(2,1),所以答案是1。求逆序对方法：1.归并排序2.把数组扫一遍，顺序把每个数加入BIT或者是线段树等数据结构中，同时查询比这个数大的数有几个，加入答案。复杂度:O(nlogn)代码（C++）（树状数组）：#includecstdio#includealgorithm#includecstringusingnamespacestd;#defineMAXN100010#definelowbit(x)(((~(x))+1)&x)#defineMAX99999997structsaver{intv,t;};savera[MAXN],b[MAXN];boolcmp(saverx,savery){returnx.vy.v;}intn,r[MAXN],ans=0;intt[MAXN];voidAdd(intx){for(inti=x;i=n;i+=lowbit(i))t[i]++;}intSum(intx){intrec=0;for(;x;x-=lowbit(x))rec+=t[x];returnrec;}intmain(){scanf(%d,&n);for(inti=0;i++n;)scanf(%d,&a[i].v),a[i].t=i;for(inti=0;i++n;)scanf(%d,&b[i].v),b[i].t=i;sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);for(inti=0;i++n;)r[a[i].t]=b[i].t;for(inti=n;i;i--)ans+=Sum(r[i]),Add(r[i]),ans%=MAX;printf(%d\n,ans);return0;}第三题：货车运输（贪心+最大生成树+树上路径倍增）首先，我们可以确定贪心的正确性，我们先把边按权值从大到小排序，然后依次加入图中，如果该边的起末点不在同一连通块中，那么就把边加入，否则不加处理，很明显，这样生成的图，两点之间要么没有路径，要么唯一一条路径中权值的最小值最大。所以，我们只要先跑一次最大生成树，然后在求点对之间的树上路径最小值就可以了。复杂度：O(mlogm+qlogn)代码（C++）（MST+树上倍增）：#includecstdio#includealgorithm#includecstringusingnamespacestd;#defineMAXN10010#defineMAXM50010#defineMAXQ30010#defineMAXD20#defineclear(x)memset(x,0,sizeof(x))#defineAddEdge(s,t,d)Add(s,t,d),Add(t,s,d)#defineinf0x7fffffffstructsaver{ints,t,d;}e[MAXM];boolcmp(saverx,savery){returnx.dy.d;}intfather[MAXN],n,m,q,Q[MAXQ][2];intFind(intx){inti,j=x;for(i=x;father[i];i=father[i]);while(father[j]){intk=father[j];father[j]=i;j=k;}returni;}intup[MAXN][MAXD],Min[MAXN][MAXD],h[MAXN];boolf[MAXN];structedge{edge*next;intt,d;edge(){next=NULL;}}*head[MAXN];voidAdd(ints,intt,intd){edge*p=new(edge);p-t=t,p-d=d,p-next=head[s];head[s]=p;}voidBuildTree(intv){f[v]=false;for(edge*p=head[v];p;p=p-next)if(f[p-t]){up[p-t][0]=v,Min[p-t][0]=p-d,h[p-t]=h[v]+1;BuildTree(p-t);}}intMove(int&v,intH){intrec=inf;for(inti=MAXD-1;i=0;i--){if(h[up[v][i]]=H){rec=min(rec,Min[v][i]);v=up[v][i];}}returnrec;}intQuery(intu,intv){if(Find(u)!=Find(v))return-1;intrec=inf;if(h[u]!=h[v])rec=h[u]h[v]?Move(u,h[v]):Move(v,h[u]);//printf(%d\n,rec);if(u==v)returnrec;for(inti=MAXD-1;i=0;i--){if(up[u][i]!=up[v][i]){rec=min(rec,min(Min[u][i],Min[v][i]));u=up[u][i],v=up[v][i];}}rec=min(rec,min(Min[u][0],Min[v][0]));returnrec;}intmain(){clear(father),clear(head),clear(up);scanf(%d%d,&n,&m);for(inti=0;im;i++)scanf(%d%d%d,&e[i].s,&e[i].t,&e[i].d);sort(e,e+m,cmp);for(inti=0;im;i++)if(Find(e[i].s)!=Find(e[i].t)){father[Find(e[i].s)]=Find(e[i].t);AddEdge(e[i].s,e[i].t,e[i].d);}memset(f,true,sizeof(f));for(inti=0;i++n;)if(f[i])h[i]=0,BuildTree(i),Min[i][0]=inf,up[i][0]=i;for(inti=0;i++MAXD-1;){for(intj=0;j++n;){up[j][i]=up[up[j][i-1]][i-1];Min[j][i]=min(Min[j][i-1],Min[up[j][i-1]][i-1]);}}scanf(%d,&q);while(q--){intu,v;scanf(%d%d,&u,&v);printf(%d\n,Query(u,v));}return0;}Day2:第一题：积木大赛（模拟）直接贪心，每次取最大一个连续区间，然后模拟即可。令h[0]=0,答案就是：∑h[i]-h[i-1](0i=n,h[i]h[i-1])复杂度:O(n)代码1(Cpp)：#includecstdio#defineMAXN100010inth[MAXN],ans=0,n;intmain(){h[0]=0;scanf(%d,&n);for(inti=0;i++n;){scanf(%d,&h[i]);if(h[i]h[i-1])ans+=h[i]-h[i-1];}printf(%d\n,ans);return0;}代码2（先对高度进行基数排序，然后逐行计算区间数，复杂度也是O(n)）(Cpp):#includeiostream#includecstringusingnamespacestd;#defineMAXH10010#defineMAXN100010structnode{node*next;intt;node(){next=NULL;}}*head[MAXH];intmaxh=0;voidInsert(inth,intt){maxh=max(maxh,h);node*p=new(node);p-t=t,p-next=head[h];head[h]=p;}intn,h,delta=1,ans=0;boolf[MAXN];intmain(){memset(f,true,sizeof(f)),memset(head,0,sizeof(head));cinn;f[0]=f[n+1]=false;for(inti=0;i++n;)cinh,Insert(h,i);for(inti=0;i=maxh;i++){if(i)ans+=delta;for(node*p=head[i];p;p=p-next){if(f[p-t-1]&&f[p-t+1])delta++;if((!f[p-t-1])&&(!f[p-t+1]))delta--;f[p-t]=false;}}coutansendl;return0;}第二题:花匠（动态规划）这道题明显可以用类似最长上升子序列的动态规划求解，易得思路如下：用f(i,0)表示以i为结尾的且最后一段上升的子序列最大长度，f(i,1)表示表示以i为结尾的且最后一段下降的子序列最大长度，那么答案明显就是max{f(i,0),f(i,1)}方程：f(i,0)=max{f(j,1)}+10=ji且h[j]h[i]f(i,1)=max{f(j,0)}+10=ji且h[j]h[i]边界：f(0,0)=f(0,1)=0如果直接DP毫无疑问复杂度是O(n^2)，会TLE，但是，考虑到我们每次取最值时候取得都是一个区间里的数，如f(i,0)=max{f(j,1)}+10=ji且h[j]h[i]取得就是区间[0,h[i]-1]里的最值，所以可以使用线段树或者是BIT（树状数组）来优化，这样复杂度就是