1004.Tokitsukaze and Multiple
求和为p的倍数的块的最大数量，我用了比较暴力的做法，好像有dp的做法？
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) int n, p; int f, ans, flag; inline void solve() { cin >> n >> p; vector<int> a; ans = 0; rep(i, 1, n) { cin >> f; flag = 0; if (f % p == 0) flag = 1; else for (vector<int>::iterator it = a.begin(); it != a.end(); it++) { *it += f; if (*it % p == 0) { flag = 1; break; } } if (flag) { ans++; a.clear(); } else a.push_back(f); } cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } }
1005.Little W and Contest
并查集维护块的数量，每合并一个块减去对应产生的贡献。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) int mod = 1e9 + 7; int pre[100010]; int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); } int n, a[100010]; int u, v; int cnt1, cnt2, s1[100010], s2[100010]; ll ans; inline void solve() { cin >> n; cnt1 = cnt2 = 0; rep(i, 1, n) { cin >> a[i]; pre[i] = i; if (a[i] == 1) { s1[i] = 1; s2[i] = 0; cnt1++; } else { s1[i] = 0; s2[i] = 1; cnt2++; } } ans = 1ll * cnt2 * (cnt2 - 1) * (cnt2 - 2) / 6 + 1ll * cnt2 * (cnt2 - 1) * cnt1 / 2; cout << ans % mod << endl; rep(i, 1, n - 1) { cin >> u >> v; u = find(u); v = find(v); ans -= 1ll * s2[u] * s2[v] * (cnt2 - s2[u] - s2[v]); ans -= 1ll * s2[u] * s2[v] * (cnt1 - s1[u] - s1[v]); ans -= 1ll * s1[u] * s2[v] * (cnt2 - s2[u] - s2[v]); ans -= 1ll * s2[u] * s1[v] * (cnt2 - s2[u] - s2[v]); pre[u] = v; s1[v] += s1[u]; s2[v] += s2[u]; cout << ans % mod << endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } }
1007.Tokitsukaze and Rescue
边权随机的情况下，最短路的边数很少？
求出最短路，再依次删除这条路所有边，递归求解。
复杂度为求最短路的复杂度*最短路边数的k次方
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) int n, k; int mp[55][55], u, v, w; int d[55], vis[55], f[10][55]; int ans; void dfs(int step) { rep(i, 0, n) { d[i] = 100000000; vis[i] = 0; f[step][i] = 0; } d[1] = 0; rep(i, 1, n) { int k = 0; rep(j, 1, n) if (!vis[j] && d[j] < d[k]) k = j; vis[k] = 1; rep(j, 1, n) if (!vis[j] && d[k] + mp[j][k] < d[j]) { d[j] = d[k] + mp[j][k]; f[step][j] = k; } } if (step == 0) { ans = max(d[n], ans); return; } for (int i = n, j, k; i != 1; i = j) { j = f[step][i]; k = mp[i][j]; mp[i][j] = mp[j][i] = 100000000; dfs(step - 1); mp[i][j] = mp[j][i] = k; } } inline void solve() { cin >> n >> k; rep(i, 1, n * (n - 1) / 2) { cin >> u >> v >> w; mp[u][v] = mp[v][u] = w; } ans = 0; dfs(k); cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } }
1009.Parentheses Matching
将'*'换成 '('，')'或' '，求最短的，字典序最小的平衡字符串。
先将左右括号的个数整相等，再判断字符串合不合法，不合法再成对的改变*号
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) char s[100010]; int cnt1, cnt2, num, sum[100010]; int tmp[100010], l, r, id; inline void solve() { cin >> s; int n = strlen(s); l = 1; cnt1 = cnt2 = r = 0; rep(i, 0, n - 1) if (s[i] == '(') cnt1++; else if (s[i] == ')') cnt2++; else tmp[++r] = i; if (abs(cnt2 - cnt1) > r) { puts("No solution!"); return; } if (cnt1 > cnt2) rep(i, 1, cnt1 - cnt2) s[tmp[r--]] = ')'; if (cnt1 < cnt2) rep(i, 1, cnt2 - cnt1) s[tmp[l++]] = '('; num = 0; rep(i, 0, n - 1) { if (s[i] == '*') continue; else if (s[i] == '(') num++; else if (s[i] == ')') num--; if (num < 0) { if (l >= r || tmp[l] > i) { puts("No solution!"); return; } s[tmp[l++]] = '('; s[tmp[r--]] = ')'; num = 0; } } if (num != 0) { puts("No solution!"); return; } rep(i, 0, n - 1) if (s[i] == '*') continue; else putchar(s[i]); puts(""); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } }