JOISC 2019 题目合集

说好的加训，结果加的跟没加一样。人啊，要支棱起来啊！

欢迎收看 10 月大型新番

点赞越多，更新越快！

为了格式统一，本文没有任何的二级标题。

Start：2023/10/04 18:??。
Done：2023/10/09 01:56。

这么慢啊！什么摆怪！受不了了啊喂喂！

别慌~

Day1

A，B，C。

A. 考试

直接三维偏序即可。代码。

B. 聚会

Portal.

给定一棵 $n(n\le 2000)$ 个节点的树，要求找到树的形态，可以调用最多 $10^5$ 次询问：

Query(x, y, z)：返回树上的一个点，这个点到三个点的距离和最小。

一个非常笨 B 的做法。

每次在树上随机出一条链，询问树上所有的点，能够成为答案的一定是链上的点。对于链，随机中点分治处理；剩下的部分依然是树，递归处理。

消耗的询问不超过 $25000$ 次，这个做法大概可以说明随机分治具有一定的正确性？

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

mt19937 Rand(time(0)); 

inline void answer(int x, int y) {
    if (x > y) swap(x, y); 
    Bridge(x, y); 
}

void dfs(vector<int> a, int x, int y) {
    if (a.empty()) return answer(x, y); 
    if (a.size() == 1) return answer(x, a[0]), answer(a[0], y); 
    int mid = a[Rand() % a.size()]; 
    vector<int> al, ar; 
    for (int i : a) if (i != mid) {
        if (Query(x, mid, i) == i) al.emplace_back(i); 
        else ar.emplace_back(i); 
    }
    dfs(al, x, mid); dfs(ar, mid, y); 
}

void solve(vector<int> a) {
    if (a.size() <= 1) return; 
    int n = a.size(), x = a[Rand() % n], y = a[Rand() % n]; 
    while (x == y) y = a[Rand() % n]; 

    map<int, vector<int>> mp; 
    mp[x].emplace_back(x); mp[y].emplace_back(y); 
    for (int i : a) if (i != x && i != y) mp[Query(x, y, i)].emplace_back(i); 
    vector<int> chain; 
    for (auto [p, q] : mp) if (p != x && p != y) chain.emplace_back(p); 
    dfs(chain, x, y); 
    for (auto [p, q] : mp) solve(q); 
}

void Solve(int n) {
    vector<int> a(n); 
    for (int i = 0; i < n; ++i) a[i] = i; 
    solve(a); 
}

C. 馕

Portal.

一个长度为 $L$ 的激光剑被分为 $L$ 段，每段一个单位长度，第 $i$ 段为第 $j$ 种口味。

$N$ 个人来吃激光剑，第 $i$ 个人吃一个单位长度的 $j$ 口味的激光剑会分泌 $V_{i,j}$ 的多巴胺。

构造一个顺序，给每个人划分一段激光剑，每个人获得一定的长度。

构造一种方案，每个人分泌的多巴胺大于自己吃掉整个激光剑的多巴胺的 $\frac 1 n$ ，或者报告无解。

$n,L\le 2000$ 。

比较显然的是，考虑让每个人恰好吃他总收益的 $\frac 1 n$ 。考虑每个人的 $n$ 等分点，贪心取所有人中 $n$ 等分点最短的一段，然后直接划给这个人，因为他消耗的最少，这样一定是不劣的。

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
typedef __int128 lll; 

