本文主要是介绍【NOIP2013】【提高组】【Day1】【解题报告】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
T1转圈游戏
题目链接：http://codevs.cn/problem/3285/
题解：
可以发现最后的位置就是(x+m*10^k)%n;
然后直接用快速幂即可。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,k,x,p,ans;
long long power(long long x,long long b){long long ans=1;for(long long i=b;i;x=x*x%p,i>>=1)if(i&1)ans=ans*x%p;return ans;
}
int main(){cin>>n>>m>>k>>x;p=n;long long temp=power(10,k);ans=(temp*m%p+x)%p;cout<<ans<<endl;
}T2火柴排队
题目链接:http://codevs.cn/problem/3286/
题解：首先一个直观的思路肯定是让两个序列的rank值相同的数对在一起。
然后随便记录一下求逆序对即可。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100010
#define P 99999997
struct use{int x,y;}p[N],q[N],t[N];
bool cmp(use a,use b){return a.x<b.x;}
bool cmp2(use a,use b){return a.y<b.y;}
using namespace std;
int a,b,c[N],ans,n,rank[N],frank[N];
void add(int x,int v){for (int i=x;i<=n;i+=(i&(-i)))(c[i]+=v)%=P;}
int query(int x){int ans(0);for (int i=x;i;i-=(i&(-i)))(ans+=c[i])%=P;return ans;}
int main(){scanf("%d",&n);for (int i=1;i<=n;i++) {scanf("%d",&p[i].x);p[i].y=i;}for (int i=1;i<=n;i++) {scanf("%d",&q[i].x);q[i].y=i;}sort(p+1,p+n+1,cmp);for (int i=1;i<=n;i++) rank[i]=p[i].y;sort(q+1,q+n+1,cmp);for (int i=1;i<=n;i++) frank[q[i].x]=i;sort(q+1,q+n+1,cmp2);for (int i=1;i<=n;i++) t[i].x=rank[frank[q[i].x]],t[i].y=i;for (int i=n;i>=1;i--){(ans+=query(t[i].x-1))%=P;add(t[i].x,1);}cout<<ans<<endl;
}题目链接：http://codevs.cn/problem/3287/
题解：可以发现最大值就是最大生成树上的最大边。
然后直接树上倍增即可，
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10010
#define INF 999999999
using namespace std;
struct use{int st,en,v;}e[N*10],b[N*10];
int point[N],n,q,next[N*10],cnt,x,y,v,fa[N],f[N][30],vis[N],deep[N],fmx[N][30],m;
int find(int x){if (x!=fa[x]) fa[x]=find(fa[x]);return fa[x];}
bool cmp(use a,use b){return a.v>b.v;}
void add(int x,int y,int v){next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;e[cnt].v=v;
}
void dfs(int x){for (int i=1;(1<<i)<=deep[x];i++)fmx[x][i]=min(fmx[f[x][i-1]][i-1],fmx[x][i-1]),f[x][i]=f[f[x][i-1]][i-1];for (int i=point[x];i;i=next[i])if (e[i].en!=f[x][0]){f[e[i].en][0]=x;deep[e[i].en]=deep[x]+1;fmx[e[i].en][0]=e[i].v;dfs(e[i].en);}
}
int lca(int x,int y){if(deep[x]<deep[y]) swap(x,y);int t=deep[x]-deep[y];for (int i=0;i<=20;i++) if (t&(1<<i)) x=f[x][i];for (int i=20;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];if (x==y) return x;else return f[x][0];
}
int bz(int x,int y){int ans(INF),t=deep[x]-deep[y];for (int i=0;i<=20;i++)if (t&(1<<i)){ans=min(ans,fmx[x][i]);x=f[x][i];}return ans;
}
int main(){scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&v);b[i].st=++x;b[i].en=++y;b[i].v=v;}sort(b+1,b+m+1,cmp);for(int i=2;i<=n+1;i++) fa[i]=i; for (int i=1;i<=m;i++){int r1=find(b[i].st),r2=find(b[i].en);if (r1!=r2){fa[r1]=r2;add(b[i].st,b[i].en,b[i].v);add(b[i].en,b[i].st,b[i].v);}}for (int i=2;i<=n+1;i++){if (!vis[find(i)]){add(1,find(i),INF);add(find(i),1,INF);vis[find(i)]=1;}}memset(fmx,127/3,sizeof(fmx));dfs(1);scanf("%d",&q);for (int i=1;i<=q;i++){scanf("%d%d",&x,&y);x++;y++;if (fa[x]!=fa[y]){printf("-1\n");continue;}int l=lca(x,y);int ans=min(bz(x,l),bz(y,l));printf("%d\n",ans);}
}这篇关于【NOIP2013】【提高组】【Day1】【解题报告】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
