[CCO2022] Double Attendance 题解

· · 题解

小数肯定做不了，但是注意到将所有区间 (l,r) 改成 [l,r) 后就可以把值域变成整数了。

心路历程

想直接看正解就跳过。

贪心应该不好做，最长路还不如 dp。不如就考虑 dp。

比如说将所有点离散化一下，dp_{i,j,b} 表示当前在(离散化后)第 i 个点，位于教室 j，从 i 花 k 的代价走到另一个教室此时放的幻灯片有没有看过(没放片就当没看过)时最多看过多少片。虽然但是，我可能中间不能存档(如下图)，这样的话转移会非常麻烦，就很难过。

然后再考虑解决这个问题，比如说每两个点之间我只记录片看得最多的那个人，看得片一样多就取最快的。仔细想想发现可能不优(原因这里因为我懒所以不多赘述)。

接着就不会了。看了看题解，发现要将离散化连根刨掉。

状态还是 dp_{i,j,b}，只是 i 变成了当前在 i 这个位置，注意现在没有离散化。

转移很简单，时间复杂度可以做到 O(k)。

如何优化？

显然对于同一 j,b，dp_{i,j,b} 随 i 单调递增，且对于值相同的两个人，假如说是 x 和 y，那么 dp_{x,j,b} 仅通过原地挂机就能得到 dp_{y,j,b}（当然 b 可能会从 1 变为 0，但并不影响 x 比 y 更优）。

而 dp_{i,j,b} 的值域是 O(n) 的，此时套路告诉我们交换 i 和 dp_{i,j,b}，即每种值只记录最快的那个人来代替其他人转移。

正解

重新定义一下状态，dp_{i,j,b} 表示看过 i 部片子，当前位于教室 j，花 k 的代价走到另一个教室此时放的幻灯片有没有看过(没放片就当没看过)时最快在哪个位置。

转移的话考虑看的下一部片在哪个教室。如果在当前教室就直接跳，否则在另一个教室那么现在就出发肯定是最优的(注意可能在当前教室再向前走几步可以使得 b 从 1 变为 0，但是不转移他显然不影响答案)。

然后用二分维护一下转移就做完了，更多细节见代码。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
const int N = 3e5;
const int INF = 0x3f3f3f3f;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++ )
inline bool is_num(char ch) {return '0' <= ch && ch <= '9';}
inline bool is_char(char ch) {return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z';}
char buf[1000005], *p1 = buf, *p2 = buf;
inline int read()
{
    char ch;
    int f = 1, x = 0;
    while (!is_num(ch = gc())) if (ch == '-') f = -1;
    do x = (x << 1) + (x << 3) + ch - '0'; while (is_num(ch = gc()));
    return f * x;
}
int n[2], m;
int dp[2][2][2];
struct node
{
    int l, r;
    bool operator < (const node &t) const {return l < t.l;}
    bool operator < (const int &t) const {return r < t;}
} block[2][N + 5];
inline int get(int type, int pos) {return std :: lower_bound(block[type] + 1, block[type] + n[type] + 1, pos) - block[type];}
inline int find(int type, int pos) {int t = get(type, pos); return block[type][t].l <= pos ? t : 0;} // 在 type 教室的 pos 位置放的是哪部片子，没放返回 0
inline int next(int type, int pos) {int t = get(type, pos); return t + (block[type][t].l <= pos);} // 在 type 教室的 pos 位置的下一部片是谁
inline void modify(int &x, int y) {x = std :: min(x, y);}
int main()
{
    n[0] = read() + 1, n[1] = read() + 1, m = read();
    for (int i = 1; i < n[0]; i ++ ) block[0][i] = /* */ {read(), read() - 1}; block[0][n[0]] = /* */ {INF, INF}; std :: sort(block[0] + 1, block[0] + n[0] + 1);
    for (int i = 1; i < n[1]; i ++ ) block[1][i] = /* */ {read(), read() - 1}; block[1][n[1]] = /* */ {INF, INF}; std :: sort(block[1] + 1, block[1] + n[1] + 1);
    std :: memset(dp, 0x3f, sizeof dp);
    dp[!block[0][1].l][0][0] = 0;
    int res = 0;
    for (int i = !block[0][1].l; i <= n[0] + n[1]; i ++ )
    {
        std :: memset(dp[i + 1 & 1], 0x3f, sizeof dp[i + 1 & 1]);
        for (int cas = 0; cas <= 1; cas ++ ) // 注意因为可能会出现 i 更新 i, 所以要么选择更新两遍，要么类似于 dijkstra 将值从小到大更新
            for (int j = 0; j <= 1; j ++ )
                for (int k = 0; k <= 1; k ++ )
                {
                    if (dp[i & 1][j][k] >= INF) continue;
                    int tim = dp[i & 1][j][k], pos = find(j, tim), across = find(j ^ 1, tim + m), after = next(j, tim);
                    modify(dp[i + (across && !k) & 1][j ^ 1][pos && find(j, tim + 2 * m) == pos], tim + m); // 下一部片在另一个教室，立即出发
                    modify(dp[i + 1 & 1][j][across && k && find(j ^ 1, block[j][after].l + m) == across], block[j][after].l); // 下一部片在当前教室
                    res = std :: max(res, i);
                }
    }
    printf("%d", res);
    return 0;
}