算法竞赛比赛记录: 上海 2015 OI 省选

[SHOI2015] 自动刷题机

一个比较重要的性质： $n=t$ 时可以完成的题目数量，一定不少于 $n=t+1$ 时能够完成的题目数量。令 $f(x)=y$ 表示如果自动刷题机的 $n=x$ ，则一共可以完成 $y$ 道题，则 $f(x)$ 单调递减。

所以，我们需要找到 $f(x)=k$ 的 $x$ 的取值区间。所以我们可以使用二分找出区间的左右端点。

Code

#include <algorithm>
#include <iostream>
#include <vector>
using i64 = long long;

int main() {
    int n, k;
    std::cin >> n >> k;

    std::vector<i64> all(n);
    i64 max = 0;
    for (int i = 0; i < n; i++) {
        std::cin >> all[i];
        max = std::max(max, all[i]);
    }

    auto check = [&](i64 L) {
        int cnt   = 0;
        i64 lines = 0;
        for (auto v : all) {
            lines += v;
            if (lines < 0) lines = 0;
            if (lines >= L) cnt++, lines = 0;
        }
        return cnt;
    };

    // find =k, =k-1 boundary as max L
    i64 l, r;
    i64 ans_r, ans_l;

    l = 0, r = 1e18 + 1;
    while (l + 1 < r) {
        i64 mid = l + ((r - l) >> 1);
        int res = check(mid);
        if (res >= k) l = mid;
        else r = mid;
    }
    ans_r = l;

    l = 0, r = 1e18 + 1;
    while (l + 1 < r) {
        i64 mid = l + ((r - l) >> 1);
        int res = check(mid);
        if (res > k) l = mid;
        else r = mid;
    }
    ans_l = r;

    if (check(ans_l) < k || check(ans_r) < k || check(ans_r) > k || check(ans_l) > k) std::cout << -1 << '\n';
    else std::cout << ans_l << " " << ans_r << "\n";
}

[SHOI2015] 脑洞治疗仪

区间修改？区间最大子段？这不就是线段树吗！

我们考虑线段树怎么做：为了维护区间最大子段（最长 $0$ 子段），我们需要维护前缀 $0$ 的长度、后缀 $0$ 的长度、最长的中缀 $0$ 的长度。区间修改的话，我们还需要懒标记。

接下来，我们来考察怎么进行 fill 操作。我们首先得知 $[l_0,r_0]$ 区间有多少个 $1$ 可以用于治疗（例如说有 $t$ 个），然后删掉，接着再在 $[l_1,r_1]$ 找到一个位置 $p$ ，使得 $[l_1,p]$ 之间恰好有 $t$ 个位置可以填充。找 $p$ 的过程可以通过二分结合线段树的区间查询做到 $O(\log^2 n)$ . 于是，操作 $0/2$ 的单次复杂度为 $O(\log n)$ ，操作 $1$ 的单次复杂度为 $O(\log n)$ ，整体时间复杂度为 $O(m\log^2 n)$ .

Code

代码里使用 reset = 0/1 分别标记这个线段树节点所代表的区间应该全部被设置为 $0/1$ .

#include <algorithm>
#include <cstdio>
#include <iostream>
constexpr int N = 2e5 + 5;

struct Node {
    // for queries
    int prefix0;
    int suffix0;
    int segment0;
    // for filling
    int length;
    int count1;
    // label;
    int reset;
    Node() : prefix0(0), suffix0(0), segment0(0), length(0), count1(0), reset(-1) {}
} T[N << 2];

int n, m;