int n, L, c[2005]; 
i64 v[2005][2005]; 
struct Frac {
    i64 x, y; 
    Frac(i64 x = 1, i64 y = 0) : x(x), y(y) {}
    bool operator< (const Frac &a) const { return (lll)x * a.y < (lll)a.x * y; }
    bool operator>= (const Frac &a) const { return (lll)x * a.y >= (lll)a.x * y; }
} a[2005][2005]; // 第 i 个人的第 j 等分段在哪里结束

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> L; 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= L; ++j) cin >> v[i][j]; 
    for (int id = 1; id <= n; ++id) {
        i64 s = 0, cur = 0; 
        for (int i = 1; i <= L; ++i) s += v[id][i]; 
        int j = 1; 
        for (int i = 1; i <= L; ++i) {
            while (j <= n && Frac(cur + v[id][i], 1) >= Frac(s * j, n))
                a[id][j] = Frac(s * j - cur * n + n * v[id][i] * (i - 1), n * v[id][i]), 
                ++j; 
            if (j > n) break; 
            cur += v[id][i]; 
        }
    }
    static bool vis[2005]; memset(vis, 0, sizeof vis); 
    for (int i = 1; i <= n; ++i) {
        Frac res; int t = 0; 
        for (int j = 1; j <= n; ++j) if (!vis[j] && a[j][i] < res) 
            res = a[j][i], t = j; 
        vis[t] = 1; c[i] = t; 
        if (i != n) cout << res.x << " " << res.y << "\n"; 
    }
    for (int i = 1; i <= n; ++i) cout << c[i] << " \n"[i == n]; 
    return 0; 
}

Day2

A，B，C。

A. * 两个天线

Portal.

$n$ 个天线，相邻距离为 $1$ ，高度为 $H_i$ 。天线 $i$ 向天线 $j$ 可以发消息，通信成本为 $|H_i-H_j|$ ，当且仅当它们之间的距离 $D_{i,j}\in [A_i,B_i]$ 。

多次询问区间中可以相互发送信息的天线的最大值。

$n\le 2\times 10^5$ 。

考虑离线，所有询问按 $R$ 排序。绝对值不好处理，拆了正反各做一遍。

每次新增一个可行的 $j$ ，将可行的 $i$ 加入答案集合。对 $y$ 来说合法的 $x$ 区间是 $[y-B_y,y-A_y]$ ， $x$ 需要满足 $y\in [x+A_x,x+B_x]$ ，典型的扫描线。

#include <bits/stdc++.h>
using namespace std; 
const int INF = 1e9; 
const int N = 800000; 

int mxA[800005], mxB[800005], tag[800005]; 
void clear(void) {
    fill(mxA + 1, mxA + N + 1, -INF); 
    fill(mxB + 1, mxB + N + 1, -INF); 
    fill(tag + 1, tag + N + 1, -INF);
}
inline void pushup(int o) {
    mxA[o] = max(mxA[o << 1], mxA[o << 1 | 1]); 
    mxB[o] = max(mxB[o << 1], mxB[o << 1 | 1]); 
}
inline void maketag(int o, int k) {
    tag[o] = max(tag[o], k); 
    mxB[o] = max(mxB[o], mxA[o] + k); 
}
inline void pushdown(int o) {
    maketag(o << 1, tag[o]); maketag(o << 1 | 1, tag[o]); 
    tag[o] = -INF; 
}
void updateA(int o, int l, int r, int x, int k) {
    if (l == r) return mxA[o] = k, void(); 
    pushdown(o); int mid = l + r >> 1; 
    if (x <= mid) updateA(o << 1, l, mid, x, k); 
    else updateA(o << 1 | 1, mid + 1, r, x, k); 
    pushup(o); 
}
void updateB(int o, int l, int r, int x, int y, int v) {
    if (x <= l && r <= y) return maketag(o, v), void(); 
    pushdown(o); int mid = l + r >> 1; 
    if (x <= mid) updateB(o << 1, l, mid, x, y, v); 
    if (mid < y) updateB(o << 1 | 1, mid + 1, r, x, y, v); 
    pushup(o); 
}
int query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return mxB[o]; 
    pushdown(o); int mid = l + r >> 1, res = -INF; 
    if (x <= mid) res = max(res, query(o << 1, l, mid, x, y)); 
    if (mid < y) res = max(res, query(o << 1 | 1, mid + 1, r, x, y)); 
    return res; 
}

int n, q; 
int h[200005], a[200005], b[200005]; 
int l[200005], r[200005], ans[200005]; 
vector<pair<int, int> > Q[200005], A[200005]; 

