XCPC wiki - 建模

二分图

Stop the Castle

There are n castles and m obstacles on a chessboard. Each castle or obstacle occupies exactly one cell and all occupied cells are distinct. Two castles can attack each other, if they’re on the same row or the same column, and there are no obstacles or other castles between them. Find a way to place the minimum number of additional obstacles onto the chessboard, so that no two castles can attack each other.

unordered_map<int, vector<pair<int, int>>> X, Y;
int n = read();
for (int i = 0; i < n; ++i) {
    int x = read(), y = read();
    X[x].emplace_back(y, 1);
    Y[y].emplace_back(x, 1);
}
int m = read();
for (int i = 0; i < m; ++i) {
    int x = read(), y = read();
    X[x].emplace_back(y, 0);
    Y[y].emplace_back(x, 0);
}

vector<array<int, 3>> boy, girl;
bool ugly = 0;
for (auto& [x, vec] : X) {
    sort(vec.begin(), vec.end());
    for (int j = 1; j < vec.size(); ++j) {
        auto& [y1, op1] = vec[j - 1];
        auto& [y2, op2] = vec[j];
        if (op1 && op2) {
            if (y1 + 1 == y2) ugly = 1;
            boy.push_back({ x, y1, y2 });
        }
    }
}
for (auto& [y, vec] : Y) {
    sort(vec.begin(), vec.end());
    for (int j = 1; j < vec.size(); ++j) {
        auto& [x1, op1] = vec[j - 1];
        auto& [x2, op2] = vec[j];
        if (op1 && op2) {
            if (x1 + 1 == x2) ugly = 1;
            girl.push_back({ y, x1, x2 });
        }
    }
}

n = boy.size(), m = girl.size();
vector<vector<int>> E(n);
for (int u = 0; u < n; ++u) {
    auto& [x, y1, y2] = boy[u];
    for (int v = 0; v < m; ++v) {
        auto& [y, x1, x2] = girl[v];
        if (x1 < x && x < x2 && y1 < y && y < y2) {
            E[u].push_back(v);
        }
    }
}

if (ugly) {
    printf("-1\n");
    return;
}

vector<int> npy(m, -1);
for (int u = 0; u < n; ++u) {
    vector<int> vis(m, 0);
    auto dfs = [&](this auto&& self, int u) -> bool {
        for (auto& v : E[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            if (npy[v] == -1 || self(npy[v])) {
                npy[v] = u;
                return true;
            }
        }
        return false;
    };
    dfs(u);
}

vector<pair<int, int>> res;
vector<int> happy(n, false);
for (int v = 0; v < m; ++v) {
    if (npy[v] != -1) {
        happy[npy[v]] = true;
        res.emplace_back(boy[npy[v]][0], girl[v][0]);
    }
    else {
        auto& [y, x1, x2] = girl[v];
        res.emplace_back(x1 + x2 >> 1, y);
    }
}
for (int u = 0; u < n; ++u) {
    if (!happy[u]) {
        auto& [x, y1, y2] = boy[u];
        res.emplace_back(x, y1 + y2 >> 1);
    }
}

printf("%d\n", res.size());
for (auto& [x, y] : res) {
    printf("%d %d\n", x, y);
}

CF1634E. Fair Share

Even a cat has things it can do that AI cannot. — Fei-Fei Li

题意 给定$m$ 个数组，第$i$ 个数组包含$n_i$ 个整数，保证$n_i$ 是偶数。另外还有两个初始为空的可重集$L,R$，将第$i$ 个数组中的所有数当中选出$\frac{n_i}{2}$ 个数放入$L$ 中，另一半则放入$R$ 中。问能否有一种方案满足$L=R$。数据范围：$1\leqslant m, n_i\leqslant2\times 10^5,\ 1\leqslant a_j\leqslant 10^9$。

思路 两种建模法：

1. 建二分图。$m$ 个数组作左部点，数组的每个值作右部点，键与值连边。根据题意，合法的图满足，每个左部点的度数为偶数，右部点的度数也为偶数。因此这个二分图存在欧拉回路则合法。
2. 建普通图。每个数组奇偶项连边，每个值出现的第奇偶次连边。这个图是二分图则合法。

int m;
cin >> m;
unordered_map<int, vector<int>> vec;
vector<vector<int>> g(200000);
vector<int> n(m);
int tot = 0;
for (int i = 0; i < m; i++) {
    cin >> n[i];
    for (int j = 0; j < n[i]; j++) {
        int x;
        cin >> x;
        if (j & 1) {
            g[tot].push_back(tot - 1);
            g[tot - 1].push_back(tot);
        }
        vec[x].push_back(tot);
        tot++;
    }
}

bool bipartite = true;
for (auto [k, v] : vec) {
    if (v.size() % 2) bipartite = false;
    for (int i = 1; i < v.size(); i += 2) {
        g[v[i]].push_back(v[i - 1]);
        g[v[i - 1]].push_back(v[i]);
    }
}

vector<int> c(tot, -1);
for (int s = 0; s < tot; ++s) {
    if (c[s] != -1) continue;
    c[s] = 0;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (auto& v : g[u]) {
            if (c[v] == -1) {
                c[v] = 1 ^ c[u];
                Q.push(v);
            }
            else if (c[v] == c[u]) {
                bipartite = false;
            }
        }
    }
}

