#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint N = 1e5 + 10; int par[N], rk[N]; voidinit(int n){ for (int i = 0; i <= n; i++)par[i] = i, rk[i] = 0; } intfind(int x){ return par[x] == x ? x : par[x] = find(par[x]); } voiduni(int x, int y){ x = find(x), y = find(y); if (x == y)return; if (rk[x] < rk[y])par[x] = y; else { par[y] = x; if (rk[x] == rk[y])rk[x]++; } } int n, m, q; int w[3010][3010]; structE { int u, v, w; booloperator<(const E& b)const { return w < b.w; } }; vector<E>es; vector<int>G[3010]; int dp[3010][3010], inMst[3010][3010]; intdfs(int rt, int u, int _fa){ int s = _fa == rt || _fa == -1 ? INF : w[rt][u]; for (int v : G[u]) { if (v == _fa)continue; int tmp = dfs(rt, v, u); s = min(s, tmp); dp[u][v] = dp[v][u] = min(dp[u][v], tmp); } return s; } intmain(){ while (scanf("%d%d", &n, &m) == 2 && n) { es.clear(); init(n); for (int i = 0; i < n; i++)G[i].clear(); memset(dp, 0x3f, sizeof(dp)); memset(w, 0x3f, sizeof(w)); memset(inMst, 0, sizeof(inMst)); for (int i = 0; i < m; i++) { int u, v, g; scanf("%d%d%d", &u, &v, &g); w[u][v] = w[v][u] = g; es.push_back(E{ u,v,g }); } int mst = 0; sort(es.begin(), es.end()); for (E e : es) { int u = e.u, v = e.v; if (find(u) != find(v)) { uni(u, v); inMst[u][v] = inMst[v][u] = 1; mst += e.w; G[u].push_back(v); G[v].push_back(u); } } for (int i = 0; i < n; i++)dfs(i, i, -1); int ans = 0; scanf("%d", &q); for (int i = 0; i < q; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); if (!inMst[u][v])ans += mst; else { ans += mst - w[u][v] + min(c, dp[u][v]); } } printf("%.4lf\n", 1.0*ans / q); } return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint N = 1e7 + 10; const ll mod = 1000000007; int par[N]; intfind(int x){ return par[x] == x ? x : par[x] = find(par[x]); } voidinit(int n){ for (int i = 0; i <= n; i++)par[i] = i; } voiduni(int x, int y){ x = find(x), y = find(y); if (x == y)return; par[x] = y; } int n, m; ll Pow(ll a, int b){ ll res = 1; while (b) { if (b & 1)res = res * a%mod; a = a * a%mod; b >>= 1; } return res; } intmain(){ while (~scanf("%d%d", &n, &m)) { init(n); int ans = 0; for (int i = 0; i < m; i++) { int l, r; scanf("%d%d", &l, &r); l--; if (find(l) != find(r))ans++, uni(l, r); } printf("%lld\n", Pow(26, n - ans)); } return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint N = 1e5 + 10; int par[N], rk[N]; intfind(int x){ return par[x] == x ? x : par[x] = find(par[x]); } voidinit(int n){ for (int i = 0; i <= n; i++)par[i] = i, rk[i] = 0; } voiduni(int x, int y){ x = find(x), y = find(y); if (x == y)return; if (rk[x] < rk[y])par[x] = y; else { par[y] = x; if (rk[x] == rk[y])rk[x]++; } } int n, m; structE { int u, v, w; }; vector<E>es; boolcmp(const E& a, const E& b){ return a.w > b.w; } int cir[N]; intmain(){ while (scanf("%d%d", &n, &m) == 2 && n) { es.clear(); init(n); fill(cir, cir + n, 0); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); es.push_back(E{ u,v,w }); } sort(es.begin(), es.end(), cmp); int ans = 0; for (E e : es) { int u = e.u, v = e.v; u = find(u), v = find(v); if (u == v) { if (cir[u])continue; ans += e.w; cir[u] = 1; } else { if (cir[u] && cir[v])continue; uni(u, v); ans += e.w; if (cir[u] || cir[v])cir[find(u)] = 1; } } printf("%d\n", ans); } return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<int, int> pii; constint INF = 0x3f3f3f3f; constint N = 1e7 + 10; const ll mod = 1000000007; int par[N], rk[N]; intfind(int x){ return par[x] == x ? x : par[x] = find(par[x]); } voidinit(int n){ for (int i = 0; i <= n; i++)par[i] = i, rk[i] = 0; } voiduni(int x, int y){ x = find(x), y = find(y); if (x == y)return; if (rk[x] < rk[y])par[x] = y; else { par[y] = x; if (rk[x] == rk[y])rk[x]++; } } int n, m; int p[N], vis[N]; intmain(){ int tt = 0; while (scanf("%d%d", &n, &m) == 2 && n) { init(n); for (int i = 0; i < n; i++) p[i] = i; int tot = n; for (int i = 0; i < m; i++) { char op; int x, y; scanf(" %c", &op); if (op == 'M') { scanf("%d%d", &x, &y); uni(p[x], p[y]); } else { scanf("%d", &x); p[x] = tot++; par[p[x]] = p[x]; } } int ans = 0, tmp; fill(vis, vis + tot, 0); for (int i = 0; i < n; i++) { if (!vis[tmp = find(p[i])])ans++, vis[tmp] = 1; } printf("Case #%d: %d\n", ++tt, ans); } return0; }
Zjnu Stadium
题意:有300列座位,每列有无限个座位,某些给出人之间隔了几列,问给出的数据有多少是错的。
带权并查集
已知A在B右边k列,就可以记为A=B+k,并查集维护每个点到根的距离,合并时要关注两个根之间的关系,在本题中就是d[f1] = z + d[y] - d[x],一维直线上画一下图就能得到。
#include<bits/stdc++.h> usingnamespace std; #define ll long long constint INF = 0x3f3f3f3f; constint N = 1e5 + 10; int par[N], d[N]; voidinit(int n){ for (int i = 0; i <= n; i++)par[i] = i, d[i] = 0; } intfind(int x){ if (par[x] == x)return x; int fa = par[x]; par[x] = find(par[x]); d[x] += d[fa]; return par[x]; } voiduni(int x, int y, int f1, int f2, int z){ par[f1] = f2; d[f1] = z + d[y] - d[x]; } intquery(int x){ if (par[x] == x)return d[x]; return d[x] + query(par[x]); } int n, m; intmain(){ while (scanf("%d%d", &n, &m) == 2) { init(n); int ans = 0; while (m--) { int x, y, z; scanf("%d%d%d", &x, &y, &z); int f1 = find(x), f2 = find(y); if (f1 == f2) { if (d[x] - d[y] != z)ans++; } else { uni(x, y, f1, f2, z); } } printf("%d\n", ans); } return0; }
How Many Answers Are Wrong
题意:给出一个区间的长度 N,及 M 个子区间和, 形如:x y z, 表示
子区间 [x, y] 的和为 z
如果一个“子区间和”与前面的“子区间和”冲突,即为错误(而且这个“子区间和”将在接下来的判断中被忽略)。
求总错误个数。
#include<bits/stdc++.h> usingnamespace std; #define ll long long constint INF = 0x3f3f3f3f; constint N = 2e5 + 10; int par[N]; ll d[N]; voidinit(int n){ for (int i = 0; i <= n; i++)par[i] = i, d[i] = 0; } intfind(int x){ if (par[x] == x)return x; int fa = par[x]; par[x] = find(par[x]); d[x] += d[fa]; return par[x]; } voiduni(int x, int y, int f1, int f2, ll z){ par[f1] = f2; d[f1] = z + d[y] - d[x]; } int n, m; intmain(){ while (scanf("%d%d", &n, &m) == 2) { init(n); int ans = 0; while (m--) { int x, y; ll z; scanf("%d%d%lld", &x, &y, &z); x--; int f1 = find(x), f2 = find(y); if (f1 == f2) { if (d[x] - d[y] != z)ans++; } else { uni(x, y, f1, f2, z); } } printf("%d\n", ans); } return0; }
Exclusive-OR
题意:
存在一个不会变化的,未知的长度为 n 的数列 x, 每个数都不超过 2^20, 有 3 种操作:
I p v 告诉你某个元素 x[p] 的值为 v
I p q v 告诉你某个元素 x[p] 和另一个元素 x[q] 的异或值 v(即 x[p] xor x[q] = v)
Q k p1 p2 ...pk 查询 k 个元素的异或值(即 x[p1] xor x[p2] xor ... xor x[pk]), k 不超过 15
#include<bits/stdc++.h> usingnamespace std; #define ll long long constint N = 1e5 + 10; constint M = 1e6 + 10; constint INF = 0x3f3f3f3f; structE { int u, v, w; }es[M]; int n, m, rt, mn[N], fa[N], tp[N], lp[N]; intzl(int n, int rt){ int ans = 0, tot = 0; while (1) { for (int i = 1; i <= n; i++)mn[i] = INF, fa[i] = tp[i] = lp[i] = 0; for (int i = 1, v, w; i <= m; i++) if (es[i].u != es[i].v && (w = es[i].w) < mn[v = es[i].v]) mn[v] = w, fa[v] = es[i].u; mn[rt] = 0; for (int u = 1; u <= n; u++) { ans += mn[u]; if (mn[u] == INF)return-1; } for (int u = 1, v = 1; u <= n; u++, v = u) { while (v != rt && tp[v] != u && !lp[v])tp[v] = u, v = fa[v]; if (v != rt && !lp[v]) { lp[v] = ++tot; for (int k = fa[v]; k != v; k = fa[k])lp[k] = tot; } } if (!tot)return ans; for (int i = 1; i <= n; i++)if (!lp[i])lp[i] = ++tot; for (int i = 1; i <= m; i++) es[i].w -= mn[es[i].v], es[i].u = lp[es[i].u], es[i].v = lp[es[i].v]; n = tot, rt = lp[rt], tot = 0; } } int X, Y, Z; int a[N], b[N], c[N]; intdis(int i, int j){ returnabs(a[i] - a[j]) + abs(b[i] - b[j]) + abs(c[i] - c[j]); } intmain(){ while (scanf("%d%d%d%d", &n, &X, &Y, &Z) == 4 && n) { rt = n + 1, m = 0; for (int i = 1; i <= n; i++) { scanf("%d%d%d", &a[i], &b[i], &c[i]); es[++m] = E{ rt,i,X*c[i] }; } for (int i = 1; i <= n; i++) { int k; scanf("%d", &k); for (int j = 1; j <= k; j++) { int v; scanf("%d", &v); es[++m] = E{ i,v,dis(i,v)*Y + (c[v] > c[i] ? Z : 0) }; } } int ans = zl(n + 1, n + 1); if (ans == -1)puts("poor XiaoA"); elseprintf("%d\n", ans); } return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long constint N = 1e3 + 10; constint M = 1e6 + 10; constint INF = 0x3f3f3f3f; int T; int n, m, k, K; structE { int v, w; }; vector<E>G[N]; int f[1 << 10][60], dp[1 << 10]; queue<int>q; int inq[N]; voidspfa(int* dis){ while (!q.empty()) { int u = q.front(); q.pop(); for (E e:G[u]) { int v = e.v, w = e.w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!inq[v]) { q.push(v); inq[v] = 1; } } } inq[u] = 0; } } boolcheck(int s){ int cnt = 0; for (int i = 0; i < K; i++) { if (s&(1 << i)) { if (i < k)cnt++; else cnt--; } } return cnt == 0; } intmain(){ cin >> T; while (T--) { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; i++)G[i].clear(); memset(f, 0x3f, sizeof(f)); memset(dp, 0x3f, sizeof(dp)); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); u--, v--; G[u].push_back(E{ v,w }); G[v].push_back(E{ u,w }); } K = 2 * k; for (int i = 0; i < k; i++) { f[(1 << i)][i] = 0; f[1 << (K - i - 1)][n - i - 1] = 0; } for (int s = 1; s < (1 << K); s++) { for (int i = 0; i < n; i++) { for (int t = s & (s - 1); t; t = (t - 1)&s) { f[s][i] = min(f[s][i], f[t][i] + f[s - t][i]); } if (f[s][i] != INF)q.push(i), inq[i] = 1; } spfa(f[s]); } for (int sta = 1; sta < (1 << K); sta++) { for (int i = 0; i < n; i++) dp[sta] = min(dp[sta], f[sta][i]); } for (int sta = 1; sta < (1 << K); sta++) if (check(sta)) for (int s = sta & (sta - 1); s; s = sta & (s - 1)) if (check(s)) dp[sta] = min(dp[sta], dp[s] + dp[sta - s]); if (dp[(1 << K) - 1] == INF)puts("No solution"); elseprintf("%d\n", dp[(1 << K) - 1]); } return0; }
Interviewe
题意:共 n 个人,分成 m 块,每块 ⌊mn⌋ 个人,后面的不要,每块取最大值,要求总和大于 s,问 m 最小值。
分块+倍增RMQ
首先枚举分成 1 到 n 组,期间若有满足条件的,直接输出。
以上已经枚举完了每组为 n 到 n 的情况,还剩下每组为 1 到 n 的情况,直接枚举每组人数。但是要注意对于每组为 k 的情况,组数 m 可能有多值,例如:共12人,分5组和分6组,每组都是2人。所以在枚举每组为2人的情况时,如果分5组就能解决问题,就不要再看分6组的了,12个人中后面的2个就不要了。
#include<bits/stdc++.h> usingnamespace std; #define ll long long constint N = 2e5 + 10; constint INF = 0x3f3f3f3f; int n, s; int mx[N][25]; voidini(int n){ for (int i = 1; i < 25; i++) { //1e7 for (int j = 1; j + (1 << i) - 1 <= n; j++) { mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]); } } } intrmq(int a, int b){ int len = log2(b - a + 1); returnmax(mx[a][len], mx[b - (1 << len) + 1][len]); } intcheck(int k){ int sum = 0, cnt = 0; for (int i = 1; i + k - 1 <= n; i += k) { cnt++; sum += rmq(i, i + k - 1); if (sum > s)return cnt; } return-1; } intmain(){ while (scanf("%d%d", &n, &s) == 2 && n > 0) { for (int i = 1; i <= n; i++)scanf("%d", &mx[i][0]); int ans = -1; ini(n); for (int i = 1; i <= sqrt(1.0*n); i++) { ans = check(n / i); if (ans != -1)break; } if (ans == -1) { for (int i = sqrt(1.0*n); i >= 1; i--) { ans = check(i); if (ans != -1)break; } } printf("%d\n", ans); } return0; }