比赛链接

A

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n, m;    cin >> n >> m;    ll suma = 0, sumb = 0;    for (int i = 1, x;i <= n;i++) cin >> x, suma += x;    for (int i = 1, x;i <= m;i++) cin >> x, sumb += x;    if (suma > sumb) cout << "Tsondu" << '\n';    else if (suma < sumb) cout << "Tenzing" << '\n';    else cout << "Draw" << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

B

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n, x;    cin >> n >> x;     int sum = 0;    for (int i = 0;i < 3;i++) {        bool ok = 1;        for (int j = 1;j <= n;j++) {            int val;            cin >> val;            ok &= (x | val) == x;            if (ok) sum |= val;        }    }     if (sum == x) cout << "YES" << '\n';    else cout << "NO" << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

C

题目

给定一个长为 $n$ 的数组 $a$ ，其中元素 $a_i \in[1,n]$ 代表颜色。

现在有一种操作：选择两个颜色相同的不同位置 $i,j$ ，然后删除 $[i,j]$ 这一段，删除操作会影响下标。

问最多能删除多少元素。

题解

知识点：线性dp。

设 $f_{i}$ 表示 $[1,i]$ 最多能删除的元素个数，有转移方程：

我们要优化这个转移，实际上我们只需要维护 $\max\limits_{j:a_j = a_i} \{ f_{j-1} -j+1 \}$ 即可。

设 $mx_j$ 表示在 $[1,i-1]$ 中颜色为 $j$ 的所有位置 $f_{j-1}-j+1$ 的最大值，每次求完 $f_i$ 更新 $mx_{a_i}$ 即可。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int a[200007];int mx[200007];int f[200007];bool solve() {    int n;    cin >> n;    for (int i = 1;i <= n;i++) cin >> a[i], mx[i] = -1e9;    for (int i = 1;i <= n;i++) {        f[i] = max(f[i - 1], mx[a[i]] + i);        mx[a[i]] = max(mx[a[i]], f[i - 1] - i + 1);    }    cout << f[n] << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

D

题目

有 $n$ 个朋友，编号为 $1$ 到 $n$ ，我们需要和他们玩最多 $n^2$ 轮游戏，每轮游戏需要选择其中的一些人一起玩，并选择要玩多久，要求是：

1. $1$ 号朋友必须被选中。
2. $n$ 号朋友不能被选中。
3. 所有人玩的时间需要遵守 $m$ 条约束。

一条约束描述为三个整数 $u,v,y$ ，表示朋友 $u$ 或朋友 $v$ 单独被选中玩的时间的总和不能超过 $y$ 。

问在如此约束下，最多能玩多久，构造一个满足的方案，并给出这个方案要玩几轮，以及每轮游戏选中了哪些人玩了多久。

题解

知识点：差分约束，构造。

由于 $n$ 一定不会被选中，而 $1$ 必须被选中。因此我们考虑将点分成两个集合：

1. 集合 $A$ 表示能和 $1$ 一起玩的。
2. 集合 $B$ 表示不能和 $1$ 一起玩的。

初始时，集合 $B$ 只有 $n$ ，剩下的都在集合 $A$ 。

显然，集合 $A$ 的朋友是可以一起玩的，但玩到一定时间会因为和 $n$ 的约束，有一些朋友就不能继续玩了，于是从集合 $A$ 中移出放入集合 $B$ ，剩下的继续玩。这个过程会逐步将朋友从 $A$ 移到 $B$ 。

实际上，我们考虑每个朋友 $u$ 移入 $B$ 的时间 $T_u$ ，那么对于任意两个有约束的朋友 $u,v$ 需要满足 $|T_u -T_v| \leq y$ 。对于这个问题，我们将朋友看作点，约束看作带权无向边，那么就构造了一个差分约束系统，用最短路即可解决，起点是 $n$ 。

我们在最短路过程中， $dis_u$ 即为 $T_u$ 。点一旦被确定距离，意味着这个时刻将点移出 $A$ ，一旦 $1$ 被确定就立刻结束。我们需要记录点被移出 $A$ 的顺序，顺序上相邻的两个点的距离差，就是这轮还未被放进集合 $B$ 的点玩的时间。

时间复杂度 $O((n+m)\log m)$

空间复杂度 $O(n+m)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; vector<pair<int, int>> g[107]; int n, m;ll dis[107];bool vis[107];struct node {    int v;    ll w;    friend bool operator<(const node &a, const node &b) { return a.w > b.w; }};priority_queue<node> pq;vector<int> ord;void dijkstra() {    for (int i = 1;i <= n;i++) dis[i] = 2e18, vis[i] = 0;    dis[n] = 0;    pq.push({ n,0 });    while (!pq.empty()) {        int u = pq.top().v;        pq.pop();        if (vis[u]) continue;        ord.push_back(u);        vis[u] = 1;        if (vis[1]) break;        for (auto [v, w] : g[u]) {            if (vis[v]) continue;            if (dis[u] + w < dis[v]) {                dis[v] = dis[u] + w;                pq.push({ v,dis[v] });            }        }    }} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    cin >> n >> m;    for (int i = 1;i <= m;i++) {        int u, v, w;        cin >> u >> v >> w;        g[u].push_back({ v,w });        g[v].push_back({ u,w });    }     dijkstra();    if (!vis[1]) {        cout << "inf" << '\n';        return 0;    }    cout << dis[1] << ' ' << ord.size() - 1 << '\n';    for (int i = 1;i < ord.size();i++) {        string s(n, '1');        for (int j = 0;j < i;j++) s[ord[j] - 1] = '0';        cout << s << ' ' << dis[ord[i]] - dis[ord[i - 1]] << '\n';    }    return 0;}

E

题目

给定 $k$ ，确定了平面直角坐标系中一条直线 $x+y = k$ 。

给出 $n$ 个点 $(x_i,y_i)$ ，满足坐标是整数且 $0 \leq x_i,y_i,x_i+y_i <k$ ，每个点有一个权值 $c_i$ 。

现在有两个操作：

1. 删除一个点，花费其权值。
2. 选择一个整数坐标位置 $(a,b)$ ，画出等腰直角三角形 $x=a,y=b,x+y=k$ ，设其直角边长是 $l$ ，以及一个常数 $A$ ，那么删除这个等腰直角三角形内所有点，花费 $lA$ 。

问删掉所有点最少花费是多少。

题解

知识点：线性dp，线段树。

容易发现，我们选择删除的三角形区域最终是不相交的，否则可以合并。同时，三角形可以通过其左上角和右下角的纵坐标唯一确定，那么一个三角形就可以映射到纵坐标上的一个线段。现在，问题就变成在纵坐标上选择一些不相交的线段，使得线段对应的三角形位置删除、其他位置单点删除后，花费最小。这是一个类似最小多个子段和的问题，因此我们可以从上到下dp解决。

为了方便，我们先将 $y$ 坐标处理为 $k-y$ ，这样点的坐标就从 $0 \sim k-1$ 映射到 $k\sim 1$ 。

设 $f_{i}$ 表示删除纵坐标 $\leq i$ 的点的最小花费，那么有转移方程：

其中：

1. 第一项表示，从 $i$ 行往上都用一个三角形删除。

2. 第二项表示，第 $i$ 行全都单点删除。

3. 第三项表示，从 $i$ 行往上到 $j+1$ 行用一个三角形删除，从 $j$ 行往上不变。

   但这导致了，坐标满足 $0 \leq x \leq j-1, j+1 \leq y\leq i$ 的点没有考虑到，而这些点不可能被三角形覆盖，因此全都选择单点删除的花费。

考虑优化第三项。我们用线段树维护 $j \in[1,i-1]$ 的

最小值。其中，求和项可以每层区间加递推。因为区间 $[1,i-1]$ 可能是导致 $[1,0]$ 不合法区间，取默认值为 $0$ 即可，此时第三项结果为 $iA$ ，不会产生错误答案。

每次最后我们需要将 $f_[i]-iA$ 加到线段树位置 $i$ 上。

最后，答案即为 $f[k]$ 。

当然，为了避免不合法区间的出现，可以选择将第二项放到线段树的位置 $i$ 上，最后更新的时候取 $f[i]$ 和线段树位置 $i$ 的最小值更新即可。实际上，线段树也能维护整个第三项，默认值设为无穷大即可，但更新的时候会有点麻烦，要把新的值覆盖无穷大的值。

这两个实现虽然不会产生不合法的区间，但区间加实现常数会大一点，可以选择专门写一个函数操作。

另一个类似的思路：假设都用单点删除，去dp将一部分改为三角形删除的贡献改变量的最小值（是负的），最后用单点删除的总和加上这个最小值即可。

时间复杂度 $O((n+k) \log k)$

空间复杂度 $O(n+k)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; template<class T, class F>class SegmentTreeLazy {    int n;    vector<T> node;    vector<F> lazy;     void push_down(int rt) {        node[rt << 1] = lazy[rt](node[rt << 1]);        lazy[rt << 1] = lazy[rt](lazy[rt << 1]);        node[rt << 1 | 1] = lazy[rt](node[rt << 1 | 1]);        lazy[rt << 1 | 1] = lazy[rt](lazy[rt << 1 | 1]);        lazy[rt] = F();    }     void update(int rt, int l, int r, int x, int y, F f) {        if (r < x || y < l) return;        if (x <= l && r <= y) return node[rt] = f(node[rt]), lazy[rt] = f(lazy[rt]), void();        push_down(rt);        int mid = l + r >> 1;        update(rt << 1, l, mid, x, y, f);        update(rt << 1 | 1, mid + 1, r, x, y, f);        node[rt] = node[rt << 1] + node[rt << 1 | 1];    }     T query(int rt, int l, int r, int x, int y) {        if (r < x || y < l) return T();        if (x <= l && r <= y) return node[rt];        push_down(rt);        int mid = l + r >> 1;        return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);    } public:    SegmentTreeLazy(int _n = 0) { init(_n); }    SegmentTreeLazy(const vector<T> &src) { init(src); }     void init(int _n) {        n = _n;        node.assign(n << 2, T());        lazy.assign(n << 2, F());    }    void init(const vector<T> &src) {        init(src.size() - 1);        function<void(int, int, int)> build = [&](int rt, int l, int r) {            if (l == r) return node[rt] = src[l], void();            int mid = l + r >> 1;            build(rt << 1, l, mid);            build(rt << 1 | 1, mid + 1, r);            node[rt] = node[rt << 1] + node[rt << 1 | 1];        };        build(1, 1, n);    }     void update(int x, int y, F f) { update(1, 1, n, x, y, f); }     T query(int x, int y) { return query(1, 1, n, x, y); }}; struct T {    int mi = 0;    friend T operator+(const T &a, const T &b) { return { min(a.mi,b.mi) }; }}; struct F {    int add = 0;    T operator()(const T &x) { return { x.mi + add }; }    F operator()(const F &g) { return { g.add + add }; }}; vector<pair<int, int>> pos[200007];int f[200007]; int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, k, A;    cin >> n >> k >> A;    for (int i = 1;i <= n;i++) {        int x, y, c;        cin >> x >> y >> c;        pos[k - y].push_back({ x,c });    }     SegmentTreeLazy<T, F> sgt(k);    for (int i = 1;i <= k;i++) {        f[i] = f[i - 1];        for (auto [x, c] : pos[i]) sgt.update(x + 1, i - 1, { c }), f[i] += c;        f[i] = min({ f[i],i * A, sgt.query(1, i - 1).mi + i * A });        sgt.update(i, i, { f[i] - i * A });    }    cout << f[k] << '\n';    return 0;}