概述

不简单，但也不算特别难。

Div1 的 BCDE 都值得一做。

因为写得比较着急，可能有各种疏漏，见谅。

Div2 A

Description

对于一个长度为 $n$ 的排列 $p$，定义其 fingerprint $F(p)$ 为 $p$ 中相邻元素和排序后得到的数组。更形式化地，

$$F(p)=\text{sort}([p_1+p_2,p_2+p_3,\cdots,p_{n-1}+p_n])$$​。

给定一个长度为 $n$ 的排列 $p$，你需要找到一个与 $p$​ 不同但 fingerprint 相同的排列。

Solution

没啥可说的，看一看这个定义，因为是排列，直接倒序输出即可。

Code

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

int T;

int main()
{
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        std::vector<int> a;
        for (int i = 1, x; i <= n; i++)
            cin >> x, a.push_back(x);
        std::reverse(a.begin(), a.end());
        for (int u : a)
            cout << u << " ";
        cout << endl;
    }
}

Div2 B

Description

给定一个序列 $a[1]-a[n]$​，满足 $\sum_{i=1}^{n}a[i]=0$​。

每次可以选两个数 $i$​，$j$​，使 $a[i]$ ​变为 $a[i]-1$​， $a[j]$ ​变为 $a[j]+1$​。

当 $i<j$ ​​使操作无花费，否则操作花费 $1$​​。

求使所有数都变为 $0$ ​所需的最小花费。

Solution

显然我们需要尽可能进行无花费的操作。

尽可能让前面的数减小，后面的数增加，但是要是已经是负的了，那么就需要花费代价。

想一想再玩一玩样例，发现答案是最小前缀和的相反数（感性理解）。

Code

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

const int maxn = 1e5 + 10;

int n;
int a[maxn];
long long sum[maxn];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        long long ans = 1ll << 60;
        for (int i = 1; i <= n; i++)
            cin >> a[i], sum[i] = sum[i - 1] + a[i], ans = std::min(ans, sum[i]);
        cout << std::abs(ans) << endl;
    }
}

A

Description

给定一个二进制字符串 由 0,1,? 组成。

? 可以是 1 或者 0，由你自由选择。

问你是否能构造出一个字符串，使得这个字符串每个长度为 $k$ 的子串中 0 和 1 的个数相等。

Solution

不会做就找规律（）

看样例发现这个东西很循环，往这个方面想一想就能想到：第 $s_i=s_{i+k}$。很显然不证明了。

那么整个字符串就被分成了 $k$ 组，把已经确定的组都确定好，如果组内有矛盾显然无解。接着只检查 $s_1\sim s_k$​ 合不合法即可。

Code

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

const int maxn = 3e5 + 10;

int a[maxn], n, k;
char s[maxn];

bool solve()
{
    cin >> n >> k >> (s + 1);
    for (int i = 1; i <= n; i++)
        a[i] = s[i] == '?' ? -1 : s[i] - '0';
    for (int i = 1; i <= k; i++)
    {
        int p = a[i];
        for (int j = i + k; j <= n; j += k)
            if (a[j] != -1)
                p = a[j];
        for (int j = i; j <= n; j += k)
            if (a[j] != -1 && a[j] != p)
                return false;
        a[i] = p;
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= k; i++)
        if (a[i] == 1)
            cnt1++;
        else if (a[i] == -1)
            cnt2++;
    if (cnt1 <= k / 2 && cnt1 + cnt2 >= k / 2)
        return true;
    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        puts(solve() ? "YES" : "NO");
    }
}

B

Description

有一棵 $n$ 个点的树， Alice 和 Bob 初始在这棵树上的节点 $a$, $b$。

他们可以在树上轮流移动一段距离不超过 $da$ 和 $db$ 的路径。

路径长度的定义是两点之间树上简单路径的边数。

如果 Alice 能在 $10^{100}$​ 次内追到 Bob ，那么则算 Alice 赢，否则算 Bob 赢。

Alice 先走。

Solution

看起来是个结论题，实际上也确实是。

