时间比较近的比赛果然难度大一些。。。

A

Description

有一个 $(n+1)\times(m+1)$​ 的点图，问最少断掉几条边能使​剩下的点全联通且没有环。（建议看原题面）

Solution

答案是 $n\times m$，一个构造性证明：蛇形就行。

B

Description

给出一个序列 $\{a_i\}$ ，求最大的 $m$ 和任意的 $c$，满足 $a_i=(a_{i-1}+c)\bmod m$​。（需要判断无解和 $m\rightarrow\infty$）​

Solution

可以发现相邻的两个数差一定是 $c-m$ 或 $c$​，那么扫一遍就能知道 $c$ 和 $m$，然后再扫一遍看看合不合法就行。

C

Description

有 $n$ 个人， $m$ 天，你每天需要从给定的一些人中选一个，且每个人最多只能选 $\lceil \dfrac m2\rceil$ 次，判断有没有解并给出一个方案。

Solution

从前往后一天一天选。当一天只能选一个人，这个人必须就选了，先预处理这些天。剩下的天我们直接选当前已经选过的次数最少的人。

证明感性一下，想要卡掉这个做法需要每天两个人一直出现，但是这样也只能让选一个人的次数达到 $\dfrac m2$，所以卡不掉。

Code

没必要看，实在是丑。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using std::cout;
using std::endl;
using std::cin;

const int maxn = 2e5 + 10;

std::vector<int> a[maxn];
int used[maxn / 2], times[maxn / 2], ans[maxn];

int main()
{
    int T;
    cin >> T;
    times[0] = used[0] = 1 << 30;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
            a[i].clear(), ans[i] = 0;
        for (int i = 1; i <= n; i++)
            used[i] = times[i] = 0;        
        int flag = 1;
        for (int x, i = 1; i <= m; i++)
        {
            int t;
            cin >> t;
            while (t--)
                cin >> x, a[i].push_back(x), times[x]++;
            if (a[i].size() == 1)
                used[a[i][0]]++, times[a[i][0]]--, ans[i] = a[i][0], flag &= used[a[i][0]] > (m + 1) / 2 ? 0 : 1;
        }
        for (int i = 1; i <= m; i++)
        {
            if (a[i].size() == 1)
                continue;
            int mx = 0;
            for (int p : a[i])
                if (used[p] < used[mx])
                    mx = p;
            used[mx]++, ans[i] = mx;
            if (used[mx] > (m + 1) / 2)
            {
                flag = 0;
                break;
            }
        }
        if (!flag)
        {
            puts("NO");
            continue;
        }
        puts("YES");
        for (int i = 1; i <= m; i++)
            cout << ans[i] << " ";
        cout << endl;
    }
}

D

Description

给出 $n$​ 首歌，和他们的类型值，从头循环播放，如果当前的歌和前一首歌的类型值互质，把当前这首歌删掉，切到下一首歌去，求删除的歌的序列。

Solution

用一个链表模拟即可，第一次扫一遍把要删除的组加进一个队列里，然后取出队首，执行删除，再判断一下需不需要接着删就行。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

inline int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

const int maxn = 1e5 + 10;
typedef std::pair<int, int> pii;

int nxt[maxn], a[maxn], used[maxn];
std::vector<int> ans;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i], nxt[i] = i + 1;
        nxt[n] = 1;
        std::queue<pii> q;
        for (int i = 1; i <= n; i++)
            if (gcd(a[i], a[nxt[i]]) == 1)
                q.push(pii(i, nxt[i])), i++;
        while (!q.empty())
        {
            auto now = q.front();
            q.pop();
            int pos = now.first, npos = now.second;
            if (used[pos] || used[npos])
                continue;
            used[npos] = 1;
            ans.push_back(npos);
            nxt[pos] = nxt[npos];
            if (gcd(a[pos], a[nxt[pos]]) == 1)
                q.push(pii(pos, nxt[pos]));
        }
        cout << ans.size() << " ";
        for (int i : ans)
            cout << i << " ";
        cout << endl;
        ans.clear(), memset(used, 0, sizeof(used));
    }
}

