SDOI 2019 大赏

2020-04-15

从四月开始摸了两周鱼… 感觉不太行, 又滚过来做省选套题了.

「SDOI2019」快速查询

题目链接

https://loj.ac/problem/3110

解题思路

~~这道题有意思的地方在于 T2.~~

显然正解是线性做法. 维护标记 $a$, $b$, $c$, 以及真实值全局和 $s$. 那么, 对于记录的值 $x$, 如果这个位置曾被单点赋值, 其真实值为 $ax + b$. 否则 $x$ 为 $c$.

可以利用离散化处理数列位置标号的问题. 但是离散化做法在实现时有些繁琐的细节, 于是偷懒用了 unordered_map, 每次全局赋值暴力清空 unordered_map = =

具体地, 对于操作

更新 $s$, 改变记录的 $A_i$, 使其满足 $a A_i + b = \mathrm{val}$, 即 $A_i \equiv a ^ {-1} \cdot (\mathrm{val} - b) \pmod P$.
更新 $b, s$.
更新 $a, b, s$.
清空 unordered_map, 初始化 $a, b, s, c$. 清空的时间复杂度和 unordered_map 中元素个数有关, 因此复杂度是对的.
在 unordered_map 中查询, 不存在该位置即为 $c$.
返回 $s$ 即可.

1 操作需要用到逆元. 注意到模数不大且是质数, 线性预处理逆元即可.

时间复杂度 $O(tq)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3110
// DeP
#include <cctype>
#include <cstdio>
#include <unordered_map>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXQ = 1e5 + 5, P = 1e7 + 19;

struct Opt {
    int opt, idx, val;
} Q[MAXQ];

int n, q, t, ans;
int inv[P];
unordered_map<int, int> A;

inline void solve(const Opt& p) {
    static int a = 1, b = 0, c = 0, s = 0;
    if (p.opt == 1) {
        if (A.count(p.idx) > 0)
            s = (s - (1LL * a * A[p.idx] % P + b) % P + P) % P;
        else s = (s - (1LL * a * c % P + b) % P + P) % P;
        A[p.idx] = 1LL * (p.val - b + P) % P * inv[a] % P;
        s = (s + p.val) % P;
    }
    if (p.opt == 2)
        b = (b + p.val) % P, s = (s + 1LL * n * p.val) % P;
    if (p.opt == 3) {
        a = 1LL * a * p.val % P, b = 1LL * b * p.val % P;
        s = 1LL * s * p.val % P;
    }
    if (p.opt == 4) {
        a = 1, b = 0, c = p.val, s = 1LL * n * p.val % P;
        A.clear();
    }
    if (p.opt == 5) {
        if (A.count(p.idx) > 0)
            ans = (ans + (1LL * a * A[p.idx] % P + b) % P) % P;
        else ans = (ans + (1LL * a * c % P + b) % P) % P;
    }
    if (p.opt == 6)
        ans = (ans + s) % P;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(q);
    for (int i = 1; i <= q; ++i) {
        static int opt, idx, val;
        read(opt), idx = val = 0;
        if (opt == 1 || opt == 5) read(idx);
        if (opt != 5 && opt != 6) read(val);
        Q[i] = (Opt){ opt, idx, (val % P + P) % P };
    }
    // init
    inv[0] = inv[1] = 1;
    for (int i = 2; i < P; ++i)
        inv[i] = 1LL * inv[P % i] * (P - P / i) % P;
    // output
    read(t);
    while (t--) {
        static int a, b;
        read(a), read(b);
        for (int j = 1; j <= q; ++j)
            solve(Q[(a + 1LL * j * b % q) % q + 1]);
    }
    printf("%d\n", ans);
    return 0;
}

「SDOI2019」染色

~~暴论: 题目名称叫 “染色” 的都是毒瘤题~~.

题目链接

https://loj.ac/problem/3111

解题思路

毒瘤题, 琢磨了好久也写了好久.

参考了 yhx-12243 的题解, 感觉 yhx-12243 讲地非常好.

容易得出一个朴素 DP: 设 $f(i, c_1, c_2)$ 表示处理前 $i$ 列, 第 $i$ 列颜色分别为 $c_1, c_2$ 的方案数, 每次转移时枚举颜色.