想一想加画一画能想到 Alice 获胜有以下三种情况。否则输。

  • $dis(a,b)\leq da$，一步就抓到了；
  • $2da\geq db$，可以一步一步逼近 Bob 胜利；
  • Alice 走到一个能控制树上所有点的点，这样 Bob 不管怎么走都会输。这个时候需要满足 $2da\geq d$，$d$ 是树的直径。

第一种情况很显然，第二种情况也挺显然：不管 Bob 怎么走，Alice 一定能拉近距离。

第三种情况是很极限的情况，Bob 最远也只能走直径长度的路径，如果 Alice 能占据直径中点那自然必胜（建议画图理解）。

Code

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

const int maxn = 1e5 + 10;

int n, a, da, b, db;

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

void clear()
{
    for (int i = 1; i <= n; i++)
        e[i].clear();
}

int dep[maxn];

void dfs(int x, int fa)
{
    dep[x] = dep[fa] + 1;
    for (int v : e[x])
        if (v != fa)
            dfs(v, x);
}

bool solve()
{
    dep[0] = -1, dfs(b, 0);
    int rt = 0;
    int dis = dep[a];
    if (dis <= da || 2 * da >= db)
        return true;
    for (int i = 1; i <= n; i++)
        if (dep[i] > dep[rt])
            rt = i;
    dfs(rt, 0);
    for (int i = 1; i <= n; i++)
        if (dep[i] > dep[rt])
            rt = i;
    int d = dep[rt];
    //cout << d << endl;
    if (da + da >= d)
        return true;
    return false;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> a >> b >> da >> db;
        for (int i = 1, x, y; i < n; i++)
            cin >> x >> y, add(x, y);
        puts(solve() ? "Alice" : "Bob");
        clear();
    }
}

C

Description

给定一个含有 $n$​ 个正整数的序列 $a$​ ，对于一次操作，你可以任选一个位置 $i$​ 且满足 $a_i=i$​ ,那么就可以移除这个元素，并将后面所有的元素向前移动一位。

对于每个相互独立的询问 $x,y$ 需要你求出在前 $x$ 个元素以及后 $y$ 个元素不能被移除的情况下，最多可以进行几次操作。

$n,q \leq 3\times 10^5$。

Solution

能想到能删除几个点和删除的顺序是没什么关系的，只要一个数前面能被删除的数足够多那么他就可以被删除（因为先删后面的不影响前面的）。

考虑到这一点，我们直接让 $a_i=i-a_i$，每次删除一个数相当于区间减 $1$ 。显然负数永远都消不掉。

这种奇怪的东西我们尝试把它离线下来。

然后就不会了，我数据结构太差了qwq，直接看题解。。。

要求解答案，我们需要尝试维护 $f_i$ 表示从 $i$ 开始能删掉几个数。

我们把询问按照右端点排序，考虑加进去一个数之后对上面这个东西的贡献。

显然 $f_i$ 是单调不增的，也就是说，对于前一部分，会使 $f_i$ 增加 $1$，后面不变。

或者换个说法：$f_k\geq q_r>f_{k+1}$。

区间加 $1$，单点查询，选择树状数组。

实际上只需要记录操作次数即可。

至于怎么找这个 $k$​，树状数组上二分即可。

有时间会写个线段树版，树状数组上二分还是很难受的。

Code

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

const int maxn = 3e5 + 10;

inline int lowbit(int x) { return x & -x; }

int n, a[maxn], t[maxn];

void modify(int x, int v)
{
    for (; x <= n; x += lowbit(x))
        t[x] += v;
}

int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x))
        res += t[x];
    return res;
}

int kth(int k)
{
    int res = 0;
    for (int i = 1 << 18; i; i >>= 1)
    {
        if (res + i <= n && k - t[res + i] > 0)
            res += i, k -= t[res];
    }
    return res + 1;
}

struct Q
{
    int l, r, ans, id;
    bool operator<(const Q &b) const { return r < b.r; }
} q[maxn];
bool cmp(const Q &a, const Q &b) { return a.id < b.id; }

int main()
{
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), a[i] = i - a[i];
    for (int i = 1, l, r; i <= m; i++)
        scanf("%d%d", &l, &r), q[i].id = i, q[i].l = 1 + l, q[i].r = n - r;
    std::sort(q + 1, q + 1 + m);
    int now = 1;
    for (int i = 1; i <= m; i++)
    {
        while (now <= q[i].r)
        {
            int pos = a[now] < 0 ? 1 : std::min(kth(now - a[now]), now + 1);
            modify(pos, 1), now++;
        }
        q[i].ans = q[i].r - query(q[i].l);
    }
    std::sort(q + 1, q + 1 + m, cmp);
    for (int i = 1; i <= m; i++)
        printf("%d\n", q[i].ans);
}

D

Description

这是一道交互题

给定 $2n$ 个数 $1,2\sim 2n$，A 和 B 进行交互，如下规则：

  • A 需要将元素分成 $n$ 组 $\mathbf{pair}$（二元组）
  • B 从每组 $\mathbf{pair}$ 中选择一个元素，如果权值和是 $2n$ 的倍数那么 B 胜，否则 A 胜。

你需要选择 A/B 中的一者扮演角色，并取得胜利。

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

Solution

观察样例 + 手算，发现当 $n$ 是偶数的时候，A 可以胜利：排一个 $(1,1+n),(2,2+n)…$ 即可。

简易证明：取出来 $n$ 个数的和在模 $n$ 意义下是 $n(n-1)/2$，设 $n=2m$，则和为 $m(2m-1)$，这玩意是必然没法被 $2m$ 整除的，也就是说在和在模 $n$ 意义下都没法是 $0$，那 $2n$ 就更不行了。

然后盲猜：当 $n$ 是奇数，B 胜利。

有了刚刚的偶数，我们可以考虑试图取在模 $n$ 意义下是 $0,1,2,…,n-1$​ 的数，这些数加在一起一定是 $2n$ 的倍数。

稍微证明一下为什么一定能取到：因为模 $n$ 相同的一个数有两个，取了一个就必然不会取另一个，我们把 $i,i+n$ 连起来，表示只选其中一个。

同一组的两个数也不能同时选，我们也连起来。

这样每个点的度数就是 $2$，也就是说连出了一堆环，且 $i,i+n$​​ 在一个环里且相邻。这样就能得出一定能取到了（好像不太严谨，感性理解吧）。

选一个就不能选另一个，这是啥？无疑是二分图染色。

我们对每个环二分图染色就能得到结果了。

Code

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

void end()
{
    int x;
    cin >> x;
}

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

int used[maxn], must[maxn], vis[maxn];
std::vector<int> e[maxn], ans[2];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }
int lst[maxn];

void dfs(int x, int d)
{
    ans[d].push_back(x);
    vis[x] = 1;
    for (int v : e[x])
        if (!vis[v])
            dfs(v, d ^ 1);
}

int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    if (n % 2 == 0)
    {
        cout << "First" << endl;
        for (int i = 1; i <= n; i++)
            cout << i << " ";
        for (int i = 1; i <= n; i++)
            cout << i << " ";
        cout << endl;
        end();
        return 0;
    }
    else
    {
        cout << "Second" << endl;
        for (int i = 1; i <= n * 2; i++)
        {
            int x;
            cin >> x;
            if (lst[x])
                add(lst[x], i);
            else
                lst[x] = i;
        }
        for (int i = 1; i <= n; i++)
            add(i, i + n);
        for (int i = 1; i <= 2 * n; i++)
            if (!vis[i])
                dfs(i, 0);
        long long sum = 0;
        for (int k : ans[0])
            sum += k;
        if (sum % (2 * n))
            std::swap(ans[0], ans[1]);
        for (int k : ans[0])
            cout << k << " ";
        cout << endl;
        end();
        return 0;
    }
}

E

Description

你有一个 $n\times m\space(1 \leq n, m\leq200)$​ 的格子纸，格子要么涂黑（#）要么涂白（.）。你需要用若干个 $1\times n$ ​和 $n\times 1$ ​的长方形去覆盖所有黑色格子，要求不能盖到白色格子上，不能盖到其他长方形上，不能出格子纸的边界，求最小用多少个长方形。