E

Description

给出 $n$​​ 个楼房的高度和美丽值，把所有楼房划分成连续的若干组，最大化 每组高度最小的楼房的美丽值 的和。$n\leq3\times10^5$​。

Solution

显然有个 DP，$f_i=\max\{f_j+val(j+1,n)\}$​，其中 $val(l,r)$​ 表示 $[l,r]$​​ 内最矮楼房的美丽值。然后发现一个楼房到下一个比它更矮的楼房这段区间内， $val$ 都是固定的，可以维护一个单调栈。

算法一

对于每个楼房，进栈时把他能影响到的 $f$ 的值全部加它的美丽值，出栈的时候减掉。使用线段树维护， $f_i$ 就是当前所有已经加进线段树的点的最大值。然后把 $f_i$ 加进去。细节有点多。。。。。

Code1

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using std::cout;
using std::endl;
using std::cin;

const int maxn = 3e5 + 10;
typedef long long ll;
const ll inf = 1ll << 60;

struct node
{
    ll lzy, mx;
    node() {}
} t[maxn * 4];
inline int ls(int x) { return x * 2; }
inline int rs(int x) { return x * 2 + 1; }
inline void push_up(int k) { t[k].mx = std::max(t[ls(k)].mx, t[rs(k)].mx); }
inline void push_down(int k)
{
    if (!t[k].lzy)
        return;
    t[ls(k)].lzy += t[k].lzy, t[rs(k)].lzy += t[k].lzy;
    t[ls(k)].mx += t[k].lzy, t[rs(k)].mx += t[k].lzy;
    t[k].lzy = 0;
}

void modify_add(int l, int r, int x, int y, ll v, int k)
{
    if (l >= x && r <= y)
    {
        t[k].lzy += v;
        t[k].mx += v;
        return;
    }
    int mid = (l + r) / 2;
    push_down(k);
    if (x <= mid)
        modify_add(l, mid, x, y, v, ls(k));
    if (y > mid)
        modify_add(mid + 1, r, x, y, v, rs(k));
    push_up(k);
}

void modify(int l, int r, int x, ll v, int k)
{
    if (l == r)
    {
        //t[k].lzy = 0;
        t[k].mx = v;
        //cout << l << " " << v << endl;
        return;
    }
    int mid = (l + r) / 2;
    //push_down(k);
    if (x <= mid)
        modify(l, mid, x, v, ls(k));
    else
        modify(mid + 1, r, x, v, rs(k));
    push_up(k);
}

ll query(int l, int r, int x, int y, int k)
{
    if (x <= l && r <= y)
    {
        return t[k].mx;
    }
    int mid = (l + r) / 2;
    ll res = -inf;
    if (x <= mid)
        res = std::max(res, query(l, mid, x, y, ls(k)));
    if (y > mid)
        res = std::max(res, query(mid + 1, r, x, y, rs(k)));
    return res;
}

struct Q
{
    int i, val, b;
    Q() { i = b = 0, val = -1; }
    Q(int i_, int val_, int b_) : i(i_), val(val_), b(b_) {}
} q[maxn];

int n, h[maxn], b[maxn];
ll f[maxn];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    int r = 1;
    h[0] = -1;
    for (int i = 1; i <= n; i++)
    {
        while (r && q[r].val >= h[i])
        {            
            modify_add(0, n, q[r - 1].i, q[r].i - 1, -q[r].b, 1);
            r--;
        }
        q[++r] = Q(i, h[i], b[i]);
        modify_add(0, n, q[r - 1].i, i - 1, b[i], 1);
        f[i] = query(0, n, 0, i - 1, 1);
        modify(0, n, i, f[i], 1);
    }
    //for (int i = 1; i <= n; i++)
    //    cout << f[i] << endl;
    cout << f[n] << endl;
}

算法二

