Noip 2013 提高组解题报告--By GreenCloudSDay 1:第一题：转圈游戏（快速幂）根据题目，答案明显是(x+10^km) mod n，化简一下，就成了(x + m (10^k mod n) modn) mod n,所以，只需要求出10^k mod n 即可，可以使用快速幂来求解,复杂度O(logk)。（另一个算法，设 f(i)=10^i mod n,则 f(i)=f(i-1)*10 mod n,然后求出f(i)的循环节，复杂度O(n)）代码(C++)：#include
#include 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(y&1){return(((Exp(y>>1)*Exp(y>>1))%n)*10)%n;}else return(Exp(y>>1)*Exp(y>>1))%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-2∑aibi 要求∑(ai-bi)^2 最小，就只需要∑aibi 最大即可。这里有个贪心，当 a1b,c>d,且 ac+bdb 矛盾，所以若a>b,c>d，则 ac+bd>ad+bc将此式子进行推广：当 a1#include#includeusing namespace std;#define MAXN 100010#define lowbit(x)(((~(x))+1)&x)#define MAX 99999997struct saver{int v,t;};saver a[MAXN],b[MAXN];bool cmp(saver x,save...
