ABC341

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) 时重复下面的过程。

  1. 让 (X=\lfloor \frac{L+R}{2}\rfloor) .
  2. 如果是 (\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)​ 次。因此，问题已经解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

https://atcoder.jp/contests/abc341/tasks/abc341\_f

设 (\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})) 时间内解决上述背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
}