同样是单调栈，直接上代码吧。。。维护之前的答案折腾一下，很难描述。看题解得来的做法。

Code2

#include <iostream>
#include <cstdio>
#include <algorithm>
using std::cout;
using std::cin;
using std::endl;

const int maxn = 3e5 + 10;
typedef long long ll;

int h[maxn], b[maxn], n;
ll f[maxn];

struct Q
{
    int i, h;
    ll val, ans;
} q[maxn];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    int r = 0;
    q[0].ans = -1ll << 60;
    for (int i = 1; i <= n; i++)
    {
        ll t = f[i - 1];
        while (r && q[r].h > h[i])
        {
            t = std::max(t, q[r].val);
            r--;
        }
        q[++r] = {i, h[i], t, 0ll};
        f[i] = q[r].ans = std::max(q[r - 1].ans, t + b[i]);
        // 前一部分是之前的答案，有更小的楼房，直接放在一组里，后面是新开一组的答案
    }
    cout << f[n] << endl;
}

F

Description

有一个 $n$​ 个点的带权无向图（$n\leq600$​），给出若干个三元组 $(u,v,l)$​​，问有多少条边满足：

  1. 在任意一个三元组中 $u$​ 到 $v$​ 的路径上；

  2. 这个路径的长度不大于 $l$。

Solution

发现一条边 $(x,y)$​​ 满足要求当且仅当存在一个三元组 $(u,v,l)$​​ 满足 $dis(u,x)+w(x,y)+dis(y,w)\leq l(u,v)$​​​。

首先枚举 $O(n^4)$ 肯定是对的，但是会 TLE，想个办法优化枚举。。。

换个形式：$dis(u,x)+w(x,y)\leq l(u,v)-dis(y,v)$​。

我们枚举 $u,y$，这样左面只和 $x$ 有关，右面只和 $v$ 有关，考虑接着枚举 $x$，我们发现，因为存在 $v$ 即可，所以一个 $x$ 满足要求等价于 $dis(u,x)+w(x,y)\leq(l(u,v)-dis(y,v))_{max}$。右面可以枚举 $u,v,y$ 在 $O(n^3)$ 时间内预处理出来，答案可以枚举 $u,v,x$ 求出来，那么我们在 $O(n^3)$​ 的时间内解决了这个问题。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 610;
typedef long long ll;

ll dis[maxn][maxn], mx[maxn][maxn];
ll p[maxn][maxn];
int ok[maxn][maxn];
struct edge
{
    int y, w;
};
std::vector<edge> e[maxn];
inline void add(int x, int y, int w) { e[x].push_back({y, w}), e[y].push_back({x, w}); }
int n, m, q;

int main()
{
    memset(dis, 1, sizeof(dis));
    memset(p, 128, sizeof(p)), memset(mx, 128, sizeof(mx));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            p[i][j] /= 2, mx[i][j] /= 2, dis[i][j] /= 2;
    for (int i = 1, x, y, w; i <= m; i++)
        cin >> x >> y >> w, dis[x][y] = dis[y][x] = w, add(x, y, w);
    cin >> q;
    for (int i = 1, x, y, l; i <= q; i++)
        cin >> x >> y >> l, p[x][y] = p[y][x] = l;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
    for (int i = 1; i <= n; i++)    
        dis[i][i] = 0, add(i, i, 0);
    for (int u = 1; u <= n; u++)
        for (int y = 1; y <= n; y++)
            for (int v = 1; v <= n; v++)
                //if (p[u][v])
                    mx[u][y] = std::max(mx[u][y], (ll)p[u][v] - dis[y][v]);

    for (int u = 1; u <= n; u++)
        for (int y = 1; y <= n; y++)
            for (auto k : e[y])
            {
                int x = k.y, w = k.w;
                if (w + dis[x][u] <= mx[u][y])
                    ok[x][y] = ok[y][x] = 1;
            }
    int ans = 0;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (ok[i][j])
                ans++;
    cout << ans << endl;
}