比赛链接

A代码

#include 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 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]\) 最多能删除的元素个数，有转移方程：

\[f_i = \max\limits_{j:a_j = a_i} \{ f_{j-1} + i-j+1 \}\]

我们要优化这个转移，实际上我们只需要维护 \(\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 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\) 号朋友必须被选中。\(n\) 号朋友不能被选中。所有人玩的时间需要遵守 \(m\) 条约束。

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

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

题解

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

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

集合 \(A\) 表示能和 \(1\) 一起玩的。集合 \(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 using namespace std;using ll = long long;vector> 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 pq;vector 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

现在有两个操作：

删除一个点，花费其权值。选择一个整数坐标位置 \((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\) 的点的最小花费，那么有转移方程：

\[f_i = \min\left\{ iA,f_{i-1} + \sum_{j:y_j = i}c_j ,\min\limits_{1 \leq j \leq i-1} \left\{ f_{j} + \sum_{k:\substack{0 \leq x_k \leq j-1\\ j+1 \leq y_k\leq i}}c_k + (i-j)A \right\}\right\}\]

其中：

第一项表示，从 \(i\) 行往上都用一个三角形删除。

第二项表示，第 \(i\) 行全都单点删除。

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

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

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

\[f_{j} + \sum_{k:\substack{0 \leq x_k \leq j-1\\ j+1 \leq y_k\leq i}}c_k - jA\]

最小值。其中，求和项可以每层区间加递推。因为区间 \([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 using namespace std;using ll = long long;templateclass SegmentTreeLazy {    int n;    vector node;    vector 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 &src) { init(src); }    void init(int _n) {        n = _n;        node.assign(n << 2, T());        lazy.assign(n << 2, F());    }    void init(const vector &src) {        init(src.size() - 1);        function 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> 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 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;}

标签：