今天又考了noip2013 DAY 1 的题 【超级气本来说好上课的！！！但是氢氟酸讲不起走了于是就又开始考试了……】 【而且三个半小时的题我们只考两个半小时还提前被叫回去了还被zj怼 我简直……】 【跑题了】 第一题 大概是一道数论题。。。 手动模拟一下，可以看出每n次就会回到原来的位置上，所以它是具有周期性的，所以可以通过一个快速幂来找出有效的区段，然后for一遍就不会超时了。
//每n次就回到原来的位置上 #include<cstdio> #include<algorithm> #define ll long long using namespace std; int n,m,k,x; ll cir; ll mpow(int a,int b){ ll rt=1; for(rt;b;b>>=1,a=a*a%n) if(b&1) rt=rt*a%n; return rt; } int main(){ freopen("circle.in","r",stdin); freopen("circle.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&x); cir=mpow(10,k);//有效轮数 for(int i=1;i<=cir;i++){ x+=m; if(x>n) x-=n; } printf("%d",x); return 0; }第二题 考试的时候想了归并排序 但是……自己对归并排序就只剩下知道这个名字了……然后也想过树状数组，但是我这么蒟蒻，肯定编不出来啦，所以考试的时候都干脆不尝试了。。【我怎么好意思说自己树状数组学的不错】 【不过考试时for的暴力居然过了百分之70的点。。。】 【后来修改还是用的树状数组】 【放弃归并排序了】【有时间刚一下，然而……】 附上代码
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const N = 100010; int const mod = 99999997; int n,ans=0; int c[N],t[N]; struct node{ int x,y; }a[N],b[N]; bool cmp(node a,node b){ return a.x<b.x; } int lowbit(int x){ return x&(-x); } void update(int x){ while(x<=n){ c[x]+=1; x+=lowbit(x); } } int getsum(int x){ int rt=0; while(x){ rt+=c[x]; x-=lowbit(x); } return rt; } int main(){ freopen("match.in","r",stdin); freopen("match.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i].x); a[i].y=i; } for(int i=1;i<=n;i++){ scanf("%d",&b[i].x); b[i].y=i; } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); for(int i=1;i<=n;i++) t[a[i].y] = b[i].y; for(int i=n;i>=1;i--){ ans+=getsum(t[i]); if(ans>=mod) ans-=mod; update(t[i]); } printf("%d",ans); return 0; }其实考试的时候离散化+for一遍也挺好的 我考试的时候居然把离散化写出来了。。。 第三题 我就想到spfa【还自以为自己的方法比较优。。。】 有时间单独刚吧，再单独写个总结【又是一个flag】
#include <cstdio> #include <cstring> #include <algorithm> #define ms(x,y) memset(x,y,sizeof(x)) using namespace std; int const N = 50010; int const M = 1010; int n,m; int head[N*2],tot=0; int q,state[N],mmin[M][M]; bool vis[M][M],exist[M]; struct node{ int pre,v,w; }edge[N*2]; void adde(int from,int to,int w){ tot++; edge[tot].pre = head[from]; edge[tot].v = to; edge[tot].w = w; head[from] = tot; } void spfa(int i){ int h=0,tail=1; mmin[i][i]=0x73f3f3f; state[1]=i; vis[i][i]=true; do{ h++; int u = state[h]; exist[u]=false; for(int j=head[u];j;j=edge[j].pre){ int v=edge[j].v; if(v == u) continue; if(vis[i][v]==false||(vis[i][v]==true&&min(mmin[i][u],edge[j].w)>mmin[i][v])){ if(vis[i][v] == false){ vis[i][v] = true; if(mmin[i][u] < edge[j].w) mmin[i][v] = mmin[i][u]; else mmin[i][v] = edge[j].w; } if(vis[i][v]==true&&min(mmin[i][u],edge[j].w)>mmin[i][v]) mmin[i][v] = min(mmin[i][u],edge[j].w); if(!exist[v]){ exist[v]=true; tail++; state[tail]=v; } } } }while(h<tail); } int main(){ freopen("truck.in","r",stdin); freopen("truck.out","w",stdout); ms(mmin,0x73f3f3f); scanf("%d%d",&n,&m); while(m--){ int x,y,z; scanf("%d%d%d",&x,&y,&z); adde(x,y,z); adde(y,x,z); } scanf("%d",&q); while(q--){ int u,v; scanf("%d%d",&u,&v); if(!vis[u][u]) spfa(u); if(vis[u][v]) printf("%d\n",mmin[u][v]); else printf("-1\n"); } return 0; }