void solve(void) {
    for (int i = 1; i <= n; ++i) Q[i].clear(), A[i].clear(); 
    for (int i = 1; i <= q; ++i) Q[r[i]].emplace_back(l[i], i); 
    for (int i = 1; i <= n; ++i) {
        if (i + a[i] <= n) A[i + a[i]].emplace_back(i, h[i]); 
        if (i + b[i] + 1 <= n) A[i + b[i] + 1].emplace_back(i, -INF); 
    }
    for (int i = 1; i <= n; ++i) {
        for (auto [p, v] : A[i]) updateA(1, 1, n, p, v); 
        if (i - a[i] >= 1) updateB(1, 1, n, max(1, i - b[i]), i - a[i], -h[i]); 
        for (auto [l, id] : Q[i]) ans[id] = max(ans[id], query(1, 1, n, l, i)); 
    }
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> h[i] >> a[i] >> b[i]; 
    cin >> q; memset(ans, -1, sizeof ans); 
    for (int i = 1; i <= q; ++i) cin >> l[i] >> r[i];  
    clear(); solve(); 
    reverse(h + 1, h + n + 1); reverse(a + 1, a + n + 1); reverse(b + 1, b + n + 1); 
    for (int i = 1; i <= q; ++i) l[i] = n - l[i] + 1, r[i] = n - r[i] + 1, swap(l[i], r[i]); 
    clear(); solve(); 
    for (int i = 1; i <= q; ++i) cout << ans[i] << "\n"; 
    return 0; 
}

B. ** 两种料理

Portal.

你要烹饪两道料理：闪耀的芝士蛋挞 和 深潜的极寒冰沙，分别有 $n,m$ 道工序，需要的时间是 $a_1,\cdots,a_n$ 和 $b_1,\cdots,b_m$ 分钟。

制作这两道料理都非常困难：一个步骤开始之后不能中断。到最后，你必须做完这两道料理。

如果你在比赛的前 $s_i$ 分钟完成了闪耀的芝士蛋挞的第 $i$ 个制作步骤，那么你可以获得 $p_i$ 的分数。

同理，在 $t_j$ 分钟前完成深潜的极寒冰沙的第 $j$ 个制作步骤可获得 $q_j$ 的分数。

问最大得分。 $n,m\le 10^6$ ，分数可能是负的。

太精彩啦！巨大的 $n,m$ 让人想只对闪耀的芝士蛋挞（以下称为 A 料理）DP，直接计算深潜的极寒冰沙（以下称为 B 料理）的贡献。但是做不了^[1]。

设 $f_{i,j}$ 代表完成 A 料理的前 $i$ 步，B 料理的前 $j$ 步的最大得分。看上去它的尽头就是 $O(nm)$ ，实则不然！

可以看作网格图上从 $(0,0)$ 走到 $(n,m)$ ，向右走代表完成 A 料理的一个步骤，向下走代表完成 B 料理的一个步骤。求出 $a,b$ 的前缀和 $sa,sb$ 。现在将贡献映射到点上，对于每个 $s_i$ ，找到最大的 $sb_j\le s_i-sa_i$ 的格点 $(i,j)$ ，它在路径的左上方（或路径上）便有贡献。同理对 $t_j$ 找到最大的 $sa_i\le t_j-sb_j$ ，那么它在路径的右下放就有贡献。

想办法将两种贡献点改成一样的。容斥！我们将 $p$ 先全部加上，然后减去严格在下面的。也就是说，将 $(i-1,j+1)$ 的贡献标记为 $-p_i$ 。也就是说，现在只需要最大化右下（包括路径上）的权值和。

每次考虑对前一列进行计算（先将 $y=0$ 和 $x=n$ 判掉）：

$f(x,y)=\max\{f(x,y-1),f(x-1,y)+\sum_{i=1}^y v(x-1,i)\}$

后缀加，前缀取 $\max$ ，维护差分数组，同 $x$ 的点按照 $y$ 从大到小加入，正数直接加入差分数组，负数的要找到这个 $y$ 让往上跑直到这个负的贡献没掉。

