NOIP2013

1.circle

ans=((10^k%n*m)%n+x)%n

int power(k){

　　if(k==0)return 1%n;

　　if(k==1)return 10%n;

　　int p=power(k>>1);

　　if(k%2==1)return ((p*p)%n*10)%n;

　　return (p*p)%n;

}

2.match

use mergesort to count inversion

int mergesort(int L,int R){
if(L==R)return 0;
int cnt=0;
int M=(L+R)>>1;
cnt=mergesort(L,M);
cnt+=mergesort(M+1,R);
cnt%=mask;
int i=L;int j=M+1;
int * p=new int[R-L+1];
for(int k=0;k<=R-L;k++){
if(i<=M&&j<=R){
if(f[i]<f[j]){
p[k]=f[i];
i++;
}
else{
p[k]=f[j];
cnt+=M-i+1;
cnt%=mask;
j++;
}
}
else{
if(j<=R){
p[k]=f[j];
j++;
}
else{
p[k]=f[i];
i++;
}
}
}
copy(p,p+R-L+1,f+L);
return cnt;
}

3.truck

kruskal,unionfindset score 60

kruskal,dfs score 60

正解参考我的随笔 http://www.cnblogs.com/JebediahKerman/p/5678625.html

  1 /*truck*/
  2 class edge{
  3 public:
  4     edge(int vv1,int vv2,int ww){
  5         v1=vv1;v2=vv2;weight=ww;
  6     }    
  7     int v1;int v2;int weight;
  8     static bool compareTo(const edge * a,const edge * b){
  9         return a->weight > b->weight;
 10     }
 11 };
 12 class UnionFindSet{
 13     static const int N=;
 14     int f[N];
 15 public:
 16     UnionFindSet(int n){
 17         for(int i=1;i<=n;i++)
 18             f[i]=i;
 19     }
 20     
 21     int find(int x){
 22         if(f[x]==x)return x;
 23         return f[x]=find(f[x]);
 24     }
 25     
 26     void Union(int a,int b){
 27         int fa=find(a);
 28         int fb=find(b);
 29         f[fb]=fa;
 30     }
 31 };
 32 class Kruskal{
 33 public:
 34     static bool kruskal(int n,vector<edge *> & E,vector<edge *> &T){
 35         UnionFindSet U(n);
 36         sort(E.begin(),E.end(),edge().compare);
 37         int k=0;int e=0;
 38         while(k<n-1&&e<E.size()){
 39             edge * ee=E[e];
 40             int a=U.find(ee->v1);
 41             int b=U.find(ee->v2);
 42             if(a!=b){
 43                 T.push_back(ee);
 44                 U.Union(ee->v1,ee->v2);
 45                 k++;
 46             }
 47         }
 48         return k==n-1;
 49     }
 50 };
 51 class SetRoot{
 52 public:
 53     static void pretreat(vector<edge *> & T,vector<int> * G){
 54         for(int i=0;i<T.size();i++){
 55             edge & e=*T[i];
 56             G[e.v1].push_back(i);
 57         }
 58     }
 59     static void dfs(vector<edge *> & T,vector<int> * G,int * fa,int *cost,int *L,int u,int fthr){
 60         vector<int> & g=G[u];
 61         for(int i=0;i<g.size();i++){
 62             edge & e=*T[g[i]];
 63             if(e.v2!=fa){
 64                 fa[e.v2]=u;
 65                 L[e.v2]=L[u]+1;
 66                 cost[e.v2]=e.weight;
 67                 dfs(T,G,fa,cost,e.v2,u);
 68             }
 69         }
 70     }
 71 };
 72 class LCA{
 73 public:
 74     static void prepocess(int (* anc)[LN],int (* mincost)[LN],int * fa,int * cost,int n){
 75         for(int i=1;i<=n;i++){
 76             anc[i][0]=fa[i];
 77             mincost[i][0]=cost[i];
 78             for(int j=1;(1<<j)<=n;j++)anc[i][j]=-1;
 79         }
 80         for(int j=1;(1<<j)<=n;j++)
 81             for(int i=1;i<=n;i++){
 82                 if(anc[i][j-1]!=-1){
 83                     int a=anc[i][j-1];
 84                     anc[i][j]=anc[a][j-1];
 85                     mincost[i][j]=min(mincost[i][j-1],mincost[a][j-1]);
 86                 }
 87             }
 88     }
 89     
 90     static query(int (* anc)[LN],int (* mincost)[LN]int p,int q){
 91         int tem;int log=0;int i;
 92         if(L[p]<L[q])swap(p,q);
 93         while((1<<(log+1))<=L[p])log++;
 94         
 95         int ans=1e9;
 96         for(int i=log;i>=0;i--)
 97             if(L[p]-(1<<i)>=L[q]){
 98                 ans=min(ans,mincost[p][i]);
 99                 p=anc[p][i];
100             }
101         if(p==q)return ans;//LCA(p,q)=p
102         
103         for(int i=log;i>=0;i--)
104             if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
105                 ans=min(ans,mincost[p][i]);
106                 p=anc[p][i];
107                 ans=min(ans,mincost[q][i]);
108                 q=anc[q][i];
109             }
110         ans=min(ans,cost[p]);
111         ans=min(ans,cost[q]);
112         return ans;//LCA(p,q)=fa[p]=fa[q]
113     }
114 };
115 class graph{
116 public:
117     static void addedge(vector<edge *> & E,int v1,int v2,int ww){
118         E.push_back(new edge(v1,v2,ww));
119         E.push_back(new edge(v2,v1,ww));
120     }
121 };
122 
123 vector<edge *> E;
124 vector<edge *> T;
125 vector<int> G;
126 int n;int m;
127 int anc[N][LN];int L[N];
128 int cost[N];int mincost[N][LN];
129 int fa[N];
130 int main(){
131     ifstream fin("truck.in");
132     ofstream fout("truck.out");
133     
134     fin>>n>>m;
135     
136     for(int i=1;i<=n;i++){
137         int v1;int v2;int ww;
138         fin>>v1>>v2>>ww;
139         graph().addedge(E,v1,v2,ww);
140     }
141     
142     Kruskal().kruskal(n,E,T);
143     SetRoot().pretreat(T,G);
144     SetRoot().dfs(T,G,cost,fa,cost,L,1,0);
145     LCA().preprocess(anc,mincost,fa,cost,n);
146     
147     for(int i=1;i<=m;i++){
148         int v1;int v2;
149         fin>>v1>>v2;
150         fout<<LCA().query(anc,mincost,v1,v2)<<endl;
151     }
152     
153     return 0;
154 }