Solution

遇事不决看样例。发现对于一个点，横着的边和竖着的边不能同时选。

选一个边就相当于少了一个矩形，那么我们就要尽可能多选边。

一个常规套路：把边看成点，那么有两种点，且选了一个就不能选另一个，这是啥？不还是二分图吗！

我们把与一个点相邻的相互垂直的边两两连起来。

因为要多选点，也就是说要求二分图最大点独立集，那么只要求最大匹配即可，最大点独立集的大小就是点数减去最大匹配。

就这么简单？确实就这么简单，但还有点小细节：假如一个黑色格子周围没有边，它应该被算进答案，但我们刚刚没算。

那就加上即可，或者直接懒一点：最终答案 = 黑格子数 - 边数 + 最大匹配。

Code

我这个代码感觉加边部分还是很清晰的。

我是用点编号来代替边的编号，很简单。

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

const int maxn = 100010;

char str[210][210];

struct edge
{
    int x, y, cap, flow;
};

struct Dinic
{
    std::vector<edge> edges;
    std::vector<int> e[maxn];
    inline void add(int x, int y, int cap)
    {
        //cout << "added: " << x << " " << y << endl;
        edges.push_back({x, y, cap, 0});
        edges.push_back({y, x, 0, 0});
        int m = edges.size();
        e[x].push_back(m - 2), e[y].push_back(m - 1);
    }
    int dis[maxn], vis[maxn], cur[maxn], s, t;
    bool bfs()
    {
        std::queue<int> q;
        memset(vis, 0, sizeof(vis));
        q.push(s), vis[s] = 1, dis[s] = 0;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i : e[x])
            {
                auto &k = edges[i];
                if (!vis[k.y] && k.cap - k.flow > 0)
                    dis[k.y] = dis[x] + 1, vis[k.y] = 1, q.push(k.y);
            }
        }
        return vis[t];
    }
    int dfs(int x, int lim)
    {
        if (x == t || lim == 0)
            return lim;
        int res = 0, f;
        for (int &i = cur[x]; i < (int)e[x].size(); i++)
        {
            auto &k = edges[e[x][i]];
            if (dis[k.y] != dis[x] + 1 || (f = dfs(k.y, std::min(lim, k.cap - k.flow))) == 0)
                continue;
            k.flow += f, edges[e[x][i] ^ 1].flow -= f, res += f, lim -= f;
            if (lim == 0)
                break;
        }
        return res;
    }
    int dinic(int s_, int t_)
    {
        s = s_, t = t_;
        int ans = 0;
        while (bfs())
            memset(cur, 0, sizeof(cur)), ans += dfs(s, 1 << 30);
        return ans;
    }
} G;

int n, m;

inline int id(int x, int y) { return (y - 1) * n + x + n * m + 2; }
inline int id2(int x, int y) { return m * (x - 1) + y + 1; }

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", str[i] + 1);
    int s = 1, t = n * m * 2 + 3, tot = 0, cnt_p = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (str[i][j] == '#')
            {
                cnt_p++;
                if (str[i + 1][j] == '#')
                    tot++, G.add(1, id2(i, j), 1);
            }
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
        {
            if (str[i][j] == '#' && str[i][j + 1] == '#')
            {
                //cout << "cur: " << i << " " << j << endl;
                G.add(id(i, j), t, 1), tot++;
                if (i > 1 && str[i - 1][j] == '#')
                    G.add(id2(i - 1, j), id(i, j), 1);
                if (i < n && str[i + 1][j] == '#')
                    G.add(id2(i, j), id(i, j), 1);
                if (i > 1 && str[i - 1][j + 1] == '#')
                    G.add(id2(i - 1, j + 1), id(i, j), 1);
                if (i < n && str[i + 1][j + 1] == '#')
                    G.add(id2(i, j + 1), id(i, j), 1);
            }
        }
    cout << cnt_p - (tot - G.dinic(s, t)) << endl;
}