「考试总结」ZROI-21-NOIP冲刺-TEST6 总结

发表于 2021-10-26 分类于考试总结

ZROI-21-NOIP冲刺-TEST6 总结

莫要问 TEST5 去哪了，他有 4 道巨大恶心的计数题，补不动了QwQ

#T1 夏令营

#题意简述

给定 $n (n \leq 3 \times 10^{5})$ 个区间，每个区间有价值 $h_{i} (1 \leq 3 \times 10^{5})$ ，每个点 $i (i \in [1, D])$ 只能选最多 $k$ 个覆盖该点的区间，问可到的价值和最大的点的最大价值和。

#大体思路

注意到我们只关注单点，且对于覆盖信息相同的点并没有实际区别，于是我们可以考虑将原本的一个区间拆成两个操作：加入和删除。

现在考虑如何快速维护这两个操作。注意到覆盖每个点的的区间分为两部分：包含在该点的答案里的和候选的，如果我们按照时间顺序维护这两个操作，不难发现，当新加入一个区间时，如果这个区间的价值大于当前已选区间的最小者，那么就把它加入答案，将最小者加入候选部分，否则直接加入候选；删除时，如果在候选部分就直接删，否则需要取出候选部分的最大值加入答案。

不难发现两个 priority_queue 就可以完成上面所需的操作（对顶堆？），删除时直接维护信息进行懒删除即可，每次修改只会进行 $O (1)$ 级别的操作，于是单次修改的时间复杂度为 $O (\log n)$ ，总体时间复杂度为 $O (n \log n)$ .

#Code

#define ll long long
#define pii pair <int, int>
#define plli pair <long long, int>
#define mp(a, b) make_pair(a, b)
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 500010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T a, T b) {return a > b ? a : b;}

struct Activity {
    int id, l, r; ll x;
    inline bool operator < (const Activity &b) const {return x > b.x;}
} a[N];

int T, n, d, k, q[N], siz, frt, tal, vis[N], st[N]; ll ans, sum;

priority_queue <plli > pq, cand;

vector <pii > qry[N];

inline bool cmp(Activity x, Activity y) {return x.l == y.l ? x.r < y.r : x.l < y.l;}

inline void reset() {
    frt = 0, tal = -1; ans = 0; mset(vis, 0);
    mset(st, 0); while (pq.size()) pq.pop();
    while (cand.size()) cand.pop(); siz = sum = 0;
    for (int i = 1; i <= d; ++ i) qry[i].clear();
}

void insert(int x) {
    if (siz < k) {
        pq.push(mp(-a[x].x, x)); ++ siz;
        sum += a[x].x; st[x] = 1;
    } else {
        plli tmp = pq.top();
        while (pq.size() && vis[tmp.second]) {pq.pop(); tmp = pq.top();}
        if (-tmp.first < a[x].x) {
            pq.pop(); cand.push(mp(-tmp.first, tmp.second));
            sum += a[x].x + tmp.first;
            pq.push(mp(-a[x].x, x));
            st[tmp.second] = 0, st[x] = 1;
        } else cand.push(mp(a[x].x, x)), st[x] = 0;
    }
}

void del(int x) {
    if (st[x] == 1) -- siz, sum -= a[x].x;
    vis[x] = 1, st[x] = 0;
    while (cand.size() && siz < k) {
        plli tmp = cand.top(); cand.pop();
        if (vis[tmp.second]) continue;
        ++ siz, sum += tmp.first; st[tmp.second] = 1;
        pq.push(mp(-tmp.first, tmp.second));
    }
}

int main() {
    read(T);
    for (int t = 1; t <= T; ++ t) {
        read(d); read(n); read(k); reset();
        for (int i = 1; i <= n; ++ i)
          read(a[i].x), read(a[i].l), read(a[i].r);
        sort(a + 1, a + n + 1, cmp);
        for (int i = 1; i <= n; ++ i) a[i].id = i;
        for (int i = 1; i <= n; ++ i) {
            qry[a[i].l].push_back(mp(1, i));
            qry[a[i].r + 1].push_back(mp(-1, i));
        }
        for (int i = 1; i <= d; ++ i) {
            for (auto k : qry[i])
              if (k.first == -1) del(k.second);
              else insert(k.second);
            ans = Max(sum, ans);
        }
        printf("Case #%d: %lld\n", t, ans);
    }
    return 0;
}