void pull_up(int rt) {
    int ls = rt << 1, rs = rt << 1 | 1;
    T[rt].length = T[ls].length + T[rs].length;
    T[rt].count1 = T[ls].count1 + T[rs].count1;
    // maintain queries
    T[rt].prefix0 = T[ls].prefix0;
    if (T[ls].prefix0 == T[ls].length) T[rt].prefix0 += T[rs].prefix0;
    T[rt].suffix0 = T[rs].suffix0;
    if (T[rs].suffix0 == T[rs].length) T[rt].suffix0 += T[ls].suffix0;
    T[rt].segment0 = std::max({T[ls].segment0, T[rs].segment0, T[ls].suffix0 + T[rs].prefix0});
}
void mark_zero(int root) {
    T[root].reset   = 0;
    T[root].count1  = 0;
    T[root].prefix0 = T[root].suffix0 = T[root].segment0 = T[root].length;
}
void mark_one(int root) {
    T[root].reset   = 1;
    T[root].count1  = T[root].length;
    T[root].prefix0 = T[root].suffix0 = T[root].segment0 = 0;
}
void push_down(int rt) {
    if (T[rt].reset == -1) return;
    int ls = rt << 1, rs = rt << 1 | 1;
    if (T[rt].reset == 0) mark_zero(ls), mark_zero(rs);
    else if (T[rt].reset == 1) mark_one(ls), mark_one(rs);
    T[rt].reset = -1;
}
// initialize to all 1s
void build(int rt = 1, int l = 1, int r = n) {
    if (l == r) {
        T[rt].length = 1, T[rt].count1 = 1;
        T[rt].segment0 = 0, T[rt].prefix0 = 0, T[rt].suffix0 = 0;
        T[rt].reset = -1;
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pull_up(rt);
}

// make [L, R] all 0s
void remove(int L, int R, int rt = 1, int l = 1, int r = n) {
    if (L > r or R < l) return; // no overlap
    if (L <= l and r <= R) {
        mark_zero(rt);
        return;
    }
    int mid = l + ((r - l) >> 1);
    push_down(rt);
    remove(L, R, rt << 1, l, mid);
    remove(L, R, rt << 1 | 1, mid + 1, r);
    pull_up(rt);
}
void set_one(int L, int R, int rt = 1, int l = 1, int r = n) {
    if (L > r or R < l) return; // no overlap
    if (L <= l and r <= R) {
        mark_one(rt);
        return;
    }
    int mid = l + ((r - l) >> 1);
    push_down(rt);
    set_one(L, R, rt << 1, l, mid);
    set_one(L, R, rt << 1 | 1, mid + 1, r);
    pull_up(rt);
}

int query_sum(int L, int R, int rt = 1, int l = 1, int r = n) {
    if (L > r or R < l) return 0;
    if (L <= l and r <= R) return T[rt].count1;
    int mid = l + ((r - l) >> 1);
    push_down(rt);
    return query_sum(L, R, rt << 1, l, mid) + query_sum(L, R, rt << 1 | 1, mid + 1, r);
}
int query_empty(int L, int R, int rt = 1, int l = 1, int r = n) {
    if (L > r or R < l) return 0;
    if (L <= l and r <= R) return T[rt].length - T[rt].count1;
    int mid = l + ((r - l) >> 1);
    push_down(rt);
    return query_empty(L, R, rt << 1, l, mid) + query_empty(L, R, rt << 1 | 1, mid + 1, r);
}
Node query_segment(int L, int R, int rt = 1, int l = 1, int r = n) {
    if (L > r or R < l) return Node();
    if (L <= l and r <= R) return T[rt];
    int mid = l + ((r - l) >> 1);
    push_down(rt);
    auto left  = query_segment(L, R, rt << 1, l, mid);
    auto right = query_segment(L, R, rt << 1 | 1, mid + 1, r);
    Node res;
    res.length  = left.length + right.length;
    res.count1  = left.count1 + right.count1;
    res.prefix0 = left.prefix0;
    if (left.prefix0 == left.length) res.prefix0 += right.prefix0;
    res.suffix0 = right.suffix0;
    if (right.suffix0 == right.length) res.suffix0 += left.suffix0;
    res.segment0 = std::max({left.segment0, right.segment0, left.suffix0 + right.prefix0});
    return res;
}

int main() {
    std::cin >> n >> m;
    build();

    int op, l0, r0, l1, r1;
    while (m--) {
        std::cin >> op;
        if (op == 0) {
            std::cin >> l0 >> r0;
            remove(l0, r0);
        } else if (op == 1) {
            std::cin >> l0 >> r0 >> l1 >> r1;
            int sum    = query_sum(l0, r0);
            remove(l0, r0);
            int empty  = query_empty(l1, r1);
            int target = std::min(empty, sum);
            // if (target <= 0) continue;

            int l = l1 - 1, r = r1 + 1;
            while (l + 1 < r) {
                int mid = l + ((r - l) >> 1);
                if (query_empty(l1, mid) <= target) l = mid;
                else r = mid;
            }
            if (l >= l1) set_one(l1, l);

        } else {
            std::cin >> l0 >> r0;
            auto seg = query_segment(l0, r0);
            std::cout << seg.segment0 << '\n';
        }
    }
}

这道题应该还有线段树上二分的做法，就是替换掉二分的过程。改日再研究一下~

[SHOI2015] 超能粒子炮·改

看到模数非常小就想到了卢卡斯定理，此题的模数 $2333$ 还是素数，我们只需要用朴素的卢卡斯定理即可，即

下面的除号都是下取整的意思。

\binom{n}{k}\equiv\binom{n/p}{k/p}\binom{n\%p}{k\%p}\pmod p

然而我们要求的却是一个和式 $\sum_{i=0}^k \binom{n}{i} \pmod p$ . 我们考虑怎么拆开这个式子，一个核心的想法就是尽量往卢卡斯定理的形式上靠。

（以下的推导略去 $\pmod p$ ）

\sum_{i=0}^k \binom{n}{i}=\sum_{i=0}^k \binom{n/p}{i/p}\binom{n\%p}{i\%p}

然后我们发现：诶！好像 $i\% p$ 的取值只有 $p$ 个，而且 $n\% p$ 还是定值！所以我们考虑把 $\binom{n/p}{i/p}$ 按照 $i\% p$ 进行分类：

\begin{aligned} &\sum_{i=0}^k \binom{n/p}{i/p}\binom{n\%p}{i\%p}\\ =&\sum_{r=0}^{p-1} \Bigg(\binom{n\% p}{r}\cdot\sum_{i=jp+r}\binom{n/p}{i/p}\Bigg)+\binom{n/p}{k/p}\sum_{i=0}^{k\% p}\binom{n\% p}{i} \end{aligned}

在这个式子里，我们把 $k$ 个组合数分成两个部分:

一个是 $[0, k/p \cdot p-1]$ ，这一部分我们可以完整地分成 $p$ 组，每组 $k/p$ 个。
我们继续考察前半部分这个和式。我们可以写成两个和式的乘积：

$\Bigg(\sum_{r=0}^{p-1} \binom{n\% p}{r}\Bigg)\cdot\Bigg( \sum_{i=jp+r}\binom{n/p}{i/p} \Bigg)$
接着考察后半个和式 $i/p$ 的取值，我们发现，其实 $j$ 的取值就是 $[0, k/p-1]$ .
另一部分则是剩余的组合数 $k/p\cdot p\sim k$ ，他们无法按余数分成 $p$ 组，所以单独计算。
但是虽然无法按余数分组，但是他们的除以 $p$ 的商是一样的，所以我们在这里按商 $\binom{n/p}{k/p}$ 合并.

所以，上面这个式子可以写作：

\sum_{i=0}^k \binom{n}{i}=\Bigg(\sum_{r=0}^{p-1} \binom{n\% p}{r}\Bigg)\cdot\Bigg( \sum_{j=0}^{k/p-1}\binom{n/p}{j} \Bigg)+\binom{n/p}{k/p}\sum_{i=0}^{k\% p}\binom{n\% p}{i}

然后我们就发现了形式上相似的地方：记 $f(x,y)=\sum_{i=0}^y \binom{x}{i}$ ，则有

f(n,k)=f(n\% p,p-1)\cdot f(n/p,k/p-1)+\binom{n/p}{k/p}\cdot f(n\% p, k\%p)

这就是 DP 递推啊！而且进一步的， $f(n\% p,p-1)$ 和 $f(n\% p, k\%p)$ 的状态数量只有 $p^2$ 个， $\binom{n/p}{k/p}$ 可以使用卢卡斯定理计算， $f(n/p,k/p-1)$ 则可以递归计算。

卢卡斯定理的计算过程是 $n,k$ 同步 $/p$ ，因此时间复杂度是 $O(\log n)$ 的。如果令 $f(x,y),x\le p,y\le p$ 进行 $O(p^2)$ 预处理计算，令计算 $f(n,k)$ 的复杂度为 $T(x)$ （这里 $n,k$ 的变化是同步除以 $p$ ，因此就使用一元了），则有

T(x)=O(1)\cdot T(x/p) + O(\log n)\cdot O(1)\\ T(x)=O(\log^2 n)

因此算上预处理，这道题的时间复杂度为 $O(p^2+T\log^2 n)$ .

Code

#include <iostream>
using i64       = long long;
constexpr int P = 2333;

// f(n, m) = sum_{i=0}^m C(n, i)    (mod p)
int fpow(i64 b, i64 p) {
    int res = 1;
    while (p) {
        if (p & 1) res = res * b % P;
        b = b * b % P;
        p >>= 1;
    }
    return res;
}

int C[P + 2][P + 2];
int F[P + 2][P + 2];
void init() {
    for (int i = 1; i <= P; ++i) C[0][i] = 0;
    C[0][0] = 1;

    for (int i = 1; i <= P; ++i) {
        for (int j = 0; j <= P; ++j) C[i][j] = 0;
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }

    // init F[][]
    for (int i = 0; i <= P; i++) F[i][0] = 1;
    for (int row = 0; row <= P; row++) {
        for (int col = 1; col <= P; col++) F[row][col] = (F[row][col - 1] + C[row][col]) % P;
    }
}
int lucas(i64 n, i64 k) {
    if (k == 0 || n == k) return 1;
    if (n < k) return 0;
    return C[n % P][k % P] * lucas(n / P, k / P) % P;
}

int f(i64 n, i64 k) {
    if (n <= P and k <= P) return F[n][k];
    return (F[n % P][P - 1] * f(n / P, k / P - 1) % P + lucas(n / P, k / P) * F[n % P][k % P] % P) % P;
}

void run() {
    i64 n, k;
    std::cin >> n >> k;

    std::cout << f(n, k) << '\n';
}

int main() {
    init();
    int T;
    std::cin >> T;
    while (T--) run();
}

[SHOI2015] 聚变反应炉

$65$ 分想法：因为 $c_i=0$ 时，我们总是必须取所有点，答案为 $\sum d_i$ ，因此有 $c_i$ 时，考虑总是贪心选择点，使得其能够减少最多的能量消耗。

看到当 $c\le 5$ 时， $n\le 2000$ ，思考是不是可能是 $O(n^2)$ 的算法。由于前 $50$ 分我们使用的是贪心算法，所以这次我们考虑能否 DP.

树形 DP 我们通常可以考虑将 dp[u] 设置为某个与其子树相关的状态。这里，我们令 dp[u] 表示把 $u$ 子树全部激活的最小 cost.

然后我们就能发现一个问题：对于 $u$ 的儿子 $v_i$ ，我们可以一部分 $v_i$ （以及其子树）先激活，再激活 $u$ ，再激活剩余的 $v_j$ （以及其子树）. 考虑把“先于 $u$ 激活的子树”、“后于 $u$ 激活的子树”都视为物品，于是我们发现，这是一个 $0/1$ 背包！

那么背包的容量是什么呢？考虑到若选取“先于 $u$ 激活的子树 $v$ ”这个物品，则 $d[u]$ 可以减免 $c[v]$ 的能量点，这一个形式就比较像背包容量。因此，我们可以令 $cap[u]=\min(d[u], \sum\limits_{v\in u.son} c[v])$ 作为背包容量。那么顺理成章地，我们就令 $c[v]$ 作为“先于 $u$ 激活的子树 $v$ ” 的 cost，“后于 $u$ 激活的子树 $v$ ” 的 cost 视作 $0$ .

顺便也改一下状态：令 dp[u, c] 表示如果 $u$ 从儿子节点接受了总计 $c$ 点能量的辐射，那么还需要 dp[u,c] 点能量才能激活整棵子树。

然后考察每一个物品的价值，我们希望最后背包的价值最小。先考虑“先于 $u$ 激活的子树 $v$ ”，其激活不受到 $u$ 的辐射，因此其价值就是

U_{v,0}=\min_{c\le cap[v]} \texttt{dp[v,c]}

对于“后于 $u$ 激活的子树 $v$ ”而言，从 $u$ 能传到 $v$ 的能量，首先不超过 $c[u]$ ，其次，还要考虑 $v$ 的儿子辐射给 $v$ 的能量（ $=d[v]-cost$ ），因此为 $\min_{cost\le cap[v]}(c[u], d[v]-cost)$ ，因此价值为激活子树所需能量去掉从 $u$ 传过来的能量，即

U_{v,1}=\min_{\texttt{cost}\le \texttt{cap[v]}}\Big(\texttt{dp[v,cost]-\(\min(\)c[u],d[v]-cost\()\)}\Big)

然后就是简单的 $0/1$ 背包问题了。后 $50$ 分的时间复杂度为 $O(cn^2)$ .

Code

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <utility>
#include <vector>
using vi  = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int, int>;

int n;
void case0(vi &d, vi &c) {
    assert(*std::ranges::max_element(c) == 0);
    std::cout << std::accumulate(d.begin(), d.end(), 0) << '\n';
}

void case1(vi &d, vi &c, vvi &G) {
    vi deg(d.size(), 0);
    for (int u = 1; u <= n; u++) deg[u] = G[u].size();

    std::set<pii, std::greater<pii>> S;
    std::queue<int> Q;
    for (int u = 1; u <= n; u++) S.insert({deg[u] * c[u], u});

    int ans = 0;
    vi vis(n + 1, false);
    while (!S.empty()) {
        auto [reduced, t] = *S.begin();
        S.erase(S.begin());
        Q.push(t);
        ans += d[t];
        d[t] = 0;

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            if (vis[u]) continue;
            vis[u] = true;

            for (auto v : G[u]) {
                if (d[v] <= 0) continue;
                d[v] -= c[u];
                S.erase({deg[v] * c[v], v});
                deg[v]--;
                S.insert({deg[v] * c[v], v});
                if (d[v] <= 0) Q.push(v);
            }
        }
    }

    std::cout << ans << '\n';
}