考虑到 “相邻节点颜色不同” 的限制只约束了颜色不同, 每次枚举所有颜色看起来没有必要. 同时行数很小, 本质不同的情况很少.

从这个角度出发, 只考虑被染色的列. 我们称上下两行任意一格已经被染色的列为关键列. 对于两个 “相邻” 的关键列, 也就是两列间不包含其他的关键列, 其对方案数的贡献只和两列的染色的相对情况, 以及相隔未染色列个数有关.

具体地, 关键列的排布只有以下几种情况. (其中 $x$, $y$ 表示已经确定过的颜色, $w$ 为不同于 $x$, $y$ 的颜色)

$\begin{bmatrix} x & \ldots & x \\ y & \ldots & y \end{bmatrix} \tag{0}$ $\begin{bmatrix} x & \ldots & y \\ y & \ldots & x \end{bmatrix} \tag{1}$ $\begin{bmatrix} x & \ldots & x \\ y & \ldots & w \end{bmatrix}, \begin{bmatrix} x & \ldots & w \\ y & \ldots & y \end{bmatrix} \tag{2}$ $\begin{bmatrix} x & \ldots & y \\ y & \ldots & w \end{bmatrix}, \begin{bmatrix} x & \ldots & w \\ y & \ldots & x \end{bmatrix} \tag{3}$ $\begin{bmatrix} x & \ldots & w_1 \\ y & \ldots & w_2 \end{bmatrix} \tag{4}$

那么预处理出两关键列之间的转移. 设 $g(i, s)$ 表示两关键列相隔长度为 $i$, 后一关键列状态为 $s$ 的方案数.

设 $\mathbf{g_i} =\begin{bmatrix} g(i, 0) \ g(i, 1) \ g(i, 2) \ g(i, 3) \ g(i, 4) \end{bmatrix}$, 大力分类讨论后可以得到转移

$\mathbf{g_{i + 1}} = \begin{bmatrix} 0 & 1 & 0 & 2(c-2) & (c-2)(c-3) \\ 1 & 0 & 2(c-2) & 0 & (c-2)(c-3) \\ 0 & 1 & c-2 & (c-2) + (c-3) & (c-3)^2 \\ 1 & 0 & (c - 2) + (c - 3) & c-2 & (c-3) ^ 2 \\ 1 & 1 & 2(c-3) & 2(c-3) & c^2 - 7c + 13 \end{bmatrix} \times \mathbf{g_i}$

(其中 $c ^ 2 - 7c + 13$ 由 $(c-2)(c-3) - (c-2) - (c-3)$ 得到)

通过预处理 $g$, 只需枚举关键列, 通过关键列的颜色分布以及关键列相隔距离转移即可得出答案.

具体地, 和 yhx-12243 的题解一样, 将转移分为 brute, open, close, move 四个部分, 具体定义参见上述题解 (

为了表述方便, 记两关键列的颜色的分布情况为 $\begin{bmatrix} l_1 & \ldots & r_1 \ l_2 & \ldots & r_2 \end{bmatrix}$.

brute

此时两关键列的情况都唯一, 根据颜色相对情况填上对应情况的数值即可.
open

不妨假设 $r_1$ 为已确定的颜色, 另一种情况同这个情况类似.

通过比较 $r_1$ 和 $l_1, l_2$ 的相等关系, 判定其是否属于情况 2 / 3, 以及枚举 $r_2$ 取值, 并额外处理 $r_2$ 和 $l_1, l_2$ 相等的情况.
close

不妨假设 $l_1$ 为已确定的颜色, 另一种情况同这个情况类似.

同 open 的情况类似, 不过在处理 $l_2$ 和 $r_1, r_2$ 相等情况时, 需减去 $l_1$ 时已经计算的部分避免算重.
move

最为繁琐的情况. ~~同时也是前两档部分分的组成~~

首先需要判定组成的局面构成情况 2 或是情况 3. 接着用类似 open / close 的方法讨论颜色, 注意减去算重的部分.

此外还需要处理首尾关键列的部分, 以及不存在关键列, 或是无解的一些特殊情况, 详细式子相对容易理解, 自行参考代码 (

综上, 得出了时间复杂度为 $O(nc)$ 的做法.

可以发现, 转移时的操作恰好是 T1 中的操作, 利用 T1 的做法优化转移即可, 时间复杂度 $O(n + c)$.

注意, 全局乘 $a$ 时, 如果 $a = 0$, 那么等价于全局赋值 $0$. 如果 T1 实现不精细, 在这里就会出现问题.

代码实现

> 点击显示 / 隐藏

// LOJ #3111
// DeP
#include <cctype>
#include <cstdio>
#include <unordered_map>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 1e5 + 5, P = 1e9 + 9;

int fpow(int base, int b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = 1LL * ret * base % P;
        base = 1LL * base * base % P, b >>= 1;
    }
    return ret;
}

void exgcd(int a, int b, int& x, int& y) {
    if (!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}
inline int inv(const int& a) {
    static int x, y;
    return exgcd(a, P, x, y), (x % P + P) % P;
}

namespace SDOI {
    int n, a, b, c, s;
    unordered_map<int, int> A;

    inline void init(int _n) { n = _n, a = 1, b = c = s = 0, A.clear(); }

    inline LL Qry() { return s; }
    inline LL Qry(const int& p) {
        return (1LL * a * ((A.count(p) > 0)? A[p]: c) % P + b) % P;
    }
    inline void Sgn(const int& v) {
        a = 1, b = 0, c = v, s = 1LL * n * v % P, A.clear();
    }
    inline void Sgn(const int& p, const int& v) {
        s = (s - (1LL * a * ((A.count(p) > 0)? A[p]: c) % P + b) % P + P) % P;
        A[p] = 1LL * (v - b + P) % P * inv(a) % P, s = (s + v) % P;
    }
    inline void Add(const int& v) { b = (b + v) % P, s = (s + 1LL * n * v % P) % P; }
    inline void Mul(const int& v) {
        if (!v) return Sgn(v);
        a = 1LL * a * v % P, b = 1LL * b * v % P, s = 1LL * s * v % P;
    }
}
using SDOI::Sgn; using SDOI::Add; using SDOI::Mul; using SDOI::Qry;

void MatrixMul(const int* f, int* g, const int (*W)[5]) {
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 5; ++j) g[i] = (g[i] + 1LL * f[j] * W[i][j] % P) % P;
}

int n, m, C;
int A[MAXN], B[MAXN];
int pos[MAXN], g[MAXN][5];

void PreMatrix() {
    int x = C - 2, y = C - 3, yy = 1LL * y * y % P, xy = 1LL * x * y % P;
    const int W[5][5] = {
        { 0, 1,   0, 2*x, xy },
        { 1, 0, 2*x,   0, xy },
        { 0, 1,   x, x+y, yy },
        { 1, 0, x+y,   x, yy },
        { 1, 1, 2*y, 2*y, int((C * (C - 7LL) + 13) % P) }
    };
    g[0][0] = 1;
    for (int i = 1; i <= n; ++i) MatrixMul(g[i - 1], g[i], W);
}

inline int brute(int l1, int l2, int r1, int r2, int* f) {
    static const int tmp[] = { 4, 2, 3, -1, 3, -1, 1, -1, 2, 0, -1 };
    return f[tmp[(l1 == r1) | (l1 == r2) << 1 | (l2 == r1) << 2 | (l2 == r2) << 3]];
}

inline void open(int l1, int l2, int r1, int r2, int* f) {
    int r = r1 | r2;
    if (!r1 && r2 > 0) swap(l1, l2);
    if (l1 == r) Sgn(f[2]), Sgn(l2, f[0]);
    else if (l2 == r) Sgn(f[3]), Sgn(l1, f[1]);
    else Sgn(f[4]), Sgn(l1, f[3]), Sgn(l2, f[2]);
    Sgn(r, 0);
}

inline int close(int l1, int l2, int r1, int r2, int* f) {
    int l = l1 | l2;
    if (!l1 && l2 > 0) swap(r1, r2);
    if (l == r1) return (Qry() * f[2] + Qry(r2) * (f[0] - f[2] + P)) % P;
    if (l == r2) return (Qry() * f[3] + Qry(r1) * (f[1] - f[3] + P)) % P;
    return (Qry() * f[4] + Qry(r1) * (f[3] - f[4] + P) + Qry(r2) * (f[2] - f[4] + P)) % P;
}

inline void move(int l1, int l2, int r1, int r2, int* f) {
    int l = l1 | l2, r = r1 | r2;
    LL v, s = Qry();
    if (!l1 ^ !r1) {
        if (l == r) Mul((f[1] - f[3] + P) % P), Add(s * f[3] % P);
        else {
            v = Qry(r), s = (s - v + P) % P;
            Mul((f[3] - f[4] + P) % P), Add((s * f[4] + v * f[2]) % P);
            Sgn(l, (s * f[2] + v * f[0]) % P);
        }
    } else {
        if (l == r) Mul((f[0] - f[2] + P) % P), Add(s * f[2] % P);
        else {
            v = Qry(r), s = (s - v + P) % P;
            Mul((f[2] - f[4] + P) % P), Add((s * f[4] + v * f[3]) % P);
            Sgn(l, (s * f[3] + v * f[1]) % P);
        }
    }
    Sgn(r, 0);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(C);
    for (int i = 1; i <= n; ++i) read(A[i]);
    for (int i = 1; i <= n; ++i) read(B[i]);
    // check
    for (int i = 1; i <= n; ++i) if (A[i] || B[i]) {
        if (A[i] == B[i]) return puts("0"), 0;
        if (i < n) {
            if (A[i] && A[i] == A[i + 1]) return puts("0"), 0;
            if (B[i] && B[i] == B[i + 1]) return puts("0"), 0;
        }
        pos[++m] = i;
    }
    int ans = 1;
    if (!m) {
        ans = 1LL * C * (C - 1) % P * fpow((C * (C - 3LL) + 3) % P, n - 1) % P;
        return printf("%d\n", ans), 0;
    }
    // init
    SDOI::init(C), PreMatrix();
    // solve
    int u = A[pos[1]], d = B[pos[1]], t = fpow((C * (C - 3LL) + 3) % P, pos[1] - 1);
    if (u && d) ans = t; else Add(t), Sgn(u | d, 0);
    for (int i = 2; i <= m; ++i) {
        int lu = u, ld = d, *f = g[pos[i] - pos[i - 1]];
        u = A[pos[i]], d = B[pos[i]];
        if (u && d) {
            if (lu && ld) ans = 1LL * ans * brute(lu, ld, u, d, f) % P;
            else ans = 1LL * ans * close(lu, ld, u, d, f) % P;
        } else {
            if (lu && ld) open(lu, ld, u, d, f); else move(lu, ld, u, d, f);
        }
    }
    if (!(u && d)) ans = ans * Qry() % P;
    ans = 1LL * ans * fpow((C * (C - 3LL) + 3) % P, n - pos[m]) % P;
    // output
    printf("%d\n", ans);
    return 0;
}

「SDOI2019」世界地图

题目链接

https://loj.ac/problem/3112

解题思路

首先有一个朴素的想法. 观察到 $1 < L \le R < m$, 预处理前缀 / 后缀的 MST, 每次查询区间 $[L, R]$ 时, 合并 $L$ 前以及 $R$ 后的 MST, 同时加入第一列和最后一列的边.

时间复杂度为 $O(m ^ 2 n \log nm + q n m\log nm)$, 快乐.

观察到题目中给定的是网格图, 对于前缀或后缀 MST, 除去边界两列, 其 “内部” 列不会再存在边同其相连. 换句话说, 每次合并 MST 时, 用到的部分只有 $2n$ 个边界两列节点, 其内部节点部分并不受影响.

那么, 每次只记录和这 $2n$ 个点相关的边, 并记录其余边的边权和, 称之为 “虚树”. 每次合并 MST 时, 取出相关的边跑 Kruksal, 之后对得到的生成树建虚树即可.

对于建虚树的部分, 为了保持 MST 的性质, 涉及到保留哪些节点以及对应边的边权问题. 我们称保留在虚树中的点为 “关键点”, 那么关键点需满足以下任一条件:

设待合并的两棵虚树分别为 $L$, $R$, 那么 $L$ 中最靠前的部分, 以及 $R$ 中最靠后的部分一定是关键点.

这一部分并不受新增加的边影响, 显然要保留.
至少有两个儿子, 满足在儿子的子树内存在关键点.

同时, 只需记录关键点之间最大边权作为合并后虚树边权即可. 根据 MST 的回路性质, 可以发现这是对的.

时间复杂度 $O(mn \log n + q n\log n)$.

代码实现

“为什么你们的代码都是一个叫 MST 的结构体, 然后都用一个叫 merge 的函数合并 ?”

> 点击显示 / 隐藏

// LOJ #3112
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

#define DEBUG(args...) fprintf(stderr, ##args)

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 1e2 + 5, MAXM = 1e4 + 5, MAXV = MAXN << 3;

struct Edge {
    int u, v, w;
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) { }
    bool operator < (const Edge& rhs) const { return w < rhs.w; }
};

int n, m, q, lim;
unsigned SA, SB, SC;

vector<Edge> E;
int Idx[MAXV], W1[MAXM][MAXN], W2[MAXM][MAXN];

namespace Graph {
    struct Edge { int nxt, to, w; } edges[MAXV << 1];
    int head[MAXV], eidx;

    inline void init(int _n) {
        memset(head, -1, (_n + 1) * sizeof (int)), eidx = 1;
    }
    inline void AddEdge(int from, int to, int w) {
        edges[++eidx] = (Edge){ head[from], to, w }, head[from] = eidx;
        edges[++eidx] = (Edge){ head[to], from, w }, head[to] = eidx;
    }

    int dfsPre(int u, int fa, const int& tot) {
        int s = 0;
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            if ((v = edges[i].to) != fa) s += dfsPre(v, u, tot);
        if (s >= 2) Idx[u] = 1;
        return s + Idx[u] > 0;
    }
    void dfs(int u, int fa, int lst, int w, LL& s) {
        if (Idx[u] > 0) {
            if (lst > 0) E.push_back(::Edge(Idx[lst], Idx[u], w));
            lst = u, s -= w, w = 0;
        }
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            if ((v = edges[i].to) != fa) dfs(v, u, lst, max(w, edges[i].w), s);
    }
}