#T2 游戏

#题意简述

给定有一个 $2 n (n \leq 5 \cdot 10^{5})$ 个点的环，同时给定 $n$ 条额外的边（没有重复的端点），要求将整张图的所有点染为两种颜色，满足没有额外边两端颜色相同，在环上没有连续的三个人颜色相同。给出构造方案，若无可行的构造方案，输出 impossible。

#大体思路

先来你考虑环上的约束条件，我们只需要保证 1 与 2 不同，3 与 4 不同…… $2 n - 1$ 与 $2 n$ 不同即可，于是我们只把 $2 i$ 与 $2 i - 1 (1 \leq i \leq n)$ 相连即可，再考虑额外的 $n$ 条边，发现每次最多也只会加入 $2$ 个点，最终形成一个具有偶数个点的环，这样的图一定是一个二分图，所以直接黑白染色即可。时间复杂度 $O (n)$ .

#Code

const int N = 2000010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct Edge {int u, v, nxt;} e[N];

int n, head[N], ecnt(1), vis[N], col[N];

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

void mark(int x, int c) {
    col[x] = c, vis[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt)
      if (!vis[e[i].v]) mark(e[i].v, c ^ 1);
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++ i) {
        int u, v; read(u), read(v);
        add_edge(u, v); add_edge(v, u);
    }
    for (int i = 1; i <= n; ++ i) {
        add_edge((i << 1) - 1, i << 1);
        add_edge(i << 1, (i << 1) - 1);
    }
    for (int i = 1; i <= n << 1; ++ i)
      if (!vis[i]) mark(i, 0);
    for (int i = 1; i <= n << 1; ++ i)
      if (col[i]) putchar('X'); else putchar('Y');
    return 0;
}

#T3 字符串

#题意简述

给定 $n (n \leq 100)$ 个字符在字符串 $S$ 中的出现次数 $a_{i} (a_{i} \leq 10^{9})$ ，要求将这些字符用 0/1 进行编码，每个字符编码的长度不超过 $l (l \leq 30)$ ，问 $S$ 在编码后的最小长度。

#大体思路

因为编码长度有限制，所以直接用哈夫曼树是不行的（实际上因为数据过水可以过 QnQ），但是可以借鉴哈夫曼树的思想，使用二叉树进行编码。

设 $f_{i, j, k}$ 为当前处理了出现次数前 $i$ 大的字符，在二叉树的第 $j$ 层，还剩 $k$ 个结点可用时的最小长度和，容易发现具有转移： $\begin{aligned} f_{i, j, k} & \to f_{i + 1, j, k - 1}, \\ f_{i, j, k} & \to f_{i, j + 1, k \times 2} . \end{aligned}$ 然后直接转移即可，时间复杂度为 $O (n^{2} l)$ .

#Code

#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 110;
const ll INF = 1e18;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Min(T a, T b) {return a < b ? a : b;}

ll n, l, a[N], ans, f[N][40][N];

int main() {
    read(n), read(l);
    while (n || l) {
        for (int i = 1; i <= n; ++ i) read(a[i]);
        auto cmp = [](int x, int y){return x > y;};
        sort(a + 1, a + n + 1, cmp); mset(f, 0x3f);
        f[0][1][2] = f[0][1][1] = 0; ans = INF;
        for (int i = 0; i < n; ++ i)
          for (int j = 1; j <= l; ++ j)
            for (int k = 1; k <= Min(n, 1ll << j); ++ k)
              if (f[i][j][k] < INF) {
                  f[i + 1][j][k - 1] = Min(f[i + 1][j][k - 1], f[i][j][k] + 1ll * a[i + 1] * j);
                  f[i][j + 1][k * 2] = Min(f[i][j + 1][k * 2], f[i][j][k]); 
              }
        for (int i = 0; i <= l; ++ i)
          for (int j = 0; j <= Min(n, 1ll << i); ++ j)
            ans = Min(ans, f[n][i][j]);
        printf("%lld\n", ans); read(n), read(l);
    }
    return 0;
}

#T4 金色飞贼

~~巨大恶心的~~计算几何，暂且咕着。