constexpr int inf  = 1e9;
constexpr int maxc = 1e4 + 5;

void case2(vi &d, vi &c, vvi &G) {
    vvi f(n + 1, vi(maxc, inf));
    vi cap(n + 1, 0);

    auto dfs = [&](auto &&F, int u, int fa) -> void {
        f[u][0]    = d[u];
        int totcap = 0;

        for (int v : G[u]) {
            if (v == fa) continue;
            totcap += c[v];
            F(F, v, u);
        }

        cap[u] = std::min(d[u], totcap);

        for (int v : G[u]) {
            if (v == fa) continue;

            int up = inf, down = inf; // up: u -> fa, down: fa -> u
            for (int i = 0; i <= cap[v]; i++) {
                up   = std::min(up, f[v][i]);
                down = std::min(down, f[v][i] - std::min(c[u], d[v] - i));
            }

            vi tmp(maxc, inf);
            for (int i = 0; i <= cap[u]; i++) {
                if (f[u][i] == inf) continue;
                tmp[i] = std::min(tmp[i], f[u][i] + down);

                int next_cap  = std::min(cap[u], i + c[v]);
                tmp[next_cap] = std::min(tmp[next_cap], f[u][i] + up - std::min(c[v], d[u] - i));
            }

            for (int i = 0; i <= cap[u]; i++) f[u][i] = tmp[i];
        }
    };
    dfs(dfs, 1, 0);
    auto ans = *std::ranges::min_element(f[1]);
    std::cout << ans << '\n';
}