使用 map 维护，时间复杂度 $O((n+m)\log (n+m))$ 。

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int N = 1000005; 

int n, m; 
i64 a[N], s[N], p[N], b[N], t[N], q[N], ans; 
vector<pair<int, i64>> node[N]; 

void tag(int x, int y, i64 v) {
    if (x < 0 | y > m) return; 
    if (x == n || y == 0) return ans += v, void(); 
    node[x].emplace_back(y, v); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i] >> s[i] >> p[i], a[i] += a[i - 1]; 
    for (int i = 1; i <= m; ++i) cin >> b[i] >> t[i] >> q[i], b[i] += b[i - 1]; 
    for (int i = 1; i <= n; ++i) {
        int j = upper_bound(b, b + m + 1, s[i] - a[i]) - b - 1; 
        ans += p[i]; 
        tag(i - 1, j + 1, -p[i]); 
    }
    for (int j = 1; j <= m; ++j) {
        int i = upper_bound(a, a + n + 1, t[j] - b[j]) - a - 1; 
        tag(i, j, q[j]); 
    }
    map<int, i64> c; 
    for (int x = 0; x < n; ++x) {
        sort(node[x].begin(), node[x].end(), greater<pair<int, i64>>()); 
        for (auto [y, v] : node[x]) {
            if (v > 0) c[y] += v; 
            else {
                v = -v; 
                auto it = c.lower_bound(y); 
                while (v > 0 && it != c.end()) {
                    if (v >= it->second) v -= it->second, it = c.erase(it); 
                    else { it->second -= v; break; }
                }
            }
        }
    }
    for (auto [y, v] : c) ans += v; 
    cout << ans << "\n"; 
    return 0; 
}

C. 两种交通工具

神风敢死队炸毁了此处的内容。

通信题。

猜猜我是否还能回来做！对不起了！

Day3

A，B，C。

A. * 指定城市

Portal.

给定一棵树，双向边，每条边两个方向的权值不同。多次询问 $k$ ，表示选出 $k$ 个点，依次将以每个点为根的内向树边权赋值为 $0$ ，需要求出最后树的边权之和的最小值。要求 $O(n)$ 。

$w_x$ 代表以 $x$ 为根的内向树边权和，换根 DP 求出， $k=1$ 被解决。

贪心地想， $k>1$ 一定是再选一条链，长剖贪心即可。

但是 $k=2$ 时这一点不成立，需要使用换根 DP 解决。换完根之后将直径缩点，然后长剖贪心。

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, m; i64 sum, ans[200005]; 
struct edge {
    int v, c, d; 
    edge(int v = 0, int c = 0, int d = 0) : v(v), c(c), d(d) {}
}; 
vector<edge> G[200005]; 

i64 w[200005]; 
void dfs1(int x, int fa) { for (auto [y, c, d] : G[x]) if (y != fa) dfs1(y, x), w[x] += w[y] + d; }
void dfs2(int x, int fa) { for (auto [y, c, d] : G[x]) if (y != fa) w[y] = w[x] - d + c, dfs2(y, x); }

int f[200005]; i64 dis[200005]; 
void DFS(int x, int fa) {
    f[x] = fa; 
    for (auto [y, c, d] : G[x]) if (y != fa) dis[y] = dis[x] + c + d, DFS(y, x); 
}