namespace DSU {
    int fa[MAXV];

    inline void init(const int& _n) {
        for (int i = 1; i <= _n; ++i) fa[i] = i;
    }

    int findfa(const int& u) { return fa[u] == u? u: fa[u] = findfa(fa[u]); }
    inline bool join(int fu, int fv) {
        fu = findfa(fu), fv = findfa(fv);
        return (fu == fv)? false: (fa[fv] = fu, true);
    }
}

struct MST {
    int v; LL s;
    vector<Edge> E;

    MST() { }
    MST(int* W) {
        v = n, s = 0;
        for (int i = 1; i < n; ++i) E.push_back(Edge(i, i + 1, W[i]));
    }
    MST(int _v, LL _s, const vector<Edge>& _E): v(_v), s(_s), E(_E) { }

    inline LL calc() {
        LL ret = s;
        for (const auto& e: E) ret += e.w;
        return ret;
    }
} pre[MAXM], suf[MAXM];

MST Mrg(const MST& L, const MST& R, const int *W) {
    int tot = L.v + R.v;
    // init
    E.clear(), DSU::init(tot), Graph::init(tot);
    // Kruskal
    for (const Edge& e: L.E) E.push_back(e);
    for (const Edge& e: R.E)
        E.push_back(Edge(L.v + e.u, L.v + e.v, e.w));
    for (int i = 1; i <= n; ++i)
        E.push_back(Edge(L.v - n + i, L.v + i, W[i]));
    sort(E.begin(), E.end());
    LL s = 0;
    for (const Edge& e: E)
        if (DSU::join(e.u, e.v)) Graph::AddEdge(e.u, e.v, e.w), s += e.w;
    // build virtual tree
    for (int u = 1; u <= tot; ++u)
        Idx[u] = (u <= n || u > tot - n);
    Graph::dfsPre(1, 0, tot);
    int idx = 0;
    for (int i = 1; i <= tot; ++i)
        if (Idx[i] > 0) Idx[i] = ++idx;
    E.clear(), Graph::dfs(1, 0, 0, 0, s);
    return MST(idx, L.s + R.s + s, E);
}