if (!bipartite) {
    cout << "NO\n";
}
else {
    cout << "YES\n";
    int tot = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n[i]; j++) {
            cout << (c[tot++] == 1 ? "L" : "R");
        }
        cout << "\n";
    }
}

一笔画

CF1981D. Turtle and Multiplication

题意 给定$n$，构造一个长度为$n$ 的整数数列$a$，满足：

• $1 \leqslant a_i \leqslant 3 \times 10^5$；
• $\forall 1 \leqslant i<j\leqslant n-1$，有$a_i \cdot a_{i + 1} \neq a_j \cdot a_{j + 1}$，即相邻两项之积两两互不相等；
• 最小化数列中的不同元素个数。

数据范围：$2 \leqslant n \leqslant 10^6$。

思路 取$a_{i}$ 为 素数。这是由于$a_i \cdot a_{i + 1} = a_j \cdot a_{j + 1}$ 的 必要条件 是无序对$(a_i, a_{i + 1})$ 和无序对$(a_j, a_{j + 1})$ 相同。而如果$a_i$ 都取素数，这个必要条件就会变成 充要条件。

如果我们把$(a_i, a_{i + 1})$ 看成一条边，问题转化为找到点数最少的无向完全图（每个点还有一个自环），使得这个完全图存在一条经过$n - 1$ 条边且不经过重复边的路径。

考虑若完全图点数确定，我们如何计算这个完全图的最长不经过重复边的路径长度。设完全图点数为$m$，若$m$ 是奇数，那么每个点的度数都是偶数，所以这个图存在欧拉路径，路径长度即为边数，其等于$\frac{m(m - 1)}{2}+m=\frac{m(m + 1)}{2}$；若$m$ 是偶数，那么每个点的度数都是奇数，我们需要删除一些边使得这个图存在欧拉路径。容易发现一条边最多使奇度数点的数量减少$2$，所以我们至少需要删除$\frac{m}{2} - 1$ 条边，删除$(2, 3), (4, 5), \ldots, (m - 2, m - 1)$ 这些边即可，路径长度为$\frac{m(m - 1)}{2} - \frac{m}{2} + 1 + m = \frac{m^2}{2} + 1$。

当$n = 10^6$ 时最小的$m$ 是$1415$，第$1415$ 小的质数是$11807$，符合$a_i \leqslant 3 \cdot 10^5$。

时间复杂度$\Theta(n)$。

constexpr int N = 3e6 + 8;
bool isntPrime[N];
vector<int> prime;
void beforeT() {
    for (int i = 2; i < N; ++i) {
        if (!isntPrime[i]) prime.push_back(i);
        for (auto& p : prime) {
            if (p * i >= N) break;
            isntPrime[p * i] = 1;
            if (i % p == 0) break;
        }
    }
    isntPrime[1] = 1;
}

void eachT() {
    int num = read();

    int m = 1;
    while (num - 1 > ((m & 1) ? (m * (m + 1) / 2) : (m * m / 2 + 1)))
        ++m;

    vector<vector<pair<int, int>>> E(m + 1);
    int id = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = i; j <= m; ++j) {
            if (m % 2 == 0 && i % 2 == 0 && i + 1 == j) continue;
            E[i].emplace_back(j, ++id);
            E[j].emplace_back(i, id);
        }
    }

    vector<int> vis(id + 1);
    vector<int> path;
    auto dfs = [&](this auto&& self, int u) -> void {
        while (!E[u].empty()) {
            auto [v, id] = E[u].back();
            E[u].pop_back();

            if (vis[id]) continue;
            vis[id] = 1;

            self(v);
        }
        path.push_back(u);
    };
    dfs(1);

    for (int i = 0; i < num; ++i) {
        printf("%d ", prime[path[i]]);
    }
}

并查集

VJspr1G - Chemical table

题意 给出一个$n \times m$ 矩形，可以在格点上放置点，对于任意两行两列，如果相交的四个格子中有三个格子有点，那么第四个格子将自动放置一个点。起初已经有一些点，求最小手动添加点的次数，使得整个矩形内的格子都有点。

思路 用两个并查集分别存储行和列的连通状态，如果一行上有多个点，就将这些点所在的列连通，同理将每一列的几个点所在的行连通，统计行的连通图总数$S_1$ 以及列的连通图总数$S_2$，将所有连通图连通的最小边数是$\max\{S_1,S_2\}-1$。