bool vis[200005]; 
vector<i64> c; 
i64 solve(int x, int fa) {
    i64 res = 0; 
    for (auto [y, c, d] : G[x]) if (y != fa) {
        i64 w = solve(y, x) + c; 
        if (!res) res = w; 
        else ::c.emplace_back(min(res, w)), res = max(res, w); 
    }
    return res; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n; 
    for (int i = 1; i < n; ++i) {
        int u, v, c, d; cin >> u >> v >> c >> d; sum += c + d; 
        G[u].emplace_back(v, c, d); G[v].emplace_back(u, d, c);
    } dfs1(1, 0); dfs2(1, 0); 
    for (int i = 1; i <= n; ++i) ans[1] = max(ans[1], w[i]); 
    DFS(1, 0); int A = 1; 
    for (int i = 1; i <= n; ++i) if (dis[i] + w[i] > dis[A] + w[A]) A = i; 
    dis[A] = 0; DFS(A, 0); int B = 1; 
    for (int i = 1; i <= n; ++i) if (dis[i] + w[i] > dis[B] + w[B]) B = i; 
    ans[2] = (w[A] + w[B] + dis[B]) / 2; // +1 
    int x = B; while (x) vis[x] = 1, x = f[x]; x = B; 
    while (x) {
        for (auto [y, _c, _d] : G[x]) if (!vis[y]) 
            c.emplace_back(solve(y, x) + _c); 
        x = f[x]; 
    }
    sort(c.begin(), c.end(), greater<i64>()); 
    int t = 2; 
    for (i64 x : c) ans[t + 1] = ans[t] + x, ++t; 
    while (t < n) ans[t + 1] = ans[t], ++t; 
    for (cin >> m; m--; ) { int x; cin >> x; cout << sum - ans[x] << "\n"; }
    return 0;
}

B. 灯光表演

Portal.

$n$ 个灯有初始状态，一次操作可以区间打开/关闭/翻转，问变成目标状态的最小操作次数。 $n\le 10^6$ 。

手玩得到基础结论：

区间异或操作可以放到所有赋值操作之后；
区间赋值操作互不相交。

得到最后形态之后，区间异或操作次数为 $s'\operatorname{xor} t$ 的极长 $1$ 段数。

$f_{i,0/1/2}$ 代表以 $i$ 结尾，第 $i$ 位用 $0$ 、 $1$ 、保持原样来覆盖的最小代价。枚举上一位情况即可实现 $O(n)$ 转移。

#include <bits/stdc++.h>
using namespace std; 

int n; 
char s[1000005], t[1000005]; 
int f[1000005][3]; 

int main(void) {
    scanf("%d%s%s", &n, s + 1, t + 1); 
    memset(f, 0x3f, sizeof f); 
    f[1][0] = 1 + (t[1] == '1'); 
    f[1][1] = 1 + (t[1] == '0'); 
    f[1][2] = (s[1] != t[1]); 
    for (int i = 2; i <= n; ++i) {
        if (t[i] == '0') f[i][0] = min({f[i - 1][0], f[i - 1][1] + 1, f[i - 1][2] + 1}); 
        else f[i][0] = min({f[i - 1][0] + (t[i - 1] == '0'), f[i - 1][1] + (t[i - 1] == '1') + 1, f[i - 1][2] + (s[i - 1] == t[i - 1]) + 1}); 
        if (t[i] == '1') f[i][1] = min({f[i - 1][0] + 1, f[i - 1][1], f[i - 1][2] + 1}); 
        else f[i][1] = min({f[i - 1][0] + (t[i - 1] == '0') + 1, f[i - 1][1] + (t[i - 1] == '1'), f[i - 1][2] + (s[i - 1] == t[i - 1]) + 1}); 
        if (s[i] == t[i]) f[i][2] = min({f[i - 1][0], f[i - 1][1], f[i - 1][2]}); 
        else f[i][2] = min({f[i - 1][0] + (t[i - 1] == '0'), f[i - 1][1] + (t[i - 1] == '1'), f[i - 1][2] + (s[i - 1] == t[i - 1])}); 
    }
    printf("%d\n", min({f[n][0], f[n][1], f[n][2]})); 
    return 0; 
}

* C. 时间旅人

Portal.

$n$ 个点，第 $i$ 条路连接第 $i$ 和 $i+1$ 个点。第 $i$ 条路在 $[l_i,r_i]$ 时开放，通过一条路需要 $1$ 的时间，行动需要保证在穿梭的过程中道路一直是开放的。

Bitaro 是能穿梭时间的河狸，它在城市可以穿梭回一秒前。给定 $Q$ 次询问：