inline int Rnd() {
    SA ^= SA << 16, SA ^= SA >> 5, SA ^= SA << 1;
    unsigned t = SA;
    SA = SB, SB = SC, SC ^= t ^ SA;
    return SC % lim + 1;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    read(SA), read(SB), read(SC), read(lim);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) W1[j][i] = Rnd();
    for (int i = 1; i < n; ++i)
        for (int j = 1; j <= m; ++j) W2[j][i] = Rnd();
    // solve
    pre[1] = MST(W2[1]);
    for (int i = 2; i < m; ++i)
        pre[i] = Mrg(pre[i - 1], MST(W2[i]), W1[i - 1]);
    suf[m] = MST(W2[m]);
    for (int i = m - 1; i > 1; --i)
        suf[i] = Mrg(MST(W2[i]), suf[i + 1], W1[i]);
    // output
    read(q);
    for (int L, R; q; --q) {
        read(L), read(R);
        printf("%lld\n", Mrg(suf[R + 1], pre[L - 1], W1[m]).calc());
    }
    return 0;
}

「SDOI2019」热闹的聚会与尴尬的聚会

题目链接

https://loj.ac/problem/3113

解题思路

清新题.

首先有 $\frac{n}{p + 1} < \lfloor \frac{n}{p + 1} \rfloor + 1 \le q + 1$, 也就是 $n < (p + 1) (q + 1)$.

再进一步转换, 也就是求尽量大的 $p$, $q$. 那么问题可拆分成两部分:

求 $G$ 点集的某个子集 $V’$, 以 $V’$ 和 $G$ 中对应边构成 $G$ 的一张子图 $G’$, 使得 $G’$ 中度数最小点的度数为 $p$.
求 $G$ 的最大独立集, 使其大小 $q$ 满足 $n < (p + 1) (q + 1)$.

对于 $p$, 一个显然的思路是依次删除度数尽量小的点, 并在删点的过程中维护当前得到的最大 $p$ 值.

对于 $q$, 直接做显然是 NPC. 考虑一个贪心, 每次选择度数最小的点, 然后将这个点周围的点删去, 更新其余点的度数.

考虑如何证明这个做法的正确性.

求一个可行的 $q$ 时, 删去的节点不超过 $p$ 个. 即 $q \ge \lceil \frac{n}{p + 1} \rceil$. 进行一些转化, 有

$\frac{n}{p + 1} <\lceil \frac{n}{p + 1} \rceil +1 \le q + 1$ $n < (p + 1) (q + 1)$

这就是要证的.

时间复杂度大概是 $O((n + m) \log m)$? 感觉很假…

代码实现

> 点击显示 / 隐藏

// LOJ #3113
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 1e4 + 5, MAXM = 1e5 + 5;

struct Item {
    int d, u;
    Item(int _d, int _u): d(_d), u(_u) { }
    bool operator < (const Item& rhs) const { return d > rhs.d; }
};

int n, m;
int deg[MAXN];

priority_queue<Item> PQ;
int vis[MAXN], Time;
int f[MAXN], A[MAXN], B[MAXN], nA, nB;

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXM << 1];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
    }
}

void Lively() {
    static int Rmv[MAXN], nR, p, limit;
    ++Time, limit = nR = 0, p = n;
    for (int u = 1; u <= n; ++u)
        p = min(p, f[u]), PQ.push(Item(f[u] = deg[u], u));
    while (!PQ.empty()) {
        int u = PQ.top().u, d = PQ.top().d; PQ.pop();
        if (d != f[u]) continue;
        if (p < d) p = d, limit = nR;
        Rmv[++nR] = u, vis[u] = Time;
        for (int v, i = Graph::head[u]; ~i; i = Graph::edges[i].nxt) {
            if (vis[v = Graph::edges[i].to] == Time) continue;
            PQ.push(Item(--f[v], v));
        }
    }
    nA = 0, ++Time;
    for (int i = 1; i <= limit; ++i) vis[Rmv[i]] = Time;
    for (int u = 1; u <= n; ++u)
        if (vis[u] != Time) A[++nA] = u;
}