值得思考的是，取最大值的原理是什么？

如样例二，竖着看是三个连通图，横着数是一个，那最终是三个连通图。这几个样例似乎都没问题，但直觉上有点面向样例编程了，得找个反例。

事实上，将点合并这个过程是正确的，但是没有点的部分会出现问题。比如$2 \times 2$ 的空格，正确答案是至少需要$3$ 步，但依此方法，竖着数是$2$ 个，横着数也是$2$ 个，答案是$1$ 步。

因此上述思路并不合理。

回到原问题，所求的是将所有连通图连通的最小边数，首先应思考，题给数据是如何连通的？不难发现，每一个点的作用实际上是将该行和该列连通，这也是“第四个格子将自动放置一个点”的原理。一句话概括，将行列视为点，将点视为边。因此，我们创建一个$n+m$ 大小的并查集，前$n$ 个元素代表行，后$m$ 个元素代表列，如果$(x,y)$ 有点，则连接$x$ 行（即$x$）和$y$ 列（即$y+n$）这两个元素，统计连通图总数$S$，结果是$S-1$。

int n = read(), m = read(), q = read();
DSU dsu(n + m);
while (q--) {
    int x = read(), y = read();
    dsu.uno(x, y + n);  // WA
}
int res = 0;
for (int i = 1; i <= n + m; ++i) {
    res += dsu.find(i) == i;
}
printf("%d\n", res - 1);

置换环

对于一个排列$p$，若连有向边$i\to p_{i}$，则整张图由若干个 环 (cycle)（包括长度为$1$ 的）组成，每个环称作 置换环。

每个置换环中，数组排序元素间所需 最小交换次数 为环上元素数量$- 1$。因此数组排序的最小交换次数为数组长度$-$ 置换环数量。如果只允许交换相邻项（冒泡排序），则最小交换次数等于逆序对的数量。

用 while 循环找置换环，时间复杂度$\Theta(n)$。

例 1（理解置换环）给定一长为$n$ 的字符串$s$ 与$1\sim n$ 的排列$p$。定义$s^0=s,s^k_i=s^{k-1}_{p_i}$。求最小的$k>0$ 使$s^k=s$。$n \leqslant 200$。

模拟置换的过程即可。

int n;
string s;
cin >> n >> s;
vector<int> p(n);
for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
}

ll res = 1;
vector<int> vis(n);
for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    int u = i;
    string cyc;
    do {
        cyc += s[u];
        vis[u] = true;
        u = p[u];
    } while (u != i);
    auto ncyc = cyc;
    int t = 0;
    do {
        t++;
        ncyc = ncyc.substr(1) + ncyc[0];
    } while (ncyc != cyc);
    res = lcm(res, t);
}

cout << res << "\n";

例 2 给定一个排列$p$，每次选择四个位置任意交换其中的元素，求排序的最小交换次数。(2024 牛客多校 4C - Sort4, [[…/contests/2024牛客多校/2024-07-25：2024牛客暑期多校训练营4#C - Sort4 (37)|2024-07-25：2024牛客暑期多校训练营4]])

考虑每个置换环，设环的长度为$s$：

• $s=3,4$ 可以一次排好；
• 两个$s=2$ 的环可以一次排好；
• 对于$s>4$ 的环，每次操作可以排好其中三个元素，环长变为$s-3$，记录有多少个环最终长度为$2$。

例 3 给定一个排列$p$，每次可交换排列中的任意两个数，求使得排列中有且仅有一个逆序对的最小交换次数。(CF1768D. Lucky Permutation)

考虑每个置换环，如果存在相邻元素，那么可以少交换一次，否则需要多交换一次。

int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
}

vector<vector<int>> cycs;
vector<int> vis(n);
for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    int u = i;
    vector<int> cyc;
    do {
        cyc.push_back(u);
        vis[u] = true;
        u = p[u];
    } while (u != i);
    cycs.push_back(cyc);
}

int res = 0, flag = 0;
for (auto& cyc : cycs) {
    sort(cyc.begin(), cyc.end());
    for (int j = 1; j < cyc.size(); j++) {
        flag |= cyc[j - 1] == cyc[j] - 1;
    }
    res += cyc.size() - 1;
}
cout << (res + 1 - 2 * flag) << "\n";

例 4 给定一个排列$p$，求一个排列$q$，满足$q^{2}=p$（即$q_{q_{i}}=p_{i}$）。(CF612E. Square Root of Permutation)

考虑每个置换环，如果环长为奇数，可构造五角星，如果是偶数，一个环内部无解，需要用两个大小相同的环构造，因此如果某个环长的环有奇数个则无解。

int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
}

