NOIp 2013 Day1 解题报告
不难看出答案就是(x+m*10k) mod n
用快速幂算法，复杂度O(log2k)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 //variable// 9 int n,m,x,k; 10 11 //solve// 12 int main(){ 13 scanf("%d%d%d%d",&n,&m,&k,&x); 14 int a=10,ans=1; 15 while (k){ 16 if (k&1){ 17 ans=(ans*a)%n; 18 } 19 k>>=1; 20 a=(a*a)%n; 21 } 22 ans=(ans*m+x)%n; 23 printf("%d\n",ans); 24 return 0; 25 }
整理题设算式，我们发现，当(A1B1+A2B2+…+AnBn)最大时题设最小。
依据排序不等式，当且仅当A1<A2<…<An且B1<B2<…<Bn时上式最大。
可以看出，对于Ak和Bk，同时交换两者和仅交换其中一个是等价的，因为无论如何交换，除了Ak和Bk以外，其他A和B彼此的相对位置不变。所以，我们默认固定A，交换B中的数，使他满足上文提到的对应关系。
令A中第i个数的num[i]=i，设A中第i个数排第k，则令B中排第k的数的num[j]=i
B的num的逆序对数就是答案。
利用树状数组求逆序对，复杂度O(NlogN)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 //variable// 9 int mod=99999997,a[110000],b[110000],st[110000],n,loc[110000],bit[110000]; 10 11 //function prototype// 12 int sumbit(int); 13 void addbit(int,int); 14 15 //solve// 16 int main(){ 17 scanf("%d",&n); 18 for (int i=1;i<=n;++i){ 19 scanf("%d",a+i); 20 } 21 for (int i=1;i<=n;++i){ 22 scanf("%d",b+i); 23 } 24 for (int i=1;i<=n;++i){ 25 st[i]=a[i]; 26 } 27 sort(st+1,st+n+1); 28 for (int i=1;i<=n;++i){ 29 a[i]=lower_bound(st+1,st+n+1,a[i])-st; 30 } 31 for (int i=1;i<=n;++i){ 32 st[i]=b[i]; 33 } 34 sort(st+1,st+n+1); 35 for (int i=1;i<=n;++i){ 36 b[i]=lower_bound(st+1,st+n+1,b[i])-st; 37 } 38 for (int i=1;i<=n;++i){ 39 st[a[i]]=i; 40 } 41 for (int i=1;i<=n;++i){ 42 loc[i]=st[b[i]]; 43 } 44 int ans=0; 45 for (int i=n;i;--i){ 46 ans=(ans+sumbit(loc[i]))%mod; 47 addbit(loc[i],1); 48 } 49 printf("%d\n",ans); 50 return 0; 51 } 52 53 void addbit(int x,int delta){ 54 for (;x<=n;x+=x&-x){ 55 bit[x]+=delta; 56 } 57 } 58 59 int sumbit(int x){ 60 int ret=0; 61 for (;x;x-=x&-x){ 62 ret+=bit[x]; 63 } 64 return ret; 65 }
定理：无向带权图上，任意两点间，满足在所有路径中，路径上边权最小（大）值最大（小）的路径一定在最大（小）生成树上。
证明：依据最大（小）生成树的定义，利用反证法可以显然得证。
因此，由上可得，本题所求就是两点间路径上最小边的最大值。求出最大生成树，再在最大生成树上倍增得到每个询问的答案。
复杂度O(MlogM+NlogN+QlogN)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 //type// 9 struct mingraph{ 10 int from,dest,cost,use; 11 }; 12 13 //variable// 14 mingraph g[100000]; 15 int tot=1,last[100100],prel[100100],dest[100100],cost[100100]; 16 int Q,n,m,ance[11000][20],mins[11000][20],fa[11000],vis[11000],q[11000],dep[11000]; 17 18 //function prototype// 19 void kruskal(void); 20 void addline(int,int,int); 21 void bfs(int); 22 void calc_ance(void); 23 bool comp(mingraph,mingraph); 24 int getfa(int); 25 int calc_ans(int,int); 26 27 //solve// 28 int main(){ 29 scanf("%d%d",&n,&m); 30 for (int i=1;i<=m;++i){ 31 scanf("%d%d%d",&g[i].from,&g[i].dest,&g[i].cost); 32 g[i].use=0; 33 } 34 kruskal(); 35 for (int i=1;i<=m;++i){ 36 if (g[i].use){ 37 addline(g[i].from,g[i].dest,g[i].cost); 38 addline(g[i].dest,g[i].from,g[i].cost); 39 } 40 } 41 memset(vis,0,sizeof vis); 42 memset(mins,0x7f,sizeof mins); 43 for (int i=1;i<=n;++i){ 44 if (!vis[i]){ 45 bfs(i); 46 } 47 } 48 calc_ance(); 49 for (scanf("%d",&Q);Q;--Q){ 50 int x,y; 51 scanf("%d%d",&x,&y); 52 if (getfa(x)!=getfa(y)){ 53 puts("-1"); 54 }else{ 55 printf("%d\n",calc_ans(x,y)); 56 } 57 } 58 return 0; 59 } 60 61 int calc_ans(int u,int v){ 62 int ans=2147000000; 63 if (dep[u]<dep[v]){ 64 swap(u,v); 65 } 66 for (int j=19;j>=0;--j){ 67 if ((1<<j)&(dep[u]-dep[v])){ 68 ans=min(ans,mins[u][j]); 69 u=ance[u][j]; 70 } 71 } 72 if (u==v){ 73 return ans; 74 } 75 for (int j=19;j>=0;--j){ 76 if (ance[u][j]!=ance[v][j]){ 77 ans=min(ans,min(mins[u][j],mins[v][j])); 78 u=ance[u][j]; 79 v=ance[v][j]; 80 } 81 } 82 return min(ans,min(mins[u][0],mins[v][0])); 83 } 84 85 void calc_ance(){ 86 for (int j=1;j<20;++j){ 87 for (int i=1;i<=n;++i){ 88 ance[i][j]=ance[ance[i][j-1]][j-1]; 89 mins[i][j]=min(mins[ance[i][j-1]][j-1],mins[i][j-1]); 90 } 91 } 92 } 93 94 void bfs(int x){ 95 int he=1,ta=1; 96 memset(q,0,sizeof q); 97 q[1]=x;vis[x]=1;dep[x]=1; 98 while (he<=ta){ 99 int u=q[he++]; 100 for (int k=last[u];k;k=prel[k]){ 101 if (!vis[dest[k]]){ 102 vis[dest[k]]=1; 103 q[++ta]=dest[k]; 104 dep[dest[k]]=dep[u]+1; 105 ance[dest[k]][0]=u; 106 mins[dest[k]][0]=cost[k]; 107 } 108 } 109 } 110 } 111 112 void addline(int u,int v,int w){ 113 dest[++tot]=v; 114 prel[tot]=last[u]; 115 last[u]=tot; 116 cost[tot]=w; 117 } 118 119 bool comp(mingraph a,mingraph b){ 120 return a.cost>b.cost; 121 } 122 123 void kruskal(){ 124 sort(g+1,g+m+1,comp); 125 for (int i=1;i<=n;++i){ 126 fa[i]=i; 127 } 128 int tot=0; 129 for (int i=1;i<=m;++i){ 130 if (getfa(g[i].from)!=getfa(g[i].dest)){ 131 g[i].use=1; 132 fa[getfa(g[i].from)]=getfa(g[i].dest); 133 ++tot; 134 if (tot==n-1){ 135 break; 136 } 137 } 138 } 139 } 140 141 int getfa(int x){ 142 return fa[x]==x? x:fa[x]=getfa(fa[x]); 143 }
原文：http://www.cnblogs.com/ZXTLFDeAR/p/4805106.html