void Awkward() {
    nB = 0, ++Time;
    for (int u = 1; u <= n; ++u)
        PQ.push(Item(f[u] = deg[u], u));
    while (!PQ.empty()) {
        int u = PQ.top().u, d = PQ.top().d; PQ.pop();
        if (d != f[u] || vis[u] == Time) continue;
        B[++nB] = u, vis[u] = Time;
        for (int v, i = Graph::head[u]; ~i; i = Graph::edges[i].nxt) {
            if (vis[v = Graph::edges[i].to] == Time) continue;
            vis[v] = Time;
            for (int x, j = Graph::head[v]; ~j; j = Graph::edges[j].nxt)
                if (vis[x = Graph::edges[j].to] != Time) PQ.push(Item(--f[x], x));
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti);
    while (Ti--) {
        // init
        Graph::init();
        memset(deg, 0, sizeof deg);
        // input
        read(n), read(m);
        for (int u, v, i = 1; i <= m; ++i) {
            read(u), read(v);
            Graph::AddEdge(u, v), Graph::AddEdge(v, u);
            ++deg[u], ++deg[v];
        }
        // solve
        Lively(), Awkward();
        // output
        printf("%d ", nA);
        for (int i = 1; i <= nA; ++i) printf("%d%c", A[i], " \n"[i == nA]);
        printf("%d ", nB);
        for (int i = 1; i <= nB; ++i) printf("%d%c", B[i], " \n"[i == nB]);
    }
    return 0;
}

「SDOI2019」移动金币

题目链接

https://loj.ac/problem/3114

解题思路

~~似乎是单纯的 Staircase Nim 计数?~~

对题意做一步转化. 将移动金币的过程看作一定量的格子移动到了金币后. 那么, 将金币看作阶梯的分界, 移动金币看作将阶梯上的石子移动到下一层, 显然就是 “阶梯博弈” 的模型了.

阶梯博弈中, 先手必胜的条件是所有编号为奇 (注意这里的编号从 $0$ 开始) 的阶梯上石子个数异或和不为 $0$. 此时根据后手的决策讨论一番即可得出证明.

那么, 现在有 $n - m$ 颗石子, 要将这些石子放在在 $m + 1$ 个阶梯上, 求满足限制的方案数.

注意到 “异或和不为 $0$” 的条件不好处理, 于是改为处理编号为奇数的阶梯上异或和为 $0$ 的方案数. 考虑二进制下按位 DP, 则需要满足的条件为每一位出现 $1$ 的次数为偶数次.

设 $f(i, j)$ 表示处理完前 $i$ 位, 剩余 $j$ 个石子的方案数. 为满足异或和为 $0$ 的条件, 需要选择偶数个阶梯, 在这些阶梯上放置 $2 ^ i$ 个石子.

记编号为奇数的阶梯个数为 $q = \lfloor \frac{m + 1}{2} \rfloor$, 有

$f(i, j) = \sum_{k \bmod 2 = 0} ^ q f(i + 1, j + k \cdot 2 ^ {i})$

记编号为偶数的阶梯个数为 $p = \lceil \frac{m + 1}{2} \rceil$, 最终答案为

$\binom{n}{m} - \sum_{i = 0} ^ {n - m} \binom{i + p - 1}{i} \cdot f\big(0,\ i\big)$

时间复杂度 $O(nm\log n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3114
// DeP
#include <cstdio>
using namespace std;

const int MAXN = 15e4 + 5, MAXM = 55, LOG = 19, P = 1e9 + 9;

int fac[MAXN], ifac[MAXN];

int fpow(int base, int b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = 1LL * ret * base % P;
        base = 1LL * base * base % P, b >>= 1;
    }
    return ret;
}

void PolyPre(int N) {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = 1LL * i * fac[i - 1] % P;
    ifac[N] = fpow(fac[N], P - 2);
    for (int i = N; i; --i) ifac[i - 1] = 1LL * ifac[i] * i % P;
}

inline int C(int n, int m) {
    return n < m? 0: 1LL * fac[n] * ifac[n - m] % P * ifac[m] % P;
}

int n, m;
int f[LOG][MAXN];

int main() {
    // input
    scanf("%d%d", &n, &m);
    // sovle
    if (n < m) return puts("0"), 0;
    PolyPre(n + m);
    int q = (m + 1) / 2, lg2 = 1;
    while ((1 << lg2) <= n - m) ++lg2;
    f[lg2][n - m] = 1;
    for (int i = lg2 - 1; i >= 0; --i)
        for (int j = 0; j <= n - m; ++j)
            for (int k = 0; k <= q && j + k * (1LL << i) <= n - m; k += 2)
                f[i][j] = (f[i][j] + 1LL * C(q, k) * f[i + 1][j + k * (1 << i)] % P) % P;
    int ans = 0;
    for (int i = 0; i <= n - m; ++i)
        ans = (ans + 1LL * C(i + (m + 2) / 2 - 1, i) * f[0][i] % P) % P;
    // output
    printf("%d\n", (C(n, m) - ans + P) % P);
    return 0;
}

「SDOI2019」连续子序列

题目链接

https://loj.ac/problem/3115

解题思路

根据 ~~T.M. 序列~~ $\text{Thue−Morse}$ 序列的定义, 手玩之后可以发现:

序列从 '0' 出发, 定义 “扩充” 为长度为 $n$ 的序列的每一个字符 '0' --> '01', '1' --> '10', 从而得到另一个长度 $2n$ 序列. 不断扩充后得到的序列, 恰好是 Thus-Morse 序列.
任何子串包含 111 或 000 的串一定不是 Thus-Morse 序列的子串.

考虑到性质 1 给出的构造 Thus-Morse 序列的方法, 至多有两个相同字符相邻.
长度 $> 3$ 的 Thus-Morse 序列子串 $S$ 一定是由唯一的某个 Thus-Morse 序列子串生成的.

证明参见: https://okazakiyumemi.github.io/blog/「SDOI2019」连续子序列/.

此时得到了一个分治做法: 每次由 $S$ 得到扩充操作之前的串 $T$, 然后分治计算 $T$ 的答案再加以合并.

注意在得出扩充操作前的串 $T$ 时, 需讨论从 $S$ 开头匹配, 以及在 $S$ 前增加一个字符后两种情况. 后者可看作 “$T$ 是 T.M. 的连续子序列” 条件下多考虑的情况.

此外, $|S| \le 3$ 时的问题仍然没有解决.

除去 $|S| = 2$ 或 $|S| = 3$ 的一些特殊情况, 剩余的问题在于 $|S| = 1$.

设 $f(k)$ 表示一个字符后添加恰好 $k$ 个字符, 得出合法序列的方案数. 不难发现, 这个字符为 0 / 1 并不影响 $f(k)$ 的值, 并有

$f(k) = f(\lfloor \frac{k}{2} \rfloor) + f(\lfloor \frac{k + 1}{2} \rfloor)$

记忆化即可. 并存在初值 $f(0) = 1, f(1) = 2, f(2) = 3$.

时间复杂度大概是 $O(T \cdot (|S| + \log k))$?

代码实现

> 点击显示 / 隐藏

// LOJ #3115
// DeP
#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;

typedef long long LL;
const int P = 1e9 + 9;

int f(const LL& k) {
    static unordered_map<LL, int> mf;
    if (k < 3) return k + 1;
    return (mf.count(k) > 0)? mf[k]: mf[k] = (f(k / 2) + f((k + 1) / 2)) % P;
}

inline bool compress(const string& S, string& T) {
    T.clear();
    for (size_t i = 0; i < S.size(); i += 2) {
        if (i + 1 != S.size() && S[i] == S[i + 1]) return false;
        T += S[i];
    }
    return true;
}

int solve(const string& S, const LL& K) {
    int lgt = (int) S.size();
    if (lgt == 1) return f(K);
    if (lgt == 2 && K == 0) return 1; // 10 / 01, 11 / 00
    if (lgt == 2 && K == 1) return (S[0] == S[1])? 1: 2;
    if (lgt == 3 && K == 0) return S[0] != S[1] || S[1] != S[2]; // 111, 000
    string T;
    int ret = 0;
    if (compress(S, T))
        ret = (ret + solve(T, (K + !(lgt & 1)) / 2)) % P;
    if (compress((S[0] == '0'? '1': '0') + S, T))
        ret = (ret + solve(T, (K + (lgt & 1)) / 2)) % P;
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int Ti;
    cin >> Ti;
    for (LL K; Ti; --Ti) {
        static string str;
        cin >> str >> K;
        cout << solve(str, K) << '\n';
    }
    return 0;
}

DepletedPrism's Blog

SDOI 2019 大赏

「SDOI2019」快速查询

题目链接

解题思路

代码实现

「SDOI2019」染色

题目链接

解题思路

代码实现

「SDOI2019」世界地图

题目链接

解题思路

代码实现

「SDOI2019」热闹的聚会与尴尬的聚会

题目链接

解题思路

代码实现

「SDOI2019」移动金币

题目链接

解题思路

代码实现

「SDOI2019」连续子序列

题目链接

解题思路

代码实现