Noip2013提高组解题报告
--By GreenCloudS
Day1:
第一题：转圈游戏（快速幂）
根据题目，答案明显是(x+10^km)mod n，化简一下，就成了(x+m(10^k mod n)mod n)mod n，所以，只需要求出10^k mod n即可，可以使用快速幂来求解，复杂度O(log k)。（另一个算法，设f(i)=10^i mod n，则f(i)=f(i-1)*10mod n，然后求出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)return1;
if(y==1)return10%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);
return0;
}
第二题：火柴排队（贪心+逆序对）
对距离公式化简得：
∑(ai-bi)^2=∑(ai^2-2aibi+bi^2)=∑ai^2+∑bi^2-2∑aibi要求∑(ai-bi)^2最小，就只需要∑aibi最大即可。这里有个贪心，当a1<a2<…<an,b1<b2<..<bn时，∑aibi最大。证明如下：
若存在a>b,c>d，且ac+bd<ad+bc，则a(c-d)<b(c-d)，则a<b，与a>b矛盾，所以若a>b,c>d，则ac+bd>ad+bc
将此式子进行推广：
当a1<a2<a3<...<an,b1<b2<...<bn的情况下∑aibi最大，即∑(ai-bi)^2最小。
然后，将两个序列分别排序，确定每对数的对应关系，明显，同时移动两个序列中的数等效于只移动一个序列中的数，那么，我们就保持一个序列不动，然后根据另外那个序列中的数对应的数的位置，重新定义一个数组，求逆序对个数，就是答案。
例如：
对于数据：
4
2314
3214
先排序:
1234
1234
保持序列1不动，那么序列2中的3就对应序列1中的2位置，2就对应序列1中的1位置，1就对应序列1中的3位置，4就对应序列1中的4位置，那么重定义数组为：
2134
这个序列的逆序对为(2,1)，所以答案是1。
求逆序对方法：
1.归并排序
2.把数组扫一遍，顺序把每个数加入BIT或者是线段树等数据结构中，同
时查询比这个数大的数有几个，加入答案。
复杂度:O(n log n)
代码（C++）（树状数组）：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN100010
#define lowbit(x)(((~(x))+1)&x)
#define MAX99999997
struct saver{
int v,t;
};
saver a[MAXN],b[MAXN];
bool cmp(saver x,saver y){
return x.v<y.v;
}
int n,r[MAXN],ans=0;
int t[MAXN];
void Add(int x){for(int i=x;i<=n;i+=lowbit(i))t[i]++;}
int Sum(int x){
int rec=0;
for(;x;x-=lowbit(x))rec+=t[x];
return rec;
}
int main(){
scanf("%d",&n);
for(int i=0;i++<n;)scanf("%d",&a[i].v),a[i].t=i;
for(int i=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);
cstring转为int
for(int i=0;i++<n;)r[a[i].t]=b[i].t;
for(int i=n;i;i--)ans+=Sum(r[i]),Add(r[i]),ans%=MAX;
printf("%d\n",ans);
return0;
}
第三题：货车运输（贪心+最大生成树+树上路径倍增）
首先，我们可以确定贪心的正确性，我们先把边按权值从大到小排序，然后依次加入图中，如果该边的起末点不在同一连通块中，那么就把边加入，否则不加处

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。