vector<vector<vector<int>>> cycs(n + 1);
vector<int> vis(n);
for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    int u = i;
    vector<int> cyc;
    do {
        cyc.push_back(u);
        vis[u] = true;
        u = p[u];
    } while (u != i);
    cycs[cyc.size()].push_back(cyc);
}

vector<int> res(n);
bool ok = true;
for (int siz = 1; siz <= n; siz++) {
    if (siz & 1) {
        for (auto& cyc : cycs[siz]) {
            for (int i = 0; i < siz; i++) {
                res[cyc[i]] = cyc[(i + (siz + 1) / 2) % siz];
            }
        }
    } else if (cycs[siz].size() % 2 == 1) {
        ok = false;
        break;
    } else for (int k = 1; k < cycs[siz].size(); k += 2) {
        vector<int>& L = cycs[siz][k - 1], &R = cycs[siz][k];
        for (int i = 0; i < siz; i++) {
            res[L[i]] = R[i];
            res[R[i]] = L[(i + 1) % siz];
        }
    }
}

if (!ok) {
    cout << "-1\n";
} else for (int i = 0; i < n; i++) {
    cout << ++res[i] << " ";
}

例 5 给定两个排列$a,b$，求一个排列满足$a_{i}=p_{a_{i}},\ b_{i}=p_{b_{i}}$，最大化$\sum|a_{i}-b_{i}|$。(CF1978E. Tokitsukaze and Two Colorful Tapes)

连边$a_{i}\to b_{i}$，问题转化为：给环重新赋值，最大化环上相邻两个数差的绝对值之和。

猜测大小交替，手玩发现先最大再次大是没有影响的，也就是说可以选择任意大于$\cfrac{n}{2}$ 的作为大数，任意小于$\cfrac{n}{2}$ 的作为小数，如此交替。这确实是对的，但是有个问题，奇环如何处理？大小大是不行的，因为最后一个无论填什么对答案都没有影响，所以应该留到最后。

int n;
cin >> n;
vector<int> pos(n), p(n);
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    pos[x] = i;
}
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    p[i] = pos[x];
}

vector<vector<int>> cycs;
vector<int> vis(n);
for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    int u = i;
    vector<int> cyc;
    do {
        cyc.push_back(u);
        vis[u] = true;
        u = p[u];
    } while (u != i);
    cycs.push_back(cyc);
}

int min = 1, max = n;
vector<int> ans(n, -1);
for (auto& cyc : cycs) {
    int siz = cyc.size();
    for (int i = 0; i < siz - siz % 2; ++i) {
        ans[cyc[i]] = i & 1 ? min++ : max--;
    }
}
for (int i = 0; i < n; i++) {
    if (ans[i] == -1) ans[i] = min++;
}

ll res = 0;
for (int i = 0; i < n; i++) {
    res += abs(ans[i] - ans[p[i]]);
}
cout << res << "\n";

例 6 给定$n$ 个二元组$(a_{i},b_{i})$，可以按任意次序重新排序，问能否使得排序后数组$\lbrace a \rbrace$ 的逆序对数和$\lbrace b \rbrace$ 的逆序对数相同，给出方案。(2024 ICPC 台湾 C. Cards)

将每个置换环排在一起，每个环内部按环的顺序排列。如果环长为奇数，选取中位数作为$a$ 的起点，由于内部按环的顺序排列，故同时这个数也是$b$ 的终点，不难证明这部分两数组的逆序对数相同。如果环长为偶数，两个数组的逆序对数之差总是为奇数，因此如果有奇数个环长为偶数的环则无解，构造方式是对于两个环，一个选取中间较小的数为起点，另一个选取中间较大的数为起点。

int n;
cin >> n;
vector<pair<int, int>> a(n);
vector<int> pos(n), p(n);
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    pos[x] = i;
    a[i].first = x;
}
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    x--;
    p[i] = pos[x];
    a[i].second = x;
}

vector<vector<pair<int, int>>> cycs;
vector<int> vis(n);
for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    int u = i;
    vector<pair<int, int>> cyc;
    do {
        cyc.push_back(a[u]);
        vis[u] = 1;
        u = p[u];
    } while (u != i);
    cycs.push_back(cyc);
}

int tot = 0, cnt = 0;
vector<pair<int, int>> res(n);
for (auto& cyc : cycs) {
    const int m = cyc.size();
    if (m % 2 == 0) cnt++;

    auto tmp = cyc;
    sort(tmp.begin(), tmp.end());
    auto mid = tmp[(m - (cnt % 2)) / 2];

    for (int i = 0; i < m; i++) {
        if (cyc[i] == mid) {
            for (int j = 0; j < m; j++) {
                res[tot++] = cyc[(i + j) % m];
            }
        }
    }
}


