A. Raising Bacteria
数二进制位有多少个1就好了。
B. Finding Team Member
题意：
有 $2n$ 个人，任意两个人配对有一个价值，如果一人的目前的最优配对那个人的最优配对也是自己，那么两个人可以配对。
思路：
直接模拟，每次至少能让两个人配对成功。所以复杂度 $O(n ^ 2)$，刚开始用优先队列写了一发，发现RE了，以为是优先队列出锅了，最后才发现是数组开小了。
#include <bits/stdc++.h> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 840; priority_queue<pii> que[N]; int who[N]; int best[N][N]; int pos[N]; int main() { freopen("in.txt", "r", stdin); int n; scanf("%d", &n); for (int i = 2; i <= 2 * n; i++) { for (int j = 1; j < i; j++) { int x; scanf("%d", &x); que[i].push(pii(x, j)); que[j].push(pii(x, i)); } } for (int i = 1; i <= 2 * n; i++) { int cnt = 0; pos[i] = 1; while (!que[i].empty()) { best[i][++cnt] = que[i].top().se; que[i].pop(); } } while (1) { bool flag = 1; for (int i = 1; i <= 2 * n; i++) { if (who[i]) { pos[i] = 2 * n + 1; continue; } while (pos[i] <= 2 * n && who[best[i][pos[i]]]) pos[i]++; if (pos[i] <= 2 * n) { int ne = best[i][pos[i]]; while (pos[ne] <= 2 * n && who[best[ne][pos[ne]]]) pos[ne]++; if (pos[ne] <= 2 * n && best[ne][pos[ne]] == i) { pos[ne] = 2 * n + 1; pos[i] = 2 * n + 1; who[i] = ne; who[ne] = i; //printf("%d %d\n", i, ne); } } } //printf("%d\n", pos[2]); for (int i = 1; i <= 2 * n; i++) if (!who[i]) flag = 0; if (flag) break; } for (int i = 1; i <= 2 * n; i++) printf("%d%c", who[i], " \n"[i == 2 * n]); return 0; }
C. A Problem about Polyline
题意：
有一条折线，$(0,0)$ – $(x, x)$ – $(2x, 0)$ – $(3x, x)$ – $(4x, 0)$ – $\dots$ - $(2kx, 0)$ – $(2kx + x, x)$ - $\dots$
给出一个点 $(a, b)$，问存不存在最小的 $x$ 使得点 $(a, b)$ 在折线上。
思路：
$a < b$ 显然没有。
若答案存在，分为两种情况，点 $(a, b)$ 在奇数段和偶数段上。
在奇数段满足 $a - (k - 1)x = b$，即 $a - b = (k - 1)x$ $k$ 为奇数。
在偶数段满足 $a - kx = -b$， 即 $a + b = kx$, $k$ 为偶数。
把第一种情况的 $k$ 看成 $k - 1$，两个情况就只有左边不一样了。
分别求一下答案就行了。
#include <bits/stdc++.h> using namespace std; const double eps = 1e-10; inline int dcmp(double x) { if (fabs(x) <= eps) return 0; return x < 0 ? -1 : 1; } double get(int sum, int b) { int z = sum / b; while (z && (z & 1 || sum / z < b)) z--; if (!z) return -1; return 1.0 * sum / z; } int main() { int a, b; scanf("%d%d", &a, &b); if (a < b) { puts("-1"); return 0; } if (a == b) { printf("%d", b); puts(".0000000000000"); return 0; } double ans1 = get(a + b, b); double ans2 = get(a - b, b); if (fabs(ans1 + 1) == 0 && fabs(ans2 + 1) == 0) puts("-1"); else if (fabs(ans1 + 1) == 0) printf("%.10f\n", ans2); else if (fabs(ans2 + 1) == 0) printf("%.10f\n", ans1); else printf("%.10f\n", min(ans1, ans2)); return 0; }
D. "Or" Game
题意：
有 $n$ 个数，给你 $k$ 次操作，每次操作是任选一个数能给它乘上一个给的数 $x$。问最后所有数或起来最大为多少。
思路：
搞了半天DP，发现是错的。因为当前最优不一定能使后面最优。
发现乘法相当于让这个数二进制位往高处移，那么把这些操作分散给几个数肯定不比直接给一个数来的优。
所以直接枚举哪个数来乘上这个数就OK了。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 7; ll pre[N], last[N]; ll a[N]; int n, k; ll x; ll get(ll x, ll y, int cnt) { ll ans = x; while (cnt--) ans *= y; return ans; } int main() { freopen("in.txt", "r", stdin); scanf("%d%d%lld", &n, &k, &x); ll m = 1; while (k--) m *= x; for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), pre[i] = pre[i - 1] | a[i]; for (int i = n; i >= 1; i--) last[i] = last[i + 1] | a[i]; ll ans = 0; for (int i = 1; i <= n; i++) { ans = max(ans, pre[i - 1] | (a[i] * m) | last[i + 1]); } printf("%lld\n", ans); return 0; }
E. Weakness and Poorness
题意：
给一个序列，求一个 $x$ 使得这个序列每个数都减去 $x$ 后的子段和中绝对值最大的那个最小。
思路：
听起来很像数学中的函数，$x$ 做自变量，子段和做因变量，求一个极值，当 $x$ 很小时，最大子段和显然会很大，当 $x$ 很大时，数字变成负的很小，子段和取绝对值之后又会很大。
所以这个就是一个单峰函数。
三分极值点，$O(n)$ 求最大子段和，因为涉及绝对值，就可以所有数乘以-1再做一次，两次得到的值取最大值即可。
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 7; int n, a[N]; double k[N]; double f[N]; double check(double x) { for (int i = 1; i <= n; i++) k[i] = a[i] - x; f[1] = k[1]; double ans = f[1]; for (int i = 2; i <= n; i++) { f[i] = max(f[i - 1], 0.0) + k[i]; ans = max(ans, f[i]); } for (int i = 1; i <= n; i++) k[i] *= -1; f[1] = k[1]; ans = max(ans, f[1]); for (int i = 2; i <= n; i++) { f[i] = max(f[i - 1], 0.0) + k[i]; ans = max(ans, f[i]); } return ans; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); double l = -1e5, r = 1e5; for (int cnt = 0; cnt < 200; cnt++) { double ll = l + (r - l) / 3.0, rr = r - (r - l) / 3.0; if (check(ll) > check(rr)) l = ll; else r = rr; } printf("%.7f\n", check(l)); return 0; }
F. LCS Again
题意：
给一个串，长度为 $n$, 给出字符集大小，问能构造出多少长度为 $n$，并且LCS为 $n - 1$ 的串。
思路：
题解没看懂。讨论区的做法很妙。
构造过程就相当于在原串中拿一个位置的字符，再重新任意放回原串。
把颜色相同且连续的看成一段，假设长度为 $g$，字符为 $c$。那么从中取一个 $c$ 再变成任意一种字符放回原串，方案数为 $nm$
不过你不能把一个 $c$ 又放回这一段中，不合法的方案是 $g$。
假设有另外一段字符为 $d$ 长度为 $h$ 的子串，把 $c$ 变成 $d$ 再放入这个段显然只有一种放法。而总放法是 $h + 1$，那么不合法的方案是 $h$。
所以总共的不合法方案就是 $n$。所以对每一段的答案为 $nm - n$，如果有 $k$ 段，则答案为 $k(nm - n)$。
还有一种重复的情况，如 $ababa$ 变成 $babab$，可以是第一个字符变成 $b$ 放到最后，也可以是最后一个字符变成 $b$ 放到开头。
这种就是长度大于等于 $2$ 的，用了两种字符的就会重复。用了三种字符的就不会影响。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; char s[N]; int main() { int n, m; scanf("%d%d%s", &n, &m, s); long long ans = n * (m - 1); for (int i = 1; i < n; i++) if (s[i] != s[i - 1]) ans += n * (m - 1); int cur = 1; for (int i = 1; i < n; i++) { if (cur == 1) { if (s[i] == s[i - 1]) continue; else cur++; } else { if (s[i] == s[i - 2]) cur++; else { ans -= 1LL * cur * (cur - 1) / 2; if (s[i] == s[i - 1]) cur = 1; else cur = 2; } } printf("%d ", cur); } ans -= 1LL * cur * (cur - 1) / 2; printf("%lld\n", ans); return 0; }
Codeforces Round #320 (Div. 2) [Bayan Thanks-Round]
原文：https://www.cnblogs.com/Mrzdtz220/p/11674372.html
