D - Only one of two
https://atcoder.jp/contests/abc341/tasks/abc341_d
数论，二分求第K大
设 \(L\) 是 \(N\) 和 \(M\) 的最小公倍数。
那么，有 \(\lfloor \frac{X}{L}\rfloor\) 个不大于 \(X\) 的正整数能被 \(\lfloor \frac{X}{L}\rfloor\) 整除，因此有 \(\lfloor \frac{X}{N}\rfloor+\lfloor \frac{X}{M}\rfloor-2\times \lfloor \frac{X}{L}\rfloor\) 个整数 \(1\) 和 \(X\) （含）能被 \(N\) 和 \(M\) 中的一个整数整除。
此外，计数是随着 \(X\) 单调递增的，因此 "答案最多为 \(X\) "当且仅当" \(1\) 和 \(X\) 之间至少有 \(K\) 个整数正好能被 \(N\) 和 \(M\) 中的一个整数整除"，这又等价于 \(\lfloor \frac{X}{N}\rfloor+\lfloor \frac{X}{M}\rfloor-2\times \lfloor \frac{X}{L}\rfloor\geq K\) 。
因此，可以利用这一性质通过二分搜索来解决这个问题。在此问题的约束条件下，答案总是最多为 \(2\times 10^{18}\) ，因此在开始二进制搜索时，可以将下界和上界分别设为 \(0\) 和 \(2\times 10^{18}\) 。
更具体地说，我们可以设置 \(L=0\) 和 \(R=2\times 10^{18}\) ，并在 \(R-L\geq 2\) 时重复下面的过程。
- 让 \(X=\lfloor \frac{L+R}{2}\rfloor\) .
- 如果是 \(\lfloor \frac{X}{N}\rfloor+\lfloor \frac{X}{M}\rfloor-2\times \lfloor \frac{X}{L}\rfloor\geq K\) ，则设为 \(R=X\) ；否则，设为 \(L=X\) 。
答案就是结果 \(R\) 。
对于固定的 \(X\) ，可以在 \(O(1)\) 次内确定是否 \(\lfloor \frac{X}{N}\rfloor+\lfloor \frac{X}{M}\rfloor-2\times \lfloor \frac{X}{L}\rfloor\geq K\) ，迭代循环最多 \(60\) 次。因此，问题已经解决。
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
i64 n, m, k;
std::cin >> n >> m >> k;
i64 lo = 0, hi = 2E18;
i64 L = std::lcm(n, m);
while (lo <= hi) {
i64 mid = lo + hi >> 1;
if ((mid / n) + (mid / m) - 2 * (mid / L) < k) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
std::cout << hi + 1 << '\n';
return 0;
}
E - Alternating String
https://atcoder.jp/contests/abc341/tasks/abc341_e
转化题意再用线段树维护
考虑线段树要维护什么信息
对于长度为 \((N-1)\) 的序列 \(A=(A_1,A_2,\ldots,A_{N-1})\)，如果 \(S_i=S_{i+1}\)，则令 \(A_i=0\)；如果 \(S_i\neq S_{i+1}\)，则令 \(A_i=1\)。
-
那么，第一类型的查询
1 L R会将 \(A\) 修改为 \(A_{L-1}\leftarrow (1-A_{L-1})\) 和 \(A_R\leftarrow (1-A_R)\)。
在这里，如果 \(L=1\) 或 \(R=N\)，则前者或后者的更新是不必要的。 -
另一方面，第二类型的查询
2 L R若 \(A_L=A_{L+1}=\cdots=A_{R-1}=1\)，则输出Yes，否则输出No。注意到每个 \(A_i\) 取值为 \(0\) 或 \(1\)，可以通过判断 \(A_L+A_{L+1}+\cdots+A_{R-1}=R-L\) 来决定输出是否为
Yes。
这些操作可以通过线段树实现。
每种查询都可以在 \(O(\log N)\) 的时间内完成，因此总共可以在 \(O(Q\log N)\) 的时间内解决问题，这足够快速。
在实现上述算法时，需要注意当 \(N=1\) 时可能需要的异常处理，此时 \(A\) 的长度为 \(0\)。可以编写异常处理程序，或者分配稍长的 \(A\)。
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::string s;
std::cin >> s;
SegmentTree<Info> T(n);
for (int i = 0; i + 1 < n; i++) {
if (s[i] != s[i + 1]) {T.modify(i, 1);}
else {T.modify(i, 0);}
}
for (int i = 0, x, l, r; i < m; i++) {
std::cin >> x >> l >> r; --l;
if (x == 1) {
if (l > 0) {T.modify(l - 1, 1 - T.rangeQuery(l - 1, l).sum);}
if (r < n) {T.modify(r - 1, 1 - T.rangeQuery(r - 1, r).sum);}//注意这里是r - 1，因为r是开区间
} else {
std::cout << (T.rangeQuery(l, r - 1).sum == r - l - 1 ? "Yes" : "No") << '\n';
}
}
return 0;
}
F - Breakdown
设 \(\mathrm{dp}[v]\) 为从顶点 \(v\) 放置棋子开始，可执行的最大操作数，即顶点 \(v\) 上棋子的最大贡献。如果对于所有 \(v = 1, 2, \ldots, N\) 都找到了这个值，那么答案就是 \(\sum_{v =1}^N \mathrm{dp}[v] \times A_v\)。以下是我们尝试用动态规划（DP）来找到 \(\mathrm{dp}[\ast]\) 的方法。
如果您从顶点 \(v\) 移除一个棋子，并且棋子放置在集合 \(S\) 中的顶点上，那么对于每个 \(u \in S\) 的顶点，可以执行 \(\mathrm{dp}[u]\) 次操作，总共可以执行 \(\sum_{u \in S} \mathrm{dp}[u]\) 次。因此，选择 \(S\) 以最大化 \(\sum_{u \in S} \mathrm{dp}[u]\) 是足够的；换句话说，
\[\mathrm{dp}[v] = 1 + \max_S \sum_{u \in S} \mathrm{dp}[u] \tag{1}. \]这里，\(S\) 是任何可能为空的与 \(v\) 相邻的顶点集合，使得 \(\sum_{u \in S} W_u < W_v\)。
由于 \(S\) 只能包含 \(W_u < W_v\) 的顶点 \(u\)，所以方程（1）的右侧只由 \(W_u < W_v\) 的顶点 \(u\) 组成，因此可以按 \(W_v\) 的升序依次找到所有 \(v\) 的 \(\mathrm{dp}[v]\)。
对于固定的 \(v\)，方程（1）的右侧可以视为以下背包问题：
对于与 \(v\) 相邻的每个顶点 \(u_1, u_2, \ldots, u_{\deg(v)}\)，\(u_i\) 的 价值 为 \(\mathrm{dp}[u_i]\)，其 成本 为 \(W_{u_i}\)。在总成本为 \(W_v\) 的约束下，最大化所选顶点的总价值。
这可以通过 DP 在 \(O(\deg(v) \times W_v)\) 时间内解决。
由于
\[\sum_{v = 1}^N \deg(v) W_v \leq W_{\max} \sum_{v = 1}^N \deg(v) = W_{\max} \times 2M, \]其中 \(W_{\max} \coloneqq \max \lbrace W_1, W_2, \ldots, W_N \rbrace\)，因此可以总共在 \(O(MW_{\max})\) 时间内解决上述背包问题
signed main() {
int N, M;
std::cin >> N >> M;
std::vector adj(N, std::vector<int>());
for (int i = 0, u, v; i < M; i++) {
std::cin >> u >> v; --u; --v;
adj[u].push_back(v); adj[v].push_back(u);
}
std::vector<int> W(N), A(N);
for (auto& x : W) {std::cin >> x;}
for (auto& x : A) {std::cin >> x;}
std::vector<int> p(N);//维护点权对应的下标
std::iota(all(p), 0);
std::sort(all(p), [&](int i, int j){return W[i] < W[j];});
std::vector<int> dp(N);
for (auto& x : p) {//按照W[i]升序更新
std::vector<int> f(W[x]);//找到当前容积下能放入的最大点数
for (auto& y : adj[x]) if (W[y] < W[x]) {
for (int i = W[x] - 1; i >= W[y]; i--) {
f[i] = std::max(f[i], f[i - W[y]] + dp[y]);
}
}
dp[x] = 1 + f[W[x] - 1];
}
i64 ans = 0;
for (int i = 0; i < N; i++) {ans += 1LL * A[i] * dp[i];}
std::cout << ans << '\n';
return 0;
}