if (cnt % 2 == 1) {
    cout << "No\n";
} else {
    cout << "Yes\n";
    for (int i = 0; i < n; i++) {
        cout << ++res[i].first << " \n"[i == n - 1];
    }
    for (int i = 0; i < n; i++) {
        cout << ++res[i].second << " \n"[i == n - 1];
    }
}

蝌蚪图

CF1787D. Game on Axis

思路 有一个包含$n$ 个点的棋盘，第$i$ 个点上有数字$a_i$，初始棋子在点$1$。当棋子在点$i$ 时：

• 若$1\le i\le n$，则你会跳到点$i+a_i$ ($-n \leqslant a_{i} \leqslant n$)；
• 否则游戏结束。

在游戏开始前，你可以选择一对$x$ 和$y$ ($1 \leqslant x \leqslant n,-n \leqslant y \leqslant n$)，并将$a_x$ 赋值为$y$。请求出这样的$(x,y)$ 的对数使得可以在有限步内结束游戏。

思路 连边$i\leftarrow i+a_{i}$，不在$1\sim n$ 范围内的点合并为一个超级点$0$。

分析这张图。每个点的入度一定为$1$，而且总共只有$n$ 条边，因此对于每个连通块，要么是有向树，要么是一个有向环带若干个树尾巴（下称蝌蚪），边的方向是从根到叶。

这就有两种情况，起点要么在蝌蚪上，要么不在。对于前者，合法的方法数是从蝌蚪路径上任意一个点跳到树上；对于后者，不合法的方法数是树的叶连接了根，或者从路径上任意一个点跳到蝌蚪上。

样例较弱，推式子需细心。

int n;
cin >> n;
vector<vector<int>> E(n + 1);
vector<int> p(n + 1);
for (int u = 1; u <= n; u++) {
    int x;
    cin >> x;
    int v = u + x;
    if (v > n || v < 1) v = 0;
    E[v].push_back(u);
    p[u] = v;
}

vector<int> vis(n + 1), siz(n + 1, 1);
auto dfs = [&](this auto&& self, int u) -> void {
    for (auto v : E[u]) {
        if (vis[v]) continue;
        vis[v] = 1;
        self(v);
        siz[u] += siz[v];
    }
};
vis[0] = 1;
dfs(0);

int cnt = count(vis.begin(), vis.end(), 0);
ll ans = 0;
if (vis[1]) {
    int u = 1;
    while (u) {
        ans += siz[u] + cnt;
        u = p[u];
    }
    ans = 1ll * n * (2 * n + 1) - ans;
} else {
    int u = 1;
    while (u && vis[u] != 2) {
        vis[u] = 2;
        ans += (2 * n + 1) - cnt;
        u = p[u];
    }
}
cout << ans << "\n";

2023 ICPC 杭州 H. Sugar Sweet II

题意$n$ 个数，有$n$ 个事件，如果$a_{i}<a_{b_{i}}$，则$a_{i}\leftarrow a_{i}+w_{i}$。事件随机顺序发生，问每个数的期望。([[…/contests/VP/2024-10-23-Autumn11-2023ICPC杭州|2024-10-23-Autumn11-2023ICPC杭州]])

思路 要求的就是每个事件发生的概率。事件只有三类：必然发生、必然不发生、发生当前仅当$b_{i}$ 发生，对于第三者，其概率为$\frac{1}{d_{i}!}$，其中$d_{i}$ 表示有向图上最近的必然发生的事件对应的点（起点）的距离，用这些边建反图，从每个起点 DFS 处理出距离。

时间复杂度$\Theta(n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 3e5, mod = 1e9 + 7;
ll fac[N], ifac[N];

ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    fac[1] = 1;
    for (int i = 2; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 1; i >= 2; i--) {
        ifac[i - 1] = ifac[i] * i % mod;
    }

    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n), b(n), w(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            b[i]--;
        }
        for (int i = 0; i < n; i++) {
            cin >> w[i];
        }

        vector<int> op(n);
        vector<vector<int>> E(n);
        vector<int> st;
        for (int i = 0; i < n; i++) {
            if (a[i] < a[b[i]]) {
                st.push_back(i);
            } else if (a[i] < a[b[i]] + w[b[i]]) {
                E[b[i]].push_back(i);
            }
        }

        vector<int> d(n);
        for (auto s : st) {
            auto dfs = [&](this auto&& self, int u) -> void {
                for (auto v : E[u]) {
                    d[v] = d[u] + 1;
                    self(v);
                }
            };
            d[s] = 1;
            dfs(s);
        }

        vector<ll> res(n);
        for (int i = 0; i < n; i++) {
            if (a[i] < a[b[i]]) {
                (res[i] += w[i]) %= mod;
            } else if (a[i] < a[b[i]] + w[b[i]]) {
                (res[i] += w[i] * ifac[d[i]]) %= mod;
            }
            (res[i] += a[i]) %= mod;
        }

        for (int i = 0; i < n; i++) {
            cout << res[i] << " \n"[i == n - 1];
        }
    }

    return 0;
}

