2016 Multi-University Training Contest 1
分类:
IT文章
•
2025-02-04 12:32:38
1001 Abandoned country
先做最小生成树（边权不同保证唯一）。
然后打牌一下sz，单边贡献为边权乘两头sz积。
![]()
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <vector>
5 #include <algorithm>
6 using namespace std;
7 typedef long long LL;
8 const int maxn = 1e5 + 10;
9 int n, m;
10 LL ans;
11
12
13 // G
14 struct Edge
15 {
16 int from, to, val;
17 Edge(int F, int T, int V): from(F), to(T), val(V){}
18 friend bool operator < (Edge A, Edge B)
19 {
20 return A.val < B.val;
21 }
22 };
23 vector<Edge> vec;
24
25
26 // UF
27 int fa[maxn];
28 int Find(int x)
29 {
30 return fa[x] == x ? x : fa[x] = Find(fa[x]);
31 }
32 void Union(int x, int y)
33 {
34 x = Find(x);
35 y = Find(y);
36 fa[y] = x;
37 }
38
39
40 // tree
41 int cnt, h[maxn];
42 struct edge
43 {
44 int to, pre, val;
45 } e[maxn<<1];
46 void add(int from, int to, int val)
47 {
48 cnt++;
49 e[cnt].pre = h[from];
50 e[cnt].to = to;
51 e[cnt].val = val;
52 h[from] = cnt;
53 }
54
55
56 // Kruskal
57 LL Kruskal()
58 {
59 LL ret = 0LL;
60 sort(vec.begin(), vec.end());
61 int sz = vec.size();
62 for(int i = 0; i < sz; i++)
63 {
64 Edge tmp = vec[i];
65 int a = tmp.from, b = tmp.to, v = tmp.val;
66 if(Find(a) == Find(b)) continue;
67 add(a, b, v), add(b, a, v);
68 Union(a, b);
69 ret = ret + v;
70 }
71 return ret;
72 }
73
74
75 // dp
76 int sz[maxn];
77 void dfs(int x, int f)
78 {
79 sz[x] = 1;
80 for(int i = h[x]; i; i = e[i].pre)
81 {
82 int to = e[i].to, v = e[i].val;
83 if(to == f) continue;
84 dfs(to, x);
85 sz[x] += sz[to];
86 ans += (LL) v * sz[to] * (n - sz[to]);
87 }
88 }
89
90
91 void init()
92 {
93 ans = 0LL;
94 cnt = 0;
95 vec.clear();
96 memset(h, 0, sizeof(h));
97 for(int i = 0; i < maxn; i++) fa[i] = i;
98 }
99
100
101 int main(void)
102 {
103 int T;
104 scanf("%d", &T);
105 while(T--)
106 {
107 init();
108 scanf("%d %d", &n, &m);
109 for(int i = 1; i <= m; i++)
110 {
111 int a, b, v;
112 scanf("%d %d %d", &a, &b, &v);
113 vec.push_back(Edge(a, b, v));
114 }
115 LL ans1 = Kruskal();
116 dfs(1, 0);
117 printf("%I64d %.2f
", ans1, 2.0 * ans / n / (n - 1));
118 }
119 return 0;
120 }
Aguin
1002 Chess
单行2^20局面暴力打好sg，每行^一下。
![]()
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 int sg[1<<20];
5
6 void cal(int x)
7 {
8 int last = -1, vis[20] = {0};
9 for(int i = 0; i < 20; i++)
10 {
11 if(!(x & (1 << i))) last = i;
12 else if(last != -1) vis[sg[((1<<last)|(1<<i))^x]] = 1;
13 }
14 for(int i = 0; i <= 20; i++)
15 if(!vis[i]) {sg[x] = i; return;}
16 }
17
18 int main(void)
19 {
20 for(int i = 0; i < (1 << 20); i++) cal(i);
21
22 int T;
23 scanf("%d", &T);
24 while(T--)
25 {
26 int N, ans = 0;
27 scanf("%d", &N);
28 for(int i = 1; i <= N; i++)
29 {
30 int m, x = 0;
31 scanf("%d", &m);
32 for(int i = 0; i < m; i++)
33 {
34 int y;
35 scanf("%d", &y);
36 x += 1 << (20 - y);
37 }
38 ans ^= sg[x];
39 }
40 puts(ans ? "YES" : "NO");
41 }
42 return 0;
43 }
Aguin
1003 Game
1004 GCD
打好st表，对每个固定的左端点，gcd最多只有logai个下降点。
可以二分每个下降点的位置，更好的方法是从右往左枚举左端点，维护下降点序列。
![]()
1 #include <iostream>
2 #include <cstdio>
3 #include <map>
4 #include <set>
5 using namespace std;
6 typedef long long LL;
7 const int maxn = 1e5 + 10;
8 map<LL, LL> M;
9 set<int> S;
10 set<int> :: iterator it;
11 int N;
12
13 LL gcd(LL a, LL b)
14 {
15 return a % b ? gcd(b, a % b) : b;
16 }
17
18 // RMQ
19 LL a[maxn], rmq[maxn][20];
20 void RMQ_init()
21 {
22 for(int i = 1; i <= N; i++) rmq[i][0] = a[i];
23 for(int j = 1; (1 << j) <= N; j++)
24 for(int i = 1; i + ( 1 << j ) - 1 <= N; i++)
25 rmq[i][j] = gcd(rmq[i][j-1] , rmq[i+(1<<j-1)][j-1]);
26 }
27 int RMQ_query(int l, int r)
28 {
29 int k = 0;
30 while( ( 1 << (k + 1) ) <= r - l + 1 ) k++;
31 return gcd(rmq[l][k], rmq[r-(1<<k)+1][k]);
32 }
33
34 int main(void)
35 {
36 int T;
37 scanf("%d", &T);
38 for(int kase = 1; kase <= T; kase++)
39 {
40 scanf("%d", &N);
41 for(int i = 1; i <= N; i++) scanf("%I64d", a + i);
42 RMQ_init();
43
44 S.clear(), M.clear();
45 for(int l = N; l; l--)
46 {
47 int last = N;
48 LL now = RMQ_query(l, N);
49 for(it = S.begin(); it != S.end();)
50 {
51 LL tmp = RMQ_query(l, -(*it));
52 if(tmp == now) S.erase(it++);
53 else
54 {
55 M[now] += (LL) (last + *it);
56 now = tmp;
57 last = -(*(it++));
58 }
59 }
60 M[now] += (LL) (last - l);
61 M[a[l]]++;
62 if(a[l] != now) S.insert(-l);
63 }
64
65 int Q;
66 scanf("%d", &Q);
67 printf("Case #%d:
", kase);
68 for(int i = 0; i < Q; i++)
69 {
70 int l, r;
71 scanf("%d %d", &l, &r);
72 LL ans = RMQ_query(l, r);
73 printf("%I64d %I64d
", ans, M[ans]);
74 }
75
76 }
77 return 0;
78 }
Aguin
1005 Necklace
枚举yin排列，以yang和空位建二分图。
空位两边yin不会使yang褪色则连边，N - 最大匹配即为答案。
习惯用Dinic跑，结果1s+。
![]()
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <queue>
6 using namespace std;
7 const int INF = 1e9;
8 int lv[22], it[22];
9 int cnt, h[22];
10
11 struct edge
12 {
13 int to, pre, cap;
14 } e[1111];
15
16 void init()
17 {
18 memset(h, -1, sizeof(h));
19 cnt = 0;
20 }
21
22 void add(int from, int to, int cap)
23 {
24 e[cnt].pre = h[from];
25 e[cnt].to = to;
26 e[cnt].cap = cap;
27 h[from] = cnt;
28 cnt++;
29 }
30
31 void ad(int from, int to, int cap)
32 {
33 add(from, to, cap);
34 add(to, from, 0);
35 }
36
37 void bfs(int s)
38 {
39 memset(lv, -1, sizeof(lv));
40 queue<int> q;
41 lv[s] = 0;
42 q.push(s);
43 while(!q.empty())
44 {
45 int v = q.front(); q.pop();
46 for(int i = h[v]; i >= 0; i = e[i].pre)
47 {
48 int cap = e[i].cap, to = e[i].to;
49 if(cap > 0 && lv[to] < 0)
50 {
51 lv[to] = lv[v] + 1;
52 q.push(to);
53 }
54 }
55 }
56 }
57
58 int dfs(int v, int t, int f)
59 {
60 if(v == t) return f;
61 for(int &i = it[v]; i >= 0; i = e[i].pre)
62 {
63 int &cap = e[i].cap, to = e[i].to;
64 if(cap > 0 && lv[v] < lv[to])
65 {
66 int d = dfs(to, t, min(f, cap));
67 if(d > 0)
68 {
69 cap -= d;
70 e[i^1].cap += d;
71 return d;
72 }
73 }
74 }
75 return 0;
76 }
77
78 int Dinic(int s, int t)
79 {
80 int flow = 0;
81 while(1)
82 {
83 bfs(s);
84 if(lv[t] < 0) return flow;
85 memcpy(it, h, sizeof(it));
86 int f;
87 while((f = dfs(s, t, INF)) > 0) flow += f;
88 }
89 }
90
91 int a[11], G[11][11];
92 int main(void)
93 {
94 int N, M;
95 while(~scanf("%d %d", &N, &M))
96 {
97 if(!N) {puts("0"); continue;}
98 memset(G, 0, sizeof(G));
99 for(int i = 1; i <= M; i++)
100 {
101 int a, b;
102 scanf("%d %d", &a, &b);
103 G[a][b] = 1;
104 }
105
106 int ans = 0;
107 for(int i = 0; i < N; i++) a[i] = i + 1;
108 while(1)
109 {
110 init();
111 int S = N + N + 1, T = S + 1;
112 for(int i = 1; i <= N; i++) ad(S, i, 1), ad(N + i, T, 1);
113 for(int i = 1; i <= N; i++)
114 for(int j = 0; j < N; j++)
115 if(!G[i][a[j]] && !G[i][a[(j+1)%N]])
116 ad(i, N + 1 + j, 1);
117 ans = max(ans, Dinic(S, T));
118 if(!next_permutation(a + 1, a + N)) break;
119 }
120 printf("%d
", N - ans);
121 }
122 return 0;
123 }
Aguin
换匈牙利倒是快些。
![]()
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 int N, cnt, h[11];
7
8 struct edge
9 {
10 int to, pre;
11 } e[1111];
12
13 void init()
14 {
15 memset(h, -1, sizeof(h));
16 cnt = 0;
17 }
18
19 void add(int from, int to)
20 {
21 e[cnt].pre = h[from];
22 e[cnt].to = to;
23 h[from] = cnt;
24 cnt++;
25 }
26
27 // Hungary
28 int lk[11], vis[11];
29 bool dfs(int x)
30 {
31 for(int i = h[x]; i != -1; i = e[i].pre)
32 {
33 int to = e[i].to;
34 if(!vis[to])
35 {
36 vis[to] = 1;
37 if(lk[to] == -1 || dfs(lk[to]))
38 {
39 lk[to] = x;
40 return true;
41 }
42 }
43 }
44 return false;
45 }
46 int Hungary()
47 {
48 int ret = 0;
49 memset(lk, -1, sizeof(lk));
50 for(int i = 1; i <= N; i++)
51 {
52 memset(vis, 0, sizeof(vis));
53 if(dfs(i)) ret++;
54 }
55 return ret;
56 }
57
58
59 int a[11], G[11][11];
60 int main(void)
61 {
62 int M;
63 while(~scanf("%d %d", &N, &M))
64 {
65 if(!N) {puts("0"); continue;}
66 memset(G, 0, sizeof(G));
67 for(int i = 1; i <= M; i++)
68 {
69 int a, b;
70 scanf("%d %d", &a, &b);
71 G[a][b] = 1;
72 }
73
74 int ans = 0;
75 for(int i = 0; i < N; i++) a[i] = i + 1;
76 while(1)
77 {
78 init();
79 for(int i = 1; i <= N; i++)
80 for(int j = 0; j < N; j++)
81 if(!G[i][a[j]] && !G[i][a[(j+1)%N]])
82 add(i, 1 + j);
83 ans = max(ans, Hungary());
84 if(!next_permutation(a + 1, a + N)) break;
85 }
86 printf("%d
", N - ans);
87 }
88 return 0;
89 }
Aguin
1006 PowMod
1007 Rigid Frameworks
首先问题等价于求连通二分图数目。
据鸟神所说，m行n列的桁架，在第i行第j列加约束，使得：
①第i行的所有竖向杆件平行。
②第j列的所有横向杆件平行。
③第i行所有竖向杆件和第j列所有横向杆件垂直。
故只要对左边m个点，右边n个点建二分图，
只要二分图连通，则所有横向杆件平行，所有竖向杆件平行，所有横向杆件与所有纵向杆件垂直，即为刚体。
连通二分图计数问题，可以照着一般的连通图计数画葫芦。
参考：gyz营员交流
令$S(n, m)$为左边n个点，右边m个点的二分图数。
$F(n, m)$为左边n个点，右边m个点的连通二分图数。
$G(n, m) = S(n, m) - F(n, m)$
固定二分图左边的第一个点，考虑有多少个点与其连通，
$G(n, m) = sum_{i = 0}^{n - 1} sum_{j = 0, i + j
eq m + n - 1}^{m} C_{n-1}^{i}C_{m}^{j} F(i+1, j) S(n-i-1, m-j)$
而本题中对于i行j列的一个格子，可以选择不加约束，加左斜杠，加右斜杠。
故$S(n, m) = 3 ^ {nm}$
最后需要注意的是$F(n, m)$的边界条件。
![]()
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 typedef long long LL;
5 const LL mod = 1e9 + 7;
6 LL S[11][11], F[11][11], G[11][11];
7 LL c[11][11], p[111];
8
9 int main(void)
10 {
11 p[0] = 1LL;
12 for(int i = 1; i <= 100; i++) p[i] = p[i-1] * 3 % mod;
13
14 for(int i = 0; i <= 10; i++) c[i][0] = c[i][i] = 1;
15 for(int i = 1; i <= 10; i++)
16 for(int j = 1; j < i; j++)
17 c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
18
19 F[0][1] = F[1][0] = 1;
20 for(int i = 0; i <= 10; i++) S[0][i] = S[i][0] = 1;
21 for(int i = 1; i <= 10; i++)
22 for(int j = 1; j <= 10; j++)
23 {
24 for(int p = 0; p <= i - 1; p++)
25 for(int q = 0; q <= j && p + q != i + j - 1; q++)
26 G[i][j] = (G[i][j] + c[i-1][p] * c[j][q] % mod * F[p+1][q] % mod * S[i-p-1][j-q] % mod) % mod;
27
28 S[i][j] = p[i*j];
29 F[i][j] = (S[i][j] - G[i][j] + mod) % mod;
30 }
31
32
33 int m, n;
34 while(~scanf("%d %d", &m, &n)) printf("%I64d
", F[m][n]);
35 return 0;
36 }
Aguin
1008 Shell Necklace
1009 Solid Dominoes Tilings
1010 Subway
树同构，哈希一下就可以了。
题解的哈希方法以前看csy说过。
大概就是先找重心，每个点的孩子按哈希值排序算哈希值。
然而一开始两个素数随便取老冲突，于是以sz作为第二关键字排，就稳了。
![]()
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <vector>
5 #include <algorithm>
6 #include <map>
7 using namespace std;
8 typedef long long LL;
9 const int maxn = 2e5 + 10;
10 const LL P = 1e6 + 7, Q = 1e9 + 7;
11 int N;
12
13 map<string, int> M1, M2;
14 string name[maxn];
15
16 // edge
17 int cnt, h[maxn];
18 void init()
19 {
20 cnt = 0;
21 memset(h, 0, sizeof(h));
22 }
23 struct edge
24 {
25 int to, pre;
26 } e[maxn<<1];
27 void add(int from, int to)
28 {
29 cnt++;
30 e[cnt].pre = h[from];
31 e[cnt].to = to;
32 h[from] = cnt;
33 }
34
35
36 // Node
37 struct node
38 {
39 int id, sz;
40 LL h;
41 node(int I, LL H, int S): id(I), h(H), sz(S) {}
42 friend bool operator < (node A, node B)
43 {
44 if(A.h != B.h) return A.h < B.h;
45 return A.sz < B.sz;
46 }
47 };
48
49
50 // dfs
51 int sz[maxn], M;
52 vector<int> G;
53 void dfs1(int x, int f)
54 {
55 sz[x] = 1;
56 int tmp = 0;
57 for(int i = h[x]; i; i = e[i].pre)
58 {
59 int to = e[i].to;
60 if(to == f) continue;
61 dfs1(to, x);
62 sz[x] += sz[to];
63 tmp = max(tmp, sz[to]);
64 }
65 tmp = max(tmp, N - sz[x]);
66 if(tmp < M)
67 {
68 M = tmp;
69 G.clear();
70 G.push_back(x);
71 }
72 else if(tmp == M) G.push_back(x);
73 }
74
75
76 LL H[maxn];
77 vector<node> v[maxn];
78 void dfs2(int x, int f)
79 {
80 sz[x] = 1;
81 v[x].clear();
82 for(int i = h[x]; i; i = e[i].pre)
83 {
84 int to = e[i].to;
85 if(to == f) continue;
86 dfs2(to, x);
87 sz[x] += sz[to];
88 v[x].push_back(node(to, H[to], sz[to]));
89 }
90
91 sort(v[x].begin(), v[x].end());
92 H[x] = 0;
93 int sv = v[x].size();
94 LL c = P;
95 if(!sv) H[x] = 1;
96 for(int i = 0; i < sv; i++)
97 {
98 H[x] = (H[x] + v[x][i].h * c) % Q;
99 c = c * P % Q;
100 }
101 }
102
103 void dfs3(int x1, int x2)
104 {
105 cout << name[x1] << ' ' << name[x2] << endl;
106 int sv = v[x1].size();
107 for(int i = 0; i < sv; i++) dfs3(v[x1][i].id, v[x2][i].id);
108 }
109
110 int main(void)
111 {
112
113 ios::sync_with_stdio(0);
114
115 while(cin >> N)
116 {
117 init();
118 M1.clear(), M2.clear();
119 int num = 0;
120
121 for(int i = 1; i < N; i++)
122 {
123 string a, b;
124 cin >> a >> b;
125 if(!M1[a]) M1[a] = ++num, name[num] = a;
126 if(!M1[b]) M1[b] = ++num, name[num] = b;
127 add(M1[a], M1[b]), add(M1[b], M1[a]);
128 }
129
130 M = N + 1;
131 dfs1(1, 0);
132 dfs2(G[0], 0);
133 int rt1 = G[0];
134
135 for(int i = 1; i < N; i++)
136 {
137 string a, b;
138 cin >> a >> b;
139 if(!M2[a]) M2[a] = ++num, name[num] = a;
140 if(!M2[b]) M2[b] = ++num, name[num] = b;
141 add(M2[a], M2[b]), add(M2[b], M2[a]);
142 }
143
144 M = N + 1;
145 dfs1(N + 1, 0);
146 dfs2(G[0], 0);
147 int rt2 = G[0];
148 if(H[rt1] != H[G[0]]) dfs2(G[1], 0), rt2 = G[1];
149
150 dfs3(rt1, rt2);
151
152 }
153 return 0;
154 }
Aguin
1011 tetrahedron
