2017-2018 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2017)
$f[i][k]$ 表示在第 $i$ 个位置刚好匹配了 $k$ 个字符。转移方程 $$ f[i][k] = \sum_{i - j > h[s[k - 1]]} f[j][k - 1] $$
前缀和优化加滚动就行了。
好像可以直接用 $f[i][k]$ 表示前缀和，就没这么多事了。
#include <bits/stdc++.h> const int N = 1e5 + 7; const int MOD = 1e9 + 7; int dp[2][N], sum[2][N], h[N]; char s[N], t[N]; void M(int &a) { if (a >= MOD) a -= MOD; } int main() { freopen("in.txt", "r", stdin); int k, n; scanf("%d%d", &k, &n); for (int i = 0; i < 26; i++) scanf("%d", h + i); scanf("%s%s", t + 1, s + 1); for (int i = 1; i <= n; i++) { if (s[i] == t[1]) dp[1][i] = 1; sum[1][i] = sum[1][i - 1] + dp[1][i]; } for (int j = 2; j <= k; j++) { int cur = j & 1, pre = cur ^ 1; memset(dp[cur], 0, sizeof(dp[cur])); memset(sum[cur], 0, sizeof(sum[cur])); for (int i = 1; i <= n; i++) { if (s[i] == t[j]) { int where = i - h[t[j - 1] - ‘A‘] - 1; if (where > 0) M(dp[cur][i] += sum[pre][where]); } //if (i == 2) printf("%d\n", dp[cur][i]); M(sum[cur][i] += sum[cur][i - 1]); M(sum[cur][i] += dp[cur][i]); } } printf("%d\n", sum[k & 1][n]); return 0; }
D - Harry Potter and The Vector Spell
并查集合并每一列中两个 $1$，不在同一个集合里则对答案贡献为 $1$
#include <bits/stdc++.h> const int N = 1e5 + 7; int fa[N]; int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); } std::vector<int> G[N]; int main() { int n, m; scanf("%d%d", &m, &n); for (int i = 1; i <= m; i++) { fa[i] = i; int k; scanf("%d", &k); while (k--) { int u; scanf("%d", &u); G[u].push_back(i); } } int ans = 0; for (int i = 1; i <= n; i++) { if (G[i].size() == 0) continue; if (G[i].size() == 1) { ans++; continue; } int u = G[i][0], v = G[i][1]; u = getfa(u); v = getfa(v); if (u != v) { ans++; fa[u] = v; } } printf("%d\n", ans); }
贪心地考虑，先把不匹配的 $1$ 从大到小消掉，再把不匹配的 $0$ 从小到大加上。但是如果存在一些匹配了的 $1$ 它们的花费特别大，就不是最优的。
那么就枚举多消去几个已经匹配了的 $1$，这部分肯定也是从大到小优。
用multiset维护即可。
#include <bits/stdc++.h> #define ll long long const int N = 1e4 + 7; std::multiset<ll, std::greater<ll> > st1; std::multiset<ll> st2; std::vector<ll> vec; int n; ll c[N]; ll sum; char a[N], b[N]; ll solve(int cnt) { ll ans = 0; ll s = sum; if (cnt) st1.insert(vec[cnt - 1]), st2.insert(vec[cnt - 1]); for (auto it: st1) { s -= it; ans += s; } for (auto it: st2) { s += it; ans += s; } return ans; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", c + i); scanf("%s", a + 1); scanf("%s", b + 1); for (int i = 1; i <= n; i++) { if (a[i] != b[i]) { if (a[i] == ‘1‘) st1.insert(c[i]); else st2.insert(c[i]); } else { if (a[i] == ‘1‘) vec.push_back(c[i]); } if (a[i] == ‘1‘) sum += c[i]; } std::sort(vec.begin(), vec.end(), std::greater<ll>()); ll ans = 1e18; for (int i = 0; i <= vec.size(); i++) ans = std::min(ans, solve(i)); printf("%lld\n", ans); return 0; }
#include <bits/stdc++.h> #define ll long long const int N = 1e4 + 7; struct In { ll a, t; bool operator < (const In &rhs) const { return a > rhs.a; } } in[N]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld%lld", &in[i].a, &in[i].t); ll v = 0; double ans1 = 0; for (int i = 0; i < n; i++) { ans1 += v * in[i].t + 0.5 * in[i].a * in[i].t * in[i].t; v += in[i].a * in[i].t; } std::sort(in, in + n); v = 0; double ans = 0; for (int i = 0; i < n; i++) { ans += v * in[i].t + 0.5 * in[i].a * in[i].t * in[i].t; v += in[i].a * in[i].t; } printf("%.1f\n", ans - ans1); return 0; }
三个人的nim...
如果全是 $1$，那么 $n \equiv 0$ (mod $3$）时必输，否则必胜。
如果只有一个不是 $1$，如果 $n \equiv 0$ (mod $3$），第一个人把 非 $1$ 那堆取出 $1$ 就必胜，否则把那一堆取光。
如果有两个不是 $1$，且至少有一个 $2$ 并且 $1$ 的个数不是 $3$ 的倍数，第一个人都可以把一堆取光或者取剩下 $1$ 使得自己赢，否则必败，另外两个人都可以让 $n \equiv 0$ (mod $3$）
如果大于两个，另外两个人的操作空间比第一个人大，就可以让第一个人必败了。
#include <bits/stdc++.h> int main() { int n; int cnt1 = 0, cnt2 = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); if (x == 1) cnt1++; else if (x == 2) cnt2++; } if (cnt1 == n) puts(n % 3 == 0 ? "Lose" : "Win"); else if (cnt1 == n - 1) puts("Win"); else if (cnt1 == n - 2) puts((cnt2 && cnt1 % 3 != 0) ? "Win" : "Lose"); else puts("Lose"); }
对于 $n$ 它的最长上升子序列肯定是 $1$，对于 $n-1$，如果它在 $n$ 后面那么肯定是 $1$，如果在 $n$ 前面那么肯定是 $2$，但是放后面会使得字典序更小。
那么就按最长上升子序列的值排个序。值小的放大的数，同权值的，越靠前面的放越大的数才符合最长上升子序列的值。
#include <bits/stdc++.h> const int N = 1e5 + 7; struct In { int pos, val; bool operator < (const In &rhs) const { if (val == rhs.val) return pos < rhs.pos; return val < rhs.val; } } in[N]; int ans[N]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &in[i].val); in[i].pos = i; } std::sort(in + 1, in + 1 + n); for (int i = 1; i <= n; i++) ans[in[i].pos] = n - i + 1; for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]); return 0; }
总边数是 $4(n-1)$，至少存在一个点的度数不超过 $3$，那么答案肯定不超过 $3$，并且有一棵树的只割去一条边。
枚举 $A$ 树中每一条边作为割边，在 $B$ 树中这条边连接的两个端点在 $A$ 树中不在一个连通块中，那么这条边需要割掉。
树上启发式合并解决。
#include <bits/stdc++.h> #define pii pair<int, int> const int N = 1e5 + 7; struct Tree { std::vector<int> G[N]; int son[N], sz[N]; inline void add(int u, int v) { G[u].push_back(v); G[v].push_back(u); } void dfs(int u, int fa) { sz[u] = 1; for (auto v: G[u]) { if (v == fa) continue; dfs(v, u); sz[u] += sz[v]; if (sz[son[u]] < sz[v]) son[u] = v; } } } a, b; bool skip[N], color[N]; int cur, n; void cal(int u, const Tree &a) { color[u] ^= 1; for (auto v: a.G[u]) if (color[v] != color[u]) cur++; else cur--; } void edt(int u, int fa, const Tree &a, const Tree &b) { cal(u, b); for (auto v: a.G[u]) if (v != fa && !skip[v]) edt(v, u, a, b); } void dfs(int u, int fa, bool keep, const Tree &a, const Tree &b, std::pii &ans) { for (auto v: a.G[u]) if (v != fa && v != a.son[u]) dfs(v, u, 0, a, b, ans); if (a.son[u]) dfs(a.son[u], u, 1, a, b, ans), skip[a.son[u]] = 1; edt(u, fa, a, b); if (fa) { if (cur < ans.first) ans = std::pii(cur, 0); if (ans.first == cur) ans.second++; } if (a.son[u]) skip[a.son[u]] = 0; if (!keep) edt(u, fa, a, b); } std::pii solve(Tree &a, Tree &b) { a.dfs(1, 0); std::pii ans = std::pii(n, 0); dfs(1, 0, 0, a, b, ans); ans.first++; return ans; } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); a.add(u, v); } for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); b.add(u, v); } auto ans = solve(a, b); if (ans.first == 2) return 0 * printf("%d %d\n", 2, ans.second); cur = 0; auto res = solve(b, a); cur = 0; if (ans.first == 3) cur += ans.second; if (res.first == 3) cur += res.second; printf("%d %d\n", 3, cur); return 0; }
2017-2018 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2017)
原文：https://www.cnblogs.com/Mrzdtz220/p/11664575.html