差分约束

给出一组包含$m$ 个不等式，有$n$ 个未知数的不等式组，形如

$$\begin{cases} x_{c_{1}} - x_{c'_{1}} + w_{1} \geqslant 0 \\ x_{c_{2}} - x_{c'_{2}} + w_{2} \geqslant 0 \\ \cdots \\ x_{c_{m}} - x_{c'_{m}} + w_{m} \geqslant 0 \end{cases}$$

求任意一组满足这个不等式组的解。

样例输入表示不等式组$\begin{cases} x_{2} - x_{1} + 3 \geqslant 0 \\ x_{3} - x_{2} - 2 \geqslant 0 \\ x_{3} + x_{1} + 1 \geqslant 0 \end{cases}$，即$\begin{cases} x_{2} + 3 \geqslant x_{1} \\ x_{3} - 2 \geqslant x_{2} \\ x_{3} + 1 \geqslant x_{1} \end{cases}$，输出表示$\lbrace x_{1},x_{2},x_{3} \rbrace = \lbrace 0,-2,0 \rbrace$ 是一组可行的解：

Input	Output
3 3 2 1 3 3 2 -2 3 1 1	0 -2 0

最短路求最大解

1. 将每个不等式$\pmb{x_{u}+w \geqslant x_{v}}$ 转化为一条从$u$ 走到$v$，权为$w$ 的 边。
2. 建立一个 虚拟源点，使得该源点一定可以遍历到所有边。
3. 跑一遍 负权图单源最短路 (Bellman - Ford)，时间复杂度$\Theta(mn)$：
   • 如果存在负环，表明不等式出现矛盾，则原不等式组一定无解；
   • 如果不存在负环，则$d_{i}$ 就是原不等式组的一个可行解，也是 最大解。

int n, m;
cin >> n >> m;

int N = n + 1;
vector<vector<pii>> E(N);
while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    E[u].push_back({ w, v });
}

int s = n;
for (int i = 0; i < n; i++) {
    E[s].push_back({ 0, i });
}

auto BellmanFord = [&](int s) {
    vector<bool> vis(N);
    vector<ll> dis(N, inf);
    dis[s] = 0;
    for (int t = 0; t < N; t++) {
        bool flag = 0;  // 判断一轮循环过程中是否发生松弛操作
        for (int u = 0; u < N; u++) {
            if (vis[u]) continue;
            for (auto [w, v] : E[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;  // 松弛
                    vis[v] = 0;
                    flag = 1;
                }
            }
            vis[u] = 1;
        }
        if (!flag) return dis;  // 没有可以松弛的边
    }
    return vector<ll>();  // N轮后仍存在可以松弛的边 存在负环
};

auto dis = BellmanFord(s);

if (dis.empty()) {
    cout << "-1\n\n";
} else for (int u = 0; u < n; u++) {
    cout << dis[u] << " \n"[u == n - 1];
}

最长路求最小解 将不等式化为$\pmb{x_{u}+w \leqslant x_{v}}$，再修改最短路的松弛条件，得到 负权图单源最长路，可求得 最小解。

	最短路求最大解	最长路求最小解
原始不等式	$x_{u}+w \geqslant x_{v}$（大于号）	$x_{u}+w \leqslant x_{v}$（小于号）
建边	从$i$ 走到$j$，权为$w$ 的边	从$i$ 走到$j$，权为$w$ 的边
初始化	dis[u] = inf	dis[u] = -inf
松弛条件	dis[v] > dis[u] + w	dis[v] < dis[u] + w
所得的解	最大解	最小解

杂题

CF1815C. Between

题意 给定整数$n,m$ 和$m$ 个整数数对$(a_i,b_i)$，构造一个满足下列所有要求的序列：

• 序列中的所有元素都应为$1\sim n$ 的整数。
• 序列中恰好有一个元素为$1$。
• 对于每个整数$i(1\leq i\leq m)$，都满足序列中任意两个位置不同且值为$a_i$ 的元素之间都存在至少一个值为$b_i$ 的元素。
• 在满足上述三条要求的情况下序列长度尽可能长。

如果满足上述前三条要求的序列可以达到任意大的长度，输出 INFINITE；否则输出 FINITE，并求出满足所有要求的任意一个序列。

思路 连边$b_{i}\to a_{i}$，从 1 开始 BFS，将同距离的存在一起，构造 4321432434。

int n, m;
cin >> n >> m;
vector<vector<int>> E(n);
while (m--) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    E[v].push_back(u);
}

vector<int> dis(n, -1);
queue<int> Q;
Q.push(0);
dis[0] = 0;
while (!Q.empty()) {
    int u = Q.front(); Q.pop();
    for (auto v : E[u]) {
        if (dis[v] != -1) continue;
        dis[v] = dis[u] + 1;
        Q.push(v);
    }
}

