统一省选2021 A卷题解

目前只有 Day1 的题目。

感觉 Day1 的三道题很 CF。

卡牌游戏

Description

有 $n$ 张卡牌，第 $i$ 张卡牌的正面有数字 $a_i$，背面有数字 $b_i$，初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 $m$ 张卡牌翻面，即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 $n$ 个数字的极差（最大值与最小值的差）尽量小。请你帮 Alice 算一算极差的最小值是多少。

$n,m\leq10^6,a_i,b_i\leq10^9$。

Solution

首先我们要确定：常数小的 $O(n\log a_i)$ 是可以过的。

然后二分一个答案，考虑怎么 check，我们显然需要保留一段连续的区间不翻面（换句话说，一定只翻前后缀）。

考虑已经有左端点了，我们双指针确定右端点，这是 $O(n)$ 的，接下来不在这段区间内的卡牌显然全部需要翻面，那就变成了一个 RMQ 问题，用 ST 表解决就好了。

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

Code

注意细节，然后建议去 uoj 看看 hack 数据的威力。

被卡常可以考虑把 ST 表小的一维放前面。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cctype>
using namespace std;

int read()
{
    int x = 0;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        ;
    for (; isdigit(ch); ch = getchar())
        x = x * 10 + ch - '0';
    return x;
}

const int maxn = 2e6 + 10;
const int inf = 2e9;

int mx[22][maxn], mi[22][maxn];
int n, a[maxn], b[maxn], m;
int lg[maxn];

void build()
{
    memset(mi, 0x7f, sizeof(mi));
    for (int i = 1; i <= n; i++)
        mx[0][i] = mi[0][i] = b[i];
    lg[0] = -1;
    for (int i = 1; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int j = 1; j <= 21; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
            mi[j][i] = min(mi[j - 1][i], mi[j - 1][i + (1 << (j - 1))]);
        }
    }
    //for (int i = 0; i < 4; i++, cout << endl)
    //    for (int j = 1; j <= n; j++)
    //        cout << mi[j][i] << " ";
}

int query_mx(int l, int r)
{
    if (l > r)
        return -inf;
    int d = r - l + 1;
    int g = lg[d];
    return max(mx[g][l], mx[g][r - (1 << g) + 1]);
}

int query_mi(int l, int r)
{
    if (l > r)
        return inf;
    int d = r - l + 1;
    int g = lg[d];
    return min(mi[g][l], mi[g][r - (1 << g) + 1]);
}

bool check(int x)
{
    int l = 1, r = 1;
    while (l <= n)
    {
        while (r <= n && a[r] - a[l] <= x)
        {
            // cout << l << " " << r << " " << x << endl;
            if (l - 1 + n - r <= m)
                if (max({a[r], query_mx(1, l - 1), query_mx(r + 1, n)}) - min({a[l], query_mi(1, l - 1), query_mi(r + 1, n)}) <= x)
                    return true;
            r++;
        }
        if (r > l)
            r--;
        l++;
    }
    return false;
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i <= n; i++)
        b[i] = read();
    build();
    //cout << query_mi(1, n) << endl << query_mx(1, n) << endl;
    int l = 0, r = 1e9, ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ans << endl;
}

矩阵游戏

Description

有一个 $(n-1)\times(m-1)$ 的矩阵 $b_{i,j}$，其是由 $n\times m$ 的矩阵 $a_{i,j}$ 生成得来的，生成方法为 $b_{i,j}=a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}$。

现在给出矩阵 $b$，你需要构造出矩阵 $a$，且满足 $0\leq a_{i,j}\leq10^6$，或判断无解。

$T$ 组数据。

$T\leq10,2\leq n,m\leq300,0\leq b_{i,j}\leq4\times10^6$。

Solution

这个构造题就很妙，首先考虑没有值域限制，那可以随便搞出来一组解。

然后试图调整这组解，我们发现对每一行/列分别加上 $a,-a,a,-a…$ 仍然能满足题目的限制，然后控制一下行和列的符号，让他们恰好相反，得到以下不等式：$0\leq a_{i,j}\pm x_i\mp y_j\leq10^6$，这样就可以差分约束了！

具体点：

列：
-+-+-+
+-+-+-
-+-+-+
+-+-+-
-+-+-+
+-+-+-

行：
+-+-+-
-+-+-+
+-+-+-
-+-+-+
+-+-+-
-+-+-+

时间复杂度 $O(nm(n+m))$。

Code

typedef long long ll;
typedef unsigned long long ull;

inline int read()
{
    int x = 0;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        ;
    for (; isdigit(ch); ch = getchar())
        x = x * 10 + ch - '0';
    return x;
}

bool MEM1;

