Noip 2013 提高组 解题报告
- 格式：pdf
- 大小：217.35 KB
- 文档页数：21
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++)：#include#include
intk;longlongans;intn,m,x;
longlongExp(inty){if(!y)return1;if(y==1)return10%n;if(y&1){return(((Exp(y>>1)*Exp(y>>1))%n)*10)%n;}elsereturn(Exp(y>>1)*Exp(y>>1))%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最大即可。这里有个贪心，当a1大。证明如下：若存在a>b,c>d,且ac+bdb矛盾，所以若a>b,c>d，则ac+bd>ad+bc将此式子进行推广：当a1
然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，那么，我们就保持一个序列不动，然后根据另外那个序列中的数对应的数的位置，重新定义一个数组，求逆序对个数，就是答案。例如：对于数据：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++）（树状数组）：#include#include#include
usingnamespacestd;#defineMAXN100010#definelowbit(x)(((~(x))+1)&x)#defineMAX99999997structsaver{intv,t;};savera[MAXN],b[MAXN];
boolcmp(saverx,savery){returnx.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++for(inti=0;i++sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);for(inti=0;i++for(inti=n;i;i--)ans+=Sum(r[i]),Add(r[i]),ans%=MAX;printf("%d\n",ans);return0;}
第三题：货车运输（贪心+最大生成树+树上路径倍增）首先，我们可以确定贪心的正确性，我们先把边按权值从大到小排序，然后依次加入图中，如果该边的起末点不在同一连通块中，那么就把边加入，否则不加处理，很明显，这样生成的图，两点之间要么没有路径，要么唯一一条路径中权值的最小值最大。所以，我们只要先跑一次最大生成树，然后在求点对之间的树上路径最小值就可以了。
复杂度：O(mlogm+qlogn)代码（C++）（MST+树上倍增）：#include#include#include
usingnamespacestd;#defineMAXN10010#defineMAXM50010#defineMAXQ30010#defineMAXD20#defineclear(x)memset(x,0,sizeof(x))#defineAddEdge(s,t,d)Add(s,t,d),Add(t,s,d)#defineinf0x7fffffff
structsaver{ints,t,d;}e[MAXM];
boolcmp(saverx,savery){returnx.d>y.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;isort(e,e+m,cmp);for(inti=0;ifather[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++for(inti=0;i++for(intj=0;j++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;}