vector<vector<int>> vec(n);
bool finite = true;
for (int i = 0; i < n; i++) {
    if (dis[i] == -1) finite = false;
    else vec[dis[i]].push_back(i);
}

if (!finite) {
    cout << "INFINITE\n";
} else {
    cout << "FINITE\n";
    int max = *max_element(dis.begin(), dis.end());
    vector<int> res;
    for (int i = 0; i <= max; i++) {
        for (int j = max; j >= i; j--) {
            for (auto u : vec[j]) {
                res.push_back(u);
            }
        }
    }

    cout << res.size() << "\n";
    for (auto u : res) {
        cout << ++u << " ";
    }
    cout << "\n";
}

VJsum1K. Slime

题意 在一条直线上有$n$ 个史莱姆，每个史莱姆的坐标是$x_i$，吞噬半径是$r_i$。当一个史莱姆被吞噬时，就会发起攻击并吞噬其它史莱姆，如果另一个史莱姆所在位置$x_j$ 满足$|x_j-x_i| \leqslant r_i$ ，那么该史莱姆就会被吞噬。

如果第$i$ 个史莱姆先发起攻击，记最终会被吞噬的史莱姆个数为$f(i)$，现在，请你帮忙计算$\sum \limits_{i=1}^n i\times f(i)$，答案对$10^9 + 7$ 取模。

数据范围：$1\le n\leqslant 500000,\quad-10^{18}\leqslant x_{i}\leqslant 10^{18},\quad0\leqslant r_{i}\leqslant 2\times 10^{18}$。

题意 有一定技巧，需要建模而实现简单，码量大但大部分是抄板子，写起来很爽的好题，此外本题有使用史莱姆算法的纯思维的解法。

建模 若$x$ 能直接吞噬$y$，则在图上连边$y\to x$，最终能吞噬的个数$f(x)$ 即有向图上能到达$x$ 的点数。

连边 显然地，对于每个固定的$x$，所有的$y$ 都连续，也即是一个区间，记为$[l,r]$，于是需要连边$[l,r]\to x$。最坏情况下需要连$n^{2}$ 条边，空间无法接受，但区间连边提示我们，可以 线段树优化建图。时间$\Theta(n\log n)$，空间$\Theta(n)$。

连边函数：

// [l,r]向x连边
void addedge(int l, int r, int x, int p = 1, int cl = L, int cr = R) {
    if (l <= cl && cr <= r) return E[p].push_back(x);
    if (l <= mid) addedge(l, r, x, lson);
    if (mid < r)  addedge(l, r, x, rson);
}

根据线段树上的点的关系，子节点需要向父节点连边，这可以边建树边连：

// 建树 树上的边先连上
void build(int p = 1, int cl = L, int cr = R) {
    if (cl == cr) {
        w[p] = { cl,cl };
        rt[cl] = p;
        return;
    }
    E[ls].push_back(p);
    E[rs].push_back(p);
    build(lson);
    build(rson);
}

求能到达的点数 按 缩点模板题 的思路，跑肽键 (Tarjan) 和拓扑 (Topo)。时间$\Theta(n+m)=\Theta(n)$（边数$m=4n$），空间$\Theta(n)$。

和模板题不同，由于线段树上的点不是并列关系，不能简单地将点权相加。

比如把树上点 1 和$\mathrm{ls}$ 缩成一个点，点 1 实际上是原图中的$[1,n]$，是$n$ 个点的集合，同理点$\mathrm{ls}$ 是$[1,n/2]$ 这$n/2$ 个点的集合。如果简单粗暴地相加，得到的新点包将含$1.5n$ 个点，显然不是我们想要的。

因此用$l,r$ 记录每个史莱姆能吞噬的范围，缩点就是把这些史莱姆揉在一起，新史莱姆能吞噬的范围就是$[l_{\min},r_{\max}]$。

还是刚才的例子，把$[1,n]$ 和$[1,n/2]$ 缩在一起，得到的是$[1,n]$，实际上是$n$ 个点。

为了尽可能地减少代码修改，我们重新定义点权相加：

struct node {
    int l = 1e9, r;  // 吞噬范围
    node& operator+=(constexpr node& other) {
        l = min(l, other.l);
        r = max(r, other.r);
        return *this;
    }
} w[N];

这样调用 w[to]+=w[u] 即可，保证新范围是$[l_{\min},r_{\max}]$（即 w[u].l 到 w[u].r）的同时不需要修改肽键和拓扑里的任何代码。

计算 现在得到了缩点后每个点 u 能到达的范围 w[u].r - w[u].l + 1，那对于原图点 i，在线段树上的点编号是 rt[i]，缩点后编号是 fa[rt[i]]，它能到达的范围就是 w[fa[rt[i]]].r - w[fa[rt[i]]].l + 1。按题设求和即可。