namespace solve
{
    const int maxn = 310;
    int n, m, b[maxn][maxn];
    ll a[maxn][maxn];
    struct edge
    {
        int y, w;
    };
    vector<edge> e[maxn * maxn * 2];
    inline void add(int x, int y, int w)
    {
        e[x].push_back({y, w});
    }
    void clear()
    {
        memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
        for (int i = 1; i <= n + m + 1; i++)
            e[i].clear();
    }
    inline int X(int i) { return i; }
    inline int Y(int i) { return i + n; }
    ll dis[maxn * maxn * 2];
    int vis[maxn * maxn * 2], cnt[maxn * maxn * 2];
    bool spfa()
    {
        memset(dis, 0x3f, sizeof(dis)), memset(vis, 0, sizeof(vis)), memset(cnt, 0, sizeof(cnt));
        queue<int> q;
        q.push(n + m + 1), vis[n + m + 1] = 1, dis[n + m + 1] = 0;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            vis[x] = 0;
            for (auto k : e[x])
            {
                int y = k.y, w = k.w;
                if (dis[x] + w < dis[y])
                {
                    dis[y] = dis[x] + w, cnt[y]++;
                    if (cnt[y] > n + m + 1)
                        return 1;
                    if (!vis[y])
                        vis[y] = 1, q.push(y);
                }
            }
        }
        return 0;
    }
    void main()
    {
        n = read(), m = read();
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++)
                b[i][j] = read();
        for (int i = n - 1; i >= 1; i--)
            for (int j = m - 1; j >= 1; j--)
                a[i][j] = b[i][j] - a[i + 1][j] - a[i + 1][j + 1] - a[i][j + 1];
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if ((i + j) % 2 == 0)
                    add(Y(j), X(i), 1e6 - a[i][j]), add(X(i), Y(j), a[i][j]);
                else
                    add(X(i), Y(j), 1e6 - a[i][j]), add(Y(j), X(i), a[i][j]);
            }
        }
        for (int i = 1; i <= n; i++)
            add(n + m + 1, X(i), 0);
        for (int i = 1; i <= m; i++)
            add(n + m + 1, Y(i), 0);
        if (spfa())
        {
            puts("NO");
        }
        else
        {
            puts("YES");
            for (int i = 1; i <= n; i++, puts(""))
                for (int j = 1; j <= m; j++)
                {
                    cout << a[i][j] + ((i + j) % 2 ? -1 : 1) * (dis[X(i)] - dis[Y(j)]) << " ";
                }
        }
    }
}

图函数

Description

对于一张 $n$ 个点 $m$ 条边的有向图 $G$ (顶点从 $1 \sim n$ 编号)，定义函数 $f(u, G)$ :

初始化返回值 $cnt = 0$，图 $G′ = G$。
从 $1$ 至 $n$ 按顺序枚举顶点 $v$，如果当前的图 $G′$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在，则将 $cnt + 1$，并在图 $G′$ 中删去顶点 $v$ 以及与它相关的边。
第 $2$ 步结束后，返回值 $cnt$ 即为函数值。

现在给定一张有向图 G,请你求出 $h(G) = f(1, G) + f(2, G) + \dots + f(n, G)$ 的值。

更进一步地，记删除（按输入顺序给出的）第 $1 \sim i$ 条边后的图为 $G_i (1 \leq i \leq m)$，请你求出所有 $h(G_i)$ 的值。

$2 \leq n \leq 1000, 1 \leq m \leq 2 \times 10^5, 1 \leq x_i, y_i \leq n$。

Solution

很神秘的一道题。

我们先看一下 $f(u,G)$，首先如果 $v>u$ 肯定是没意义的，因为 $u$ 会被自己删除掉。

发现点对 $(u,v)$ （$u>v$）会对这个函数有贡献当且仅当存在一条不经过点标号大于 $v$ 的路径 $u\rightarrow v$ 和 $v\rightarrow u$。

用反证法证明，假设路径上存在一个点 $k<v$，分两种情况：

$k$ 已经被删掉，那么显然不成立。
$k$ 没被删掉，那么如果还能走回来，就会矛盾（画画图就知道了）。

这样对于 $h(G)$，我们只需要求出 $(u,v)$（$u>v$）的对数，其中 $(u,v)$ 满足上面条件。

然后我们考虑删边这个事情，套路地，转化为加边。

那么一个点对显然会对答案的前缀产生贡献，开始产生贡献的时间就是 $u$ 到 $v$ （以及 $v$ 到 $u$ ）所有路径上加入时间最晚的边的最大值，这里显然可以把边的删除时间当作一种“边权”。

我试图用单源最短路解决这个问题，但是无果。

回头看看满足条件的点对，即只考虑 $[v,n]$ 内点，求 $u,v$ 联通性以及互相联通的时间。

emmm，floyd？好像从大到小枚举 $k$ 就能满足要求。

时间复杂度 $O(n^3+m)$，注意常数优化即可通过本题。

可能没讲清楚，看下面代码吧。

Code

#include <cstdio>
#include <iostream>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;

namespace solve
{
    const int maxn = 1e3 + 10;
    const int maxm = 2e5 + 10;
    const int inf = 1e6;

    int f[maxn][maxn], n, m;
    int ans[maxm];

    void main()
    {
        ios::sync_with_stdio(false);
        cin >> n >> m;
        for (int i = 1, x, y; i <= m; i++)
            cin >> x >> y, f[x][y] = i;
        for (int i = 1; i <= n; i++)
            f[i][i] = m + 1;
        for (int k = n; k >= 1; k--)
        {
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= (i < k ? n : k - 1); j++) // i j 至少一个小于 k
                    f[i][j] = max(f[i][j], min(f[i][k], f[k][j]));
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                ans[min(f[i][j], f[j][i])]++;
        for (int i = m; i >= 1; i--)
            ans[i] += ans[i + 1];
        for (int i = 1; i <= m + 1; i++)
            cout << ans[i] << " ";
        cout << endl;
    }
}

卡牌游戏¶

Description¶

Solution¶

Code¶

矩阵游戏¶

Description¶

Solution¶

Code¶

图函数¶

Description¶

Solution¶

Code¶

卡牌游戏

Description

Solution

Code

矩阵游戏

Description

Solution

Code

图函数

Description

Solution

Code