改变 $i$ 道路的开放时间。
假设 $B$ 时刻它在 $A$ 城，问最少需要进行多少次时间旅行才能在 $D$ 时刻前到达 $C$ 城。

$n,Q\le 3\times 10^5$ ，时间在 $10^9$ 级别。

显然走的方式很呆板：能走就走，不能走就时间旅行。现在假设 $A<C$ 。

设 $y$ 时刻的 $x$ 城市代表 $(x,y)$ ，套路地，为了避免行走时时间流逝的自然影响，将其改成 $(x,y-x)$ 。

用 $(a,b,c)$ 表示行动， $a$ 为开始时刻， $b$ 为结束时刻， $c$ 为时间倒流次数。 $(L,R)$ 代表这条道路只能在 $[L,R]$ 时通过。现在考虑如何合并：

两个二元：如果有交集则取交集，否则可以转化为三元组。
一二一三：观察二元组和 $a$ 的关系即可算出。
两个三元：计算中间时间穿越的次数即可。

最终答案用起终点的两个三元组加上中间路径的三元组即可得到。具有结合律，可以使用线段树维护。 $A>C$ 的情况是对称的。时间复杂度 $O((n+q)\log n)$ 。

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int INF = 1e9; 

int n, q; 
int l[300005], r[300005]; 

struct Node {
    int l, r; i64 val; 
    Node(int l = -INF, int r = INF, i64 val = -1) : l(l), r(r), val(val) {}
    friend Node operator+ (const Node &a, const Node &b) {
        if (a.val == -1 && b.val == -1) {
            if (a.l > b.r) return Node(a.l, b.r, a.l - b.r); 
            if (a.r < b.l) return Node(a.r, b.l, 0); 
            return Node(max(a.l, b.l), min(a.r, b.r)); 
        }
        if (a.val == -1) {
            if (b.l < a.l) return Node(a.l, b.r, b.val + a.l - b.l); 
            if (b.l > a.r) return Node(a.r, b.r, b.val); 
            return b; 
        }
        if (b.val == -1) {
            if (a.r < b.l) return Node(a.l, b.l, a.val); 
            if (a.r > b.r) return Node(a.l, b.r, a.val + a.r - b.r); 
            return a; 
        }
        return Node(a.l, b.r, a.val + b.val + max(0, a.r - b.l)); 
    }
}; 
struct Segment_Tree {
    Node T[1200005]; 
    void update(int o, int l, int r, int p, int x, int y) {
        if (l == r) return T[o] = Node(x, y, -1), void(); 
        int mid = l + r >> 1; 
        if (p <= mid) update(o << 1, l, mid, p, x, y); 
        else update(o << 1 | 1, mid + 1, r, p, x, y); 
        T[o] = T[o << 1] + T[o << 1 | 1]; 
    }
    void update(int p, int x, int y) { update(1, 1, n - 1, p, x, y); }
    Node query(int o, int l, int r, int x, int y) {
        if (x <= l && r <= y) return T[o]; 
        int mid = l + r >> 1; 
        if (y <= mid) return query(o << 1, l, mid, x, y); 
        if (mid < x) return query(o << 1 | 1, mid + 1, r, x, y); 
        return query(o << 1, l, mid, x, y) + query(o << 1 | 1, mid + 1, r, x, y); 
    }
    Node query(int x, int y) { return query(1, 1, n - 1, x, y); }
} tL, tR; 

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> q; 
    for (int i = 1; i < n; ++i) {
        cin >> l[i] >> r[i]; 
        tL.update(i, l[i] - i, r[i] - 1 - i); 
    }
    reverse(l + 1, l + n); reverse(r + 1, r + n); 
    for (int i = 1; i < n; ++i) tR.update(i, l[i] - i, r[i] - 1 - i); 
    while (q--) {
        int op; cin >> op; 
        if (op == 1) {
            int p, l, r; cin >> p >> l >> r; 
            tL.update(p, l - p, r - 1 - p); 
            p = n - p; tR.update(p, l - p, r - 1 - p); 
        } else {
            int a, b, c, d; cin >> a >> b >> c >> d; 
            if (a < c) cout << max(0ll, (Node(b - a, b - a) + tL.query(a, c - 1) + Node(d - c, d - c)).val) << "\n"; 
            else if (a == c) cout << max(0, b - d) << "\n";  
            else {
                a = n - a + 1; c = n - c + 1; 
                cout << max(0ll, (Node(b - a, b - a) + tR.query(a, c - 1) + Node(d - c, d - c)).val) << "\n"; 
            }
        }
    }
    return 0; 
}