总的时间$\Theta(n\log n)$，空间$\Theta(n)$。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using ll = long long;
constexpr int N = 2e6 + 8;
constexpr int MOD = 1e9 + 7;

inline ll read() {
    ll Y = getchar(), S = 0, C = 1;
    while (Y > 57 || Y < 48) { if (Y == 45) C = -1; Y = getchar(); }
    while (Y <= 57 && Y >= 48) { S = (S << 3) + (S << 1) + Y - 48; Y = getchar(); }
    return S * C;
}

/// ----------------结构体----------------
struct node {
    int l = 1e9, r;  // 吞噬范围
    node& operator+=(constexpr node& other) {
        l = min(l, other.l);
        r = max(r, other.r);
        return *this;
    }
} w[N];
int n, rt[N];

/// ----------------肽键和拓扑 都是抄板子----------------
vector<int> E[N];
vector<int> Etmp[N];
node wtmp[N];
int dfn[N], low[N], fa[N], unix;
stack<int> S;

void eachTarjan(int u) {
    dfn[u] = low[u] = ++unix;       // 记录DFS序
    S.push(u);
    // DP更新low[u]
    for (auto v : E[u]) {
        if (!dfn[v]) eachTarjan(v), low[u] = min(low[u], low[v]);
        else if (!fa[v]) low[u] = min(low[u], dfn[v]);
    }
    // u是SCC的根
    if (low[u] == dfn[u]) {
        int top;
        do {
            top = S.top(); S.pop();    // 出栈
            fa[top] = u;               // 记录u的子节点的根为u
        } while (top != u);            // 不断弹出直到根u弹出为止
    }
}

void tarjan(int n) {
    // Tarjan
    for (int u = 1; u <= n; ++u) {
        if (!dfn[u]) eachTarjan(u);
    }
    // 重构图 将子树的性质嫁接到SCC的根上
    for (int u = 1; u <= n; ++u) {
        for (auto v : E[u]) {
            if (fa[u] != fa[v]) Etmp[fa[u]].push_back(fa[v]);
        }                              // 存储新的边
        wtmp[fa[u]] += w[u];           // 存储新的边权
    }
    for (int u = 1; u <= n; ++u) {
        w[u] = wtmp[u];
        E[u] = Etmp[u];
        sort(E[u].begin(), E[u].end());
        E[u].erase(unique(E[u].begin(), E[u].end()), E[u].end());
    }
}

int deg[N];
void topo(int n) {
    for (int u = 1; u <= n; ++u) {
        for (auto v : E[u]) deg[v] += 1;
    }
    queue<int> Q;
    for (int u = 1; u <= n; ++u) {
        if (!deg[u] && u == fa[u]) Q.push(u);
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto to : E[u]) {
            w[to] += w[u];
            deg[to] -= 1;
            if (!deg[to]) {
                Q.push(to);
            }
        }
    }
}

/// ----------------线段树----------------
#define ls p<<1
#define rs p<<1|1
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

// 建树 树上的边先连上
void build(int p = 1, int cl = L, int cr = R) {
    if (cl == cr) return w[p] = { cl,cl }, rt[cl] = p, void();
    E[ls].push_back(p), build(lson);
    E[rs].push_back(p), build(rson);
}

// [l,r]向x连边
void addedge(int l, int r, int x, int p = 1, int cl = L, int cr = R) {
    if (l <= cl && cr <= r) return E[p].push_back(x);
    if (l <= mid) addedge(l, r, x, lson);
    if (mid < r)  addedge(l, r, x, rson);
}

/// ----------------主函数----------------
ll xi[N], ri[N];  // 1e18 范围需要 LL
int main() {
    n = read();

    for (int i = 1; i <= n; ++i) {
        xi[i] = read(), ri[i] = read();
    }

    build();
    for (int i = 1; i <= n; ++i) {
        int l = lower_bound(xi + 1, xi + n + 1, xi[i] - ri[i]) - xi,      // 二分找第一个大于等于 xi[i]-ri[i] 的 l 即是下界
            r = upper_bound(xi + 1, xi + n + 1, xi[i] + ri[i]) - xi - 1;  // 二分找第一个大于 xi[i]+ri[i] 的 r 即是上界上面的那一个 再 -1 即是上界
        addedge(l, r, rt[i]);   // Slime i will eat [l,r]
        // rt[] 数组表示 i 在新图上点的编号是 rt[i]
    }

    tarjan(n << 2), topo(n << 2);  // 缩个点再跑一圈

    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        res += 1ll * i * (w[fa[rt[i]]].r - w[fa[rt[i]]].l + 1);
        res %= MOD;
    }
    printf("%lld", res);

    return 0;
}

苯人正在研究 史莱姆算法，有机会再补。