int main() {
    std::cin >> n;

    vi d(n + 1, 0), c(n + 1, 0);
    vvi G(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> d[i];
    for (int i = 1; i <= n; i++) std::cin >> c[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    if (*std::ranges::max_element(c) == 0) case0(d, c);
    else if (*std::ranges::max_element(c) == 1) case1(d, c, G);
    else case2(d, c, G);
}

[SHOI2015] 激光发生器

计算几何题，但是细节有点多……

因为只要反射十次，而且只有 $100$ 面镜子，所以我们可以直接模拟光线轨迹。

每次模拟中，我们计算当前射线与每一面镜子的交点（要保证在线段上），那么距离射线起点最近的就是光线的反射点。

然后取出镜子的法向量，注意要和光线在镜子的同一侧（可以使用点积判断）。计算法向量和入射光线的夹角，乘上 $\lambda$ 就是反射角，那么就直接旋转法向量即可。当然这里要判断一下应该逆时针旋转还是顺时针旋转。

还有要注意的点是，计算夹角时要考虑浮点数误差，即先对 $\cos$ 的值取 clamp(-1, 1) 然后再 std::acos() 比较稳妥。

Code

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>
constexpr int N      = 110;
constexpr double EPS = 1e-9;
struct pvec {
    double x, y;
    pvec operator+(const pvec &other) const { return {x + other.x, y + other.y}; }
    pvec operator-(const pvec &other) const { return {x - other.x, y - other.y}; }
    pvec operator*(double t) const { return {x * t, y * t}; }
};
struct segment {
    pvec s, d, e;
    double lambda;
};

int n;
segment seg[N], current;
int vis[N];
std::vector<int> order;

//! methods
// -1 if a < b, 0 if a == b, 1 if a > b
int sign(double a, double b);
double cross(const pvec &, const pvec &);
double dot(const pvec &, const pvec &);
double dist(const pvec &, const pvec &);
double angle(const pvec &, const pvec &);
pvec normalize(const pvec &);
pvec rotate_anticlock(const pvec &, const double &);
bool do_intersect(const segment &, const segment &);
bool on_segment(const pvec &, const segment &);
// assuming all lines, does not check parallel
pvec intersect(const segment &, const segment &);

int main() {
    std::cin >> current.s.x >> current.s.y >> current.d.x >> current.d.y;
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        double a, b;
        std::cin >> seg[i].s.x >> seg[i].s.y >> seg[i].e.x >> seg[i].e.y >> a >> b;
        seg[i].lambda = a / b;
        seg[i].d.x    = seg[i].e.x - seg[i].s.x;
        seg[i].d.y    = seg[i].e.y - seg[i].s.y;
    }

    // iteration
    std::vector<std::pair<pvec, int>> pts;
    for (int _ = 1; _ <= 10; _++) {
        pts.clear();
        for (int i = 1; i <= n; i++) {
            if (sign(cross(seg[i].d, current.d), 0) == 0) continue; // parallel
            auto res = intersect(current, seg[i]);
            if (do_intersect(current, seg[i])) pts.push_back({res, i});
        }

        if (pts.empty()) break;
        std::sort(pts.begin(), pts.end(), [&](const auto &a, const auto &b) {
            return dist(a.first, current.s) < dist(b.first, current.s);
        });

        int idx = pts[0].second;
        order.push_back(idx), vis[idx] = true;
        pvec res = pts[0].first;

        pvec input_d     = normalize(current.d);
        pvec reverse_d   = {-input_d.x, -input_d.y}; // reverse direction
        pvec mirror_base = normalize(seg[idx].d);
        pvec normal_d    = {mirror_base.y, -mirror_base.x}; // rotate 90 degrees

        if (dot(input_d, normal_d) > 0) normal_d = normal_d * (-1); // 同侧
        double cosA = dot(reverse_d, normal_d);
        assert(sign(cosA, -1) >= 0 && sign(cosA, 1) <= 0); // cosA should be in [-1, 1]
        double alpha = std::acos(std::max(-1.0, std::min(1.0, cosA)));
        double beta  = seg[idx].lambda * alpha; // angle of reflection

        pvec new_d;
        if (cross(normal_d, reverse_d) < 0) new_d = rotate_anticlock(normal_d, beta);
        else new_d = rotate_anticlock(normal_d, -beta);
        res = res + new_d * 1e-5; // move a bit forward to avoid numerical issues

        current.s = res;
        current.d = new_d;
        current.e = {current.s.x + current.d.x, current.s.y + current.d.y};
    }

    if (order.empty()) std::cout << "NONE\n";
    else {
        for (auto v : order) std::cout << v << " ";
        std::cout << "\n";
    }
}

int sign(double a, double b) {
    if (a < b - EPS) return -1;
    if (a > b + EPS) return 1;
    return 0;
}
double cross(const pvec &a, const pvec &b) { return a.x * b.y - a.y * b.x; }
double dot(const pvec &a, const pvec &b) { return a.x * b.x + a.y * b.y; }
double dist(const pvec &a, const pvec &b) { return std::sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
double angle(const pvec &a, const pvec &b) {
    double d = dot(a, b);
    double m = std::sqrt(dot(a, a) * dot(b, b));
    return std::acos(d / m);
}
pvec normalize(const pvec &v) {
    double len = std::sqrt(dot(v, v));
    return {v.x / len, v.y / len};
}
pvec rotate_anticlock(const pvec &v, const double &ang) {
    double cosa = std::cos(ang);
    double sina = std::sin(ang);
    return {v.x * cosa - v.y * sina, v.x * sina + v.y * cosa};
}
bool on_segment(const pvec &p, const segment &seg) {
    pvec v1 = seg.d;
    pvec v2 = {p.x - seg.s.x, p.y - seg.s.y};
    pvec v3 = {p.x - seg.e.x, p.y - seg.e.y};
    return sign(cross(v1, v2), 0) == 0 && sign(dot(v2, v3), 0) <= 0;
}
bool do_intersect(const segment &lazer, const segment &seg) {
    pvec pt   = intersect(lazer, seg);
    pvec dvec = {pt.x - lazer.s.x, pt.y - lazer.s.y};
    return on_segment(pt, seg) && sign(dot(dvec, lazer.d), 0) >= 0;
}
pvec intersect(const segment &a, const segment &b) {
    double div = cross(b.d, a.d);
    pvec dif   = {a.s.x - b.s.x, a.s.y - b.s.y};
    double t   = cross(dif, b.d) / div;
    return {a.s.x + a.d.x * t, a.s.y + a.d.y * t};
}

[SHOI2015] 零件组装机

排除掉不连通、自环、重边的情况后，对于一张连通图 $G$ ，拿出和 $0$ 相邻的节点 $\{v\}$ ，考察一下 $size$ 可能的取值。根据题意我们有

$size\le \lfloor \frac{n}{2} \rfloor$ ，这是题目规定
由于和 $0$ 邻接，所以对于 $v_i\ge size \land v_i\equiv 0\pmod {size}$ 的节点来说，都应该和 $0$ 邻接。

那么，只要我们找到了这样的 $size$ 之后，就可以把这两部分之间的边全部断开，形成两张导出子图，再递归判断即可。

于是我们的任务变成了，怎么找到这样的 $size$ .

首先可以想到， $size$ 应该至多是 $\ge size$ 且与 $0$ 邻接的 $v_i$ 的最大公约数。例如， $G[0]=\{1,2,4,6,8\}$ ，那么 $size \le 4$ ，如果 $size=4$ ，则 $4,6,8=0\pmod 4$ 而这显然不对，模数应该是 $2$ 才能让这 $3$ 个数和 $0$ 连边，于是 $(4,6,8)=2$ . 所以为了让 $4=6=8=0 \pmod p$ ，那么必须有 $p|(4,6,8)$ .

那么 $size$ 可能是 $p$ 的约数吗？我们可以断言不可能，因为如果 $size\lt p$ 的话，那么 $4+size\lt 6$ 也应该和 $0$ 连边，但是并没有，所以我们只需要检验 $size=p=2$ 的情况，也就是 $v[i]=\texttt{suffix\_gcd}[i]$ ，然后 $O(n\log n)$ 检查是否正确连边、以及删去边，这一点可以用 std::vector<std::set<int>> 进行维护。总时间复杂度为 $O(n\log^2 n)$

Code

#include <iostream>
#include <numeric>
#include <set>
#include <vector>
constexpr int MAXN = 100005;
using vi           = std::vector<int>;
using si           = std::set<int>;

struct UnionFind {
    vi fa, size;
    UnionFind(int n) : fa(n), size(n, 1) {
        for (int i = 0; i < n; ++i) fa[i] = i;
    }
    int root(int u) { return u == fa[u] ? u : fa[u] = root(fa[u]); }
    bool same(int u, int v) { return root(u) == root(v); }
    void merge(int u, int v) {
        int fu = root(u), fv = root(v);
        if (fu == fv) return;
        if (size[fu] < size[fv]) std::swap(fu, fv);
        fa[fv] = fu;
        size[fu] += size[fv];
    }
    bool check_connected() {
        bool ok = true;
        for (int i = 1; i < fa.size(); ++i) {
            if (!same(i, 0)) {
                ok = false;
                break;
            }
        }
        return ok;
    }
};

bool dfs(std::vector<si> &G, int L, int R) {
    if (L == R) return true;

    int length   = R - L + 1;
    int max_size = length / 2;

    int begin = L;
    vi nodes;
    for (auto v : G[begin])
        if (v >= L && v <= R) nodes.push_back(v - L);
    
    if (nodes.empty()) return false;

    int size = nodes.size();
    vi suffixgcd(size);
    suffixgcd[size - 1] = nodes[size - 1];
    for (int i = size - 2; i >= 0; i--) suffixgcd[i] = std::gcd(suffixgcd[i + 1], nodes[i]);

    int c_size = -1;
    for (int i = size - 1; i >= 0; i--) {
        if (suffixgcd[i] == nodes[i] && nodes[i] <= max_size) {
            c_size = nodes[i];
            break;
        }
    }

    if (c_size < 1) return false;

    // remove edges
    for (int u = L + c_size; u <= R; u++) {
        if (!G[u].contains(L + (u - L) % c_size)) return false; // no such edge
        G[u].erase(L + (u - L) % c_size);
        G[L + (u - L) % c_size].erase(u);
    }

    for (int u = L; u < L + c_size; u++) {
        if (G[u].empty()) continue;
        if (*G[u].rbegin() >= L + c_size) return false;
    }
    for (int u = L + c_size; u <= R; u++) {
        if (G[u].empty()) continue;
        if (*G[u].begin() < L + c_size) return false;
    }

    return dfs(G, L, L + c_size - 1) && dfs(G, L + c_size, R);
}

void run() {
    int n, m;
    std::cin >> n >> m;

    UnionFind uf(n);
    std::vector<si> G(n);
    bool is_valid = true;
    for (int i = 0, u, v; i < m; i++) {
        std::cin >> u >> v;
        if (u == v || G[u].contains(v)) is_valid = false;
        G[u].insert(v);
        G[v].insert(u);
        uf.merge(u, v);
    }

    is_valid &= uf.check_connected();
    if (!is_valid) return void(std::cout << "NO\n");
    else std::cout << (dfs(G, 0, n - 1) ? "YES\n" : "NO\n");
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) run();
}