Day4

A，B，C。

A. * 蛋糕拼接 3

Portal.

$n(n\le 2\times 10^5)$ 块蛋糕有自己的价值 $V_i$ 和颜色 $C_i$ ，需要选择 $M$ 块互不相同的蛋糕拼成一个环，蛋糕的美味程度为：

$\sum_{j=1}^M V_{k_j}-\sum_{j=1}|C_{k_j}-C_{k_j \bmod M+1}|$

给定 $M$ ，求出一个 $k$ ，问最大的美味程度。

如果选定了 $k$ ，那么按照 $C$ 排序算出贡献。

打表发现具有决策单调性，分治计算即可。

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int N = 200005; 

int n, m, nn; 
struct Cake {
    int v, c; 
    bool operator< (const Cake &a) const { return c < a.c; }
} a[N]; 
int b[N]; 

struct Node {
    int ls, rs; 
    int siz; i64 sum; 
} T[N * 40]; 
int rt[N], tot; 
int update(int pre, int l, int r, int x, int v) {
    int o = ++tot; T[o] = T[pre]; ++T[o].siz; T[o].sum += v; 
    if (l == r) return o; 
    int mid = l + r >> 1; 
    if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x, v); 
    else T[o].rs = update(T[pre].rs, mid + 1, r, x, v); 
    return o; 
}
i64 query(int p, int q, int l, int r, int k) { // 值域在 [l, r] 中的 V 最大 k 个的答案
    if (l == r) return 1ll * k * b[l]; 
    int mid = l + r >> 1, res = T[T[q].rs].siz - T[T[p].rs].siz; 
    if (res >= k) return query(T[p].rs, T[q].rs, mid + 1, r, k); 
    return query(T[p].ls, T[q].ls, l, mid, k - res) + T[T[q].rs].sum - T[T[p].rs].sum; 
}

i64 ans = -1e18; 
inline i64 calc(int l, int r) { return query(rt[l - 1], rt[r], 1, nn, m) - 2 * (a[r].c - a[l].c); }

void solve(int l, int r, int L, int R) { // 决策区间 [L, R]
    if (l > r) return; 
    int mid = l + r >> 1, p = 0, RR = min(R, mid - m + 1); 
    i64 mx = -1e18; 
    for (int i = L; i <= RR; ++i) {
        i64 w = calc(i, mid); 
        if (w > mx) mx = w, p = i; 
    } ans = max(ans, mx); 
    solve(l, mid - 1, L, p); solve(mid + 1, r, p, R); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i].v >> a[i].c, b[i] = a[i].v; 
    sort(b + 1, b + n + 1); sort(a + 1, a + n + 1); 
    nn = unique(b + 1, b + n + 1) - (b + 1); 
    for (int i = 1; i <= n; ++i) rt[i] = update(rt[i - 1], 1, nn, lower_bound(b + 1, b + nn + 1, a[i].v) - b, a[i].v); 
    solve(m, n, 1, n); 
    cout << ans << "\n"; 
    return 0; 
}

B. 合并

Portal.

$n(n\le 2\times 10^5)$ 个点的树，每个点有颜色，一次操作可以将两种操作并为一种颜色。

一棵树是不合法的，当且仅当存在一条边，没有任何一种颜色存在于两边。问使得树合法的最小操作数。

合并所有的两个相同颜色构成的链上的边，最后合并所有度数为 $1$ 的点，答案是 $\left\lceil \frac c 2 \right\rceil$ 。时间复杂度为 $O(n\log n)$ （并查集只路径压缩）。

