2016 Multi-University Training Contest 1

题目：https://cn.vjudge.net/contest/296683

A - Abandoned country

HDU - 5723 求最小生成树，再求这个最小生成树上任意两个点的最短距离期望 任意两个点情况数就是C(n,2)，任意两个点的距离和可以转化为求每条边的贡献和 而每条边的贡献就是u->v valsz[v](n-sz[v]用dp[u]储存所有和u相连的边的贡献和，简单树形Dp

#include using namespace std; #define ll long long const int maxn=100010; const int maxm=1000010; struct edge{ int u,v,w,nxt; }e[maxm]; int head[maxn],tot; int n,m; int f[maxn]; void init() { memset(head,-1,sizeof(head)); tot=0; } void addedge(int u,int v,int w) { e[tot].u=u; e[tot].v=v; e[tot].w=w;e[tot].nxt=head[u]; head[u]=tot++; } int find1(int x) { return x==f[x]?x:f[x]=find1(f[x]); } bool union1(int a,int b) { int fa=find1(a),fb=find1(b); if(fa!=fb){ f[fa]=fb; return false; } return true; } struct node{ int a,b,c; }hh[maxm]; bool cmp(const node& a,const node& b) { return a.c<b.c; } ll kruscal() { sort(hh,hh+m,cmp); ll sum=0; for(int i=0;i<m;i++){ int a=hh[i].a; int b=hh[i].b; if(!union1(a,b)){ sum+=1LL*hh[i].c; int c=hh[i].c; addedge(a,b,c); addedge(b,a,c); } } return sum; } int sz[maxn]; double dp[maxn]; void dfs(int u,int fa)// { sz[u]=1; for(int i=head[u];~i;i=e[i].nxt){// int v=e[i].v,w=e[i].w; if(v==fa) continue; dfs(v,u); sz[u]+=sz[v]; dp[u]+=dp[v]+(double)(n-sz[v])*sz[v]*w; } } int main() { int t; scanf("%d",&t); while(t--){ init(); scanf("%d%d",&n,&m); int a,b,c; for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); hh[i].a=a;hh[i].b=b; hh[i].c=c; } for(int i=1;i<=n;i++){ f[i]=i; dp[i]=0; } ll ans=kruscal(); printf("%lld ",ans); dfs(1,-1); printf("%.2f\n",dp[1]*2/n/(n-1)); } } 

B - Chess

HDU - 5724 题解转载自：https://blog.csdn.net/fsss_7/article/details/51957497 题意：有个n*20的表格，每行有若干棋子，两个人轮流移动。每次移动棋子只能将这枚棋子移动到它右边的第一个空格，同一个位置最多只能有一个棋子，不能移动棋子的人输。 SG函数：https://blog.csdn.net/Danliwoo/article/details/51968789 分析：因为每一行只有20个位置，我们直接用二进制保存，然后计算每个状态的sg值，然后将n行的sg值异或起来就行了，xor=0先手输否则先手胜 状态储存，这里逆着储存状态，高位到地位，方便用前面的结果

#include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int N=4010; const int mod=100000000; const int MOD1=1000000007; const int MOD2=1000000009; const double EPS=0.00000001; typedef long long ll; const ll MOD=1000000007; const int MAX=1000000010; const ll INF=1ll<<55; const double pi=acos(-1.0); typedef double db; typedef unsigned long long ull; int d[25],f[1050000]; int get(int x) { int i,bo=0,w; for (i=1;i<=20;i++) if ((1<<i)-1==x) return 0; memset(d,0,sizeof(d)); for (i=0;i<20;i++) if ((1<<i)>x) break ; else if (((1<<i)&x)==0) { bo=1;w=i; } else if (bo) { d[f[x-(1<<i)+(1<<w)]]=1; } for (i=0;i<25;i++) if (!d[i]) return i; } int main() { int i,j,g,x,n,t,sum,ans; f[0]=0;for (i=1;i<=(1<<20);i++) f[i]=get(i); scanf("%d", &t); while (t--) { scanf("%d", &n);ans=0; for (i=1;i<=n;i++) { scanf("%d", &g);sum=0; for (j=1;j<=g;j++) { scanf("%d", &x);sum+=1<<(20-x); } ans^=f[sum]; } if (ans) printf("YES\n"); else printf("NO\n"); } return 0; } 

C - Game

HDU - 5725

题解转载自：https://blog.csdn.net/y1196645376/article/details/52187900/ 题意：对于一个nm地图的任意两点的曼哈顿距离和为 n ∗ m ∗ ( n ∗ m − 1 ) ∗ ( n + m ) / 3 n*m*(n*m-1)*(n+m)/3 n∗m∗(n∗m−1)∗(n+m)/3 n ∗ m n*m n∗m的图上有一些守卫，守卫的位置，满足彼此不同行，不同列，且相邻8格内不会有其他守卫，现等概率的选取起点和终点，所有可以不碰守卫可以到达的路径中，最短路径的期望。 分析：期望等于路径总和除以路径条数。 我们先算路径条数： 对于起点和终点都是等概率随机选择，那么起点和终点组合一共有 ( n ∗ m ) ∗ ( n ∗ m ) (n*m)*(n*m) (n∗m)∗(n∗m)种。然后我们应该去掉起点或者终点为G的组合。怎么去呢？ 分类：当起点为G终点不为G的组合有numG * num# ( numG表示G的个数，num#表示#个数). 然后是起点不为G终点为G的组合有numG * num#.起点也是G终点也是G的有numG * num G.三者加起来就是应该去掉的路径数量。有人可能问？如果起点和终点不为G就一定存在路径？答案是是的。因为根据守卫的摆放原则，一定是有解的。(这注意了，可能是题目没有描述清楚，但是通过数据可知为了躲避守卫的路径中可以超越nm这个地图边界)。 那么剩下来算路径总和： 对于一个 n ∗ m n*m n∗m地图的任意两点的曼哈顿距离和为 n ∗ m ∗ ( n ∗ m − 1 ) ∗ ( n + m ) / 3 n*m*(n*m-1)*(n+m)/3 n∗m∗(n∗m−1)∗(n+m)/3。 然后我们需要减去起点终点含有G的路径。怎么减呢？只需要对于每个G减去两倍的地图所有点到该点的距离(O(1)可得)。然后我们明显知道。对于起点和终点都是G的情况我们减多了2倍。所以我们两重for循环对于起点终点都是G的组合路径加回来。 然后我们知道，这些路径中有的路径可能会被守卫挡住。需要绕开，并且绕开之后的路径长度并不为该两点的曼哈顿距离。所以我们要计算因为G而导致多走的路径。 因为每条路径最多只会背一个守卫阻挡（根据守卫的摆放规则)。 那么每条路径如果要绕开就会多2的长度。所以我们要计算所有多走的长度。只需要计算有多少条路径需要多走。然后乘2即可。 我们可以发现： 假如地图为： ##G##那么左边两边点和右边两个点之间的路径需要绕开G。这种情况说明如果起点和终点在一条直线上，并且之间有G隔开说明需要绕开。 #G### ###G# 我们发现左上角走到右下角。也需要绕开第一个G或者第二个。这种情况索命。如果起点和终点不在一条直线上。那么如果在横或者竖方向上有一排G拦住。注意这里的一排G并不处于一排。而是保证每列或者每行都有。并且，越靠近起点的另一个方向上的坐标也就越靠近起点。（最后一句可能不好理解。我画图）# #G### ###G#我们可以看到第一排的G必须在第二排G的左边，因为起点在左边，行数越靠近起点的，横坐标越靠近起点。为什么呢？ 如果是这样： ###G# #G### 你认为还能阻拦左上到右下么？ 所以满足以上两种情况的路径都应该被计算到绕路路径中，然后让路径总和再加上绕路路径的条数*2。 最后相除就是期望。

#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair<ll,ll> ll2; ll n,m; char mpt[1005][1005]; ll2 book[1005]; int x[1005],y[1005]; int num; //n*m的图，计算以（1，1）为起点到所有曼哈顿距离和 ll get(ll n,ll m) { return m*(m-1)*n/2+n*(n-1)*m/2; } //n*m的图，计算任意点到所有点的曼哈顿距离和 ll get2(ll x,ll y) { return get(x,y)+get(n-x+1,y)+get(x,m-y+1)+get(n-x+1,m-y+1)-(get(1,x)+get(1,y)+get(1,n-x+1)+get(1,m-y+1)); } ll get3(int i,int j) { ll a = book[i].first - book[j].first; if(a<0) a= -a; ll b = book[i].second - book[j].second; if(b<0) b= -b; return a+b; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); getchar(); for(int i = 0 ; i < n ; i ++) gets(mpt[i]); ll ans = n*m*(n*m-1)*(n+m)/3;//n*m的所有点对曼哈顿距离和  ll cnt = n*m*n*m;//路径数  num = 0; memset(x,-1,sizeof(x)); memset(y,-1,sizeof(y)); for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < m ; j ++) if(mpt[i][j] == 'G') { book[num++] = ll2(i,j); x[i] = j; y[j] = i; ans -= 2* get2(i+1,j+1);//减去G到所有其他点  cnt -= 2 * (n*m-1) + 1;//G到所有其他点的路径数  } for(int i = 0 ; i < num ; i ++) for(int j = 0 ; j < num ; j ++) { ans += get3(i,j);//加上G到G  if(i != j) cnt += 1;//加上G到G的路径数  } for(int i = 0 ; i < num ; i ++)//下面加了2次，这里需要减1次  { ans -= 4 * book[i].first * ( n - book[i].first - 1);//减去G的左右  ans -= 4 * book[i].second * ( m - book[i].second - 1);//减去G的上下  } //left to right ll suml = 0,sumr = 0; for(int i = 0 ; i < n ; i ++) { if(x[i] != -1) { if(i != 0 && x[i] > x[i-1]) suml += x[i]; else suml = x[i]; ans += 4 * suml * (m - x[i] - 1); if(i != 0 && x[i] < x[i-1]) sumr += (m - x[i] - 1); else sumr = (m - x[i] - 1); ans += 4 * sumr * x[i]; } else suml = 0,sumr = 0; } //down to up ll sumu = 0,sumd = 0; for(int j = 0 ; j < m ; j ++) { if(y[j] != -1) { if(j != 0 && y[j] > y[j-1]) sumu += y[j]; else sumu = y[j]; ans += 4 * sumu * (n - y[j] - 1); if(j != 0 && y[j] < y[j-1]) sumd += (n - y[j] - 1); else sumd = (n - y[j] - 1); ans += 4 * sumd * y[j]; } else sumu = 0,sumd = 0; } double an = (long double)ans/cnt; printf("%.4llf\n",an); } return 0; } 

D – GCD（RMQ+st表）

HDU - 5726

题解转载自：https://blog.csdn.net/viphong/article/details/52013352 首先用st表预处理RMQ的gcd，然后枚举起点【1-n】i 由于gcd一段固定以后具有单调性的 对于每个起点，枚举右端点pos，记下i到pos的gcd为X，则在【pos,n】里二分查找最远的gcd仍为X的下标next，则说明从i开始到pos，与i到next之间的gcd都是同样的，因此mp[x]+=（next-pos+1） 每次case，nlogn预处理st表，预处理所有gcd个数大约时间为nlognlogn，查询o(1)+o(logn)

#include #include #include  #include using namespace std; #define ll long long const int maxn=1e5+5; int h[maxn],mx[maxn][17]; map<int,ll> mp; int n; int gcd(int a,int b) { return b?gcd(b,a%b):a; } void rmq_init() { for(int i=1;i<=n;i++) mx[i][0]=h[i]; int m=floor(log((double)n)/log(2.0)); for(int i=1;i<=m;i++){ for(int j=n;j>0;j--){ //for(int j=1;j<=n;j++){ mx[j][i]=mx[j][i-1]; if(j+(1<<(i-1))<=n) mx[j][i]=gcd(mx[j][i-1],mx[j+(1<<(i-1))][i-1]); } } } int rmq_gcd(int l,int r) { int m=floor(log((double)(r-l+1))/log(2.0)); return gcd(mx[l][m],mx[r-(1<<m)+1][m]); } int bin(int st,int l,int r,int pre_gcd) { int ans; while(l<=r){//l