Noip 2013 提高组 解题报告.pdf

Noip2013 提高组 解题报告 --ByGreenCloudS Day1: 第一题：转圈游戏 （快速幂） 根据题目，答案明显是(x+10^km)modn，化简一下，就成了(x+m(10^kmodn)mod n)modn,所以，只需要求出10^kmodn 即 ，可以使用快速幂来求解复杂度, O(log k) f(i)=10^imodn, f(i)=f(i-1)*10modn, f(i) 。（另一个算法，设 则 然后求出 的循环节， 复杂度O(n)） 代码(C++)： #include cstdio #include cstring int k; long long ans; int n,m,x; long long Exp(int y){ if(!y)return 1; if(y==1)return 10%n; if(y1){ return(((Exp(y1)*Exp(y1))%n)*10)%n; }else return(Exp(y1)*Exp(y1))%n; } int main(){ scanf(%d%d%d%d,n,m,k,x); ans=Exp(k); ans*=m; ans%=n; ans+=x; ans%=n; printf(%lld,ans); return 0; } 第二题：火柴排队 （贪心+逆序对） 对距离公式化简得： (ai-bi)^2= (ai^2-2aibi+bi^2)= ai^2+ bi^2- aibi (ai-bi)^ ∑ ∑ ∑ ∑ ∑ 要求∑ 最小，就只 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)^ 当 的情况下∑ 最大，即∑ 最小。 然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列 中的数等效于只移动一个序列中的数，那么，我们就保持一个序列不动，然后根 据另外那个序列中的数对应的数的位置，重新定义一个数组，求逆序对个数，就 是答案。 例如： 对于数据： 4 314 3 14 先排序: 1 34 1 34 1 3 1 1 保持序列 不动，那么序列 中的 就对应序列 中的 位置， 就对应序列 1 1 1 3 4 1 4 中的 位置， 就对应序列 中的 位置， 就对应序列 中的 位置，那么重定 义数组为： 134 这个序列的逆序对为(2,1),所以答案是 。1 求逆序对方法： 1. 归并排序 2. 把数组扫一遍，顺序把每个数加入BIT或者是线段树等数据结构中，同 时查询比这个数大的数有几个，加入答案。 复杂度 :O(nlogn) C++ 代码（ ）（树状数组）