Noip 2013 提高组 解题报告

Noip2013提高组解题报告

--ByGreenCloudS

Day1:

第一题：转圈游戏（快速幂）

根据题目，答案明显是(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#includeintk;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(\,&n,&m,&k,&x);ans=Exp(k);ans*=m;ans%=n;ans+=x;ans%=n;printf(\,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

然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，那么，我们就保持一个序列不动，然后根据另外那个序列中的数对应的数的位置，重新定义一个数组，求逆序对个数，就是答案。例如：对于数据：42314

3214先排序: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#includeusingnamespacestd;#defineMAXN100010#definelowbit(x)(((~(x))+1)&x)#defineMAX99999997structsaver{intv,t;};savera[MAXN],b[MAXN];boolcmp(saverx,savery){returnx.v