#include <bits/stdc++.h>
using namespace std; 

int n, k, a[500005]; 
vector<int> G[500005]; 
int f[500005], dep[500005]; 

int bin[500005]; 
int find(int x) { return bin[x] == x ? x : bin[x] = find(bin[x]); }

void dfs(int x, int fa) {
    dep[x] = dep[f[x] = fa] + 1; bin[x] = x; 
    for (int y : G[x]) if (y != fa) dfs(y, x); 
}

int lst[500005]; 
void calc(int x, int y) {
    x = find(x); y = find(y); 
    while (x != y) {
        if (dep[x] < dep[y]) swap(x, y); 
        bin[x] = find(bin[f[x]]); 
        x = find(x); 
    }
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> k; 
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v; 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    } dfs(1, 0); 
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; 
        if (lst[a[i]]) calc(lst[a[i]], i); 
        lst[a[i]] = i; 
    }
    static int deg[500005]; memset(deg, 0, sizeof deg); 
    for (int i = 2; i <= n; ++i) {
        int x = find(f[i]), y = find(i); 
        if (x != y) ++deg[x], ++deg[y]; 
    }
    int cnt = 0; 
    for (int i = 1; i <= n; ++i) cnt += (deg[i] == 1); 
    cout << (cnt == 1 ? 0 : (cnt + 1) / 2) << "\n"; 
    return 0; 
}

* C. 矿物

Portal.

$2n(n\le 4.3\times 10^4)$ 个球， $n$ 种颜色每种恰好出现两次，需要将球配对。可以询问 $10^6$ 次：

插入/删除一个球，得到颜色种类数。

看到这个数据范围考虑分治。solve(A, B) 表示所有相同颜色的球一个在 $A$ ，另一个在 $B$ 。只需要对 $A$ 的前一半问一次，然后对 $B$ 全部问一次，就可以得到 $B$ 中的是否归 $A$ 的前一半的。

卡常卡到丧心病狂，中点分治不一定是最优，发现稍微小一点表现更好，随机偏移一下。同时，注意不要浪费非必要的询问。

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std; 

mt19937 Rand(time(0)); 
double rnd(double l, double r) { 
    return uniform_real_distribution<double>(l, r)(Rand); 
}
bool query(int x) {
    static int last = 0;
    int v = Query(x); 
    if (v == last) return 0; 
    return last = v, 1; 
}

void solve(vector<int> a, vector<int> b, bool in) {
    if (a.size() == 1) return Answer(a[0], b[0]); 
    vector<int> bl, br; 
    int m = max(1, int(a.size() * rnd(0.3, 0.5))); 
    for (int i = 0; i < m; ++i) query(a[i]); 
    for (int i : b) 
        if (bl.size() == m) br.emplace_back(i); 
        else if (br.size() == a.size() - m) bl.emplace_back(i); 
        else if (query(i) == in) bl.emplace_back(i); 
        else br.emplace_back(i); 
    solve(vector<int>(a.begin(), a.begin() + m), bl, !in); 
    solve(vector<int>(a.begin() + m, a.end()), br, in); 
}

void Solve(int n) {
    n <<= 1; vector<int> a, b; 
    static int id[200005]; 
    for (int i = 1; i <= n; ++i) id[i] = i; 
    shuffle(id + 1, id + n + 1, Rand); 
    for (int i = 1; i <= n; ++i) 
        if (query(id[i])) a.emplace_back(id[i]); 
        else b.emplace_back(id[i]); 
    solve(a, b, 1); 
}

总结

10/8 机房集体 CF 被所有人干烂了……

唉，加训，加训！

在笔者的设定中，闪耀的芝士蛋挞可以在暗夜中发出荧光，并且无毒，暂时没有想到如何制作；而深潜的极寒冰沙是世界上最寒冷的冰激凌，但是需要保证它的比热足够低，这样才能正常食用它。 ↩︎