2024 ACM-ICPC 校内选拔赛 / YAC Round 7 题解

A 成长的道路

题意描述

一共有 $n$ 天，第 $i$ 天做 $1 + 2 + \ldots + i$ 个题，求 $n$ 天一共做了多少题。「YAC Round 7」成长的道路

解题思路

签到题。$n$ 的范围不大，可以 $n$ 次用等差数列求和公式求得每一天的做题数量，累加得到这 $n$ 天的数量之和。

当然，可以通过数学推导得出所求 $n$ 项和就是 $\frac{n(n + 1)(n + 2)}{6}$。

(注意数据范围，需要开 $\text{long long}$)

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;

int main(){
    ios;

    ll n; cin >> n;
    cout << n * (n + 1) * (n + 2) / 6 << '\n';

    return 0;
}

B 竹林冰火人

题意描述

一共有 $n$ 种竹子，种类编号为 $1 \sim n$。两个人分别找到 $x$ 种和 $y$ 种竹子，问这两个人是否可以凑齐全部的 $n$ 种竹子。「YAC Round 7」竹林冰火人

解题思路

签到题。用哈希集合或者定义一个记录数组标记种类是否访问过，最后判断一下是否 $n$ 种竹子都被找到即可。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int main(){
    ios;

    int n, x, y, c; cin >> n;
    vector<bool> vis(n + 1, false);

    cin >> x;
    while(x -- ) cin >> c, vis[c] = true;
    cin >> y;
    while(y -- ) cin >> c, vis[c] = true;

    bool flag = true;
    for(int i = 1; i <= n; i ++ )
        if(!vis[i]){
            flag = false;
            break;
        }

    cout << (flag ? "It Takes Two." : "Maybe Next Time.") << "\n";

    return 0;
}

C 晚安，爱丽丝

题意描述

给定一个长度为 $n$ 的 $01$ 字符串和一个次数限制 $k$，每次操作可以选择一个下标 $i$ 将 $[i, i + L - 1]$ 范围内字符串中的 $1$ 全部变成 $0$，求能够在 $k$ 次操作内使得字符串中的 $1$ 全部变成 $0$ 的最小的 $L$。「YAC Round 7」晚安，爱丽丝

解题思路 二分

很显然，我们选择的长度 $L$ 越长，使得字符串全部变成 $0$ 的操作次数也会越少。假设我们最终得到的最小的长度是 $L_{ans}$，选择的长度 $\ge L_{ans}$，操作次数小于等于次数限制 $k$；选择的长度 $< L_{ans}$，操作次数大于次数限制 $k$。显然，此题具有二段性，故我们可以二分答案。

在 $\text{check}$ 中，假设此时选择的长度为 $L$。在遍历字符串的时候，若当前下标为 $i$。如果遇到的是 $0$，那么我们可以直接不管；如果遇到的是 $1$，由于要将所有的 $1$ 都变成 $0$，因此当前的下标 $i$ 必须选择，并且区间 $[i, i + L - 1]$ 范围内的都变成 $0$（无论原先是 $1$ 还是 $0$）。因此，只需要遍历字符串过程中，遇到 $0$ 就 $i ++ $ 跳过，而遇到 $1$ 就次数 $\text{+}1$，同时 $i \text{+=} L$，直到最后遍历完整个字符串。最后得到的次数如果 $\le k$，那么返回 $\text{true}$；否则，返回 $\text{false}$。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int n, k;
string s;

bool check(int d){
    int cnt = 0;
    for(int i = 1; i <= n; ){
        if(s[i] == '0') i ++ ;
        else i += d, cnt ++ ;
    }
    return cnt <= k;
}

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        cin >> n >> k >> s;
        s = " " + s;
        int l = 1, r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << r << "\n";
    }

    return 0;
}

D ✌巫女要买茶叶了

题意描述

给定一个长度为 $n$ 的数组，现在需要清空数组，有两种操作：

• 选择一个元素 $x$ ，直接删除，花费代价为 $1$；

• 若之前删除的一个元素为 $x$，那么可以选择一个元素 $x + 1$ 进行删除，花费代价为 $0$。（前提是 $x + 1$ 存在于数组中）

求清空数组的最少操作次数。

「YAC Round 7」✌巫女要买茶叶了

解题思路 贪心 + 排序

显然我们可以任意选择一个较小的元素 $x$，然后将可以选到的连续的 $x + 1, x + 2, \ldots, x + k$ 都一次性删除，删除这一连续序列花费的代价为 $1$。因此，我们的问题就转化为求出数组中最少有多少个连续序列，形如 $x, x + 1, x + 2, \ldots , x + k$。

我们可以记录当前元素 $x$ 出现的次数（由于元素范围是 $[1, 10^9]$，所以建议直接用 $map$ 哈希映射），将数组以当前元素出现次数为第一关键字、以元素值为第二关键字排序（可以用 $pair$ 存）。排序后得到的序列就变成若干个连续的序列拼接在一起。

最后，只需要统计一下排序后的序列中，有多少个断点即可（也就是相邻两个不是连续的位置的个数），答案就是断点数量 $+ 1$ 。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e5 + 10;
typedef long long ll;
typedef pair<int, int> pii;
#define se second
#define fi first

pii a[N];
unordered_map<int, int> mp;

int main(){
    ios;

    int n; cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i].se;
        mp[a[i].se] ++ ;   // 统计元素出现次数
        a[i].fi = mp[a[i].se];
    }
    sort(a + 1, a + n + 1);  // 按照出现次数为第一关键字排序
    
    int res = 1;
    for(int i = 2; i <= n; i ++ ) res += (a[i].se - a[i - 1].se != 1); 
    cout << res << '\n';

    return 0;
}

E 魔理沙骑着扫帚飞

题意描述

给定一个 $n \times m$ 的网格图，每个位置 $(i, j)$ 上有一个方向 $s_{i, j}$ 和一个元素 $a_{i, j}$。$s_{i, j} = \{'u', 'd', 'l', 'r'\}$，分别表示上下左右。处于位置 $(i,j)$ 上时可以向当前位置指定方向移动 $a_{i,j}$ 的距离（前提是位置存在）。判断是否可以找一个初始位置，一直走直到所有位置都走过一次。「YAC Round 7」魔理沙骑着扫帚飞

解题思路 并查集

首先我们要注意到，每个位置 $(i, j)$ 只有一个出边，我们考虑将所有边都建立起来构成一个图。从一个初始点一次性走完所有点只有两种情况：

• 整个图构成一个环，此时从任意点出发都一个走到所有点。

• 从一个点出发，走到一个小环上，从而走到所有点。

因此，我们首先需要满足的一点就是所有点都必须在一个连通块中，否则不可能选择一个点到达所有点。对于判断所有点是否都在一个连通块中，我们可以采用并查集进行判断。

其次，我们只能选择一个初始点，根据上面的两种可能的情况，显然入度为 $0$ 的点不能超过 $1$ 个。如果存在多个入度为 $0$ 的点，选择其中一个作为初始点，其他的入度为 $0$ 的点显然都无法到达。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e6 + 2;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

unordered_map<char, int> mp = {{'u', 0}, {'d', 1}, {'l', 2}, {'r', 3}};
string g[N];              // 只给了 n x m 大小范围，故需要采用字符串
int n, m, fa[N], ind[N];  // 并查集 和 入度

int getID(int x, int y){ return (x - 1) * m + y; }

// 并查集
int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y){ fa[find(x)] = find(y); }

// 判断在一个连通块中
bool check1(){ 
    int f = find(1);
    for(int i = 2; i <= n * m; i ++ )
        if(f != find(i)) return false;
    return true;
}

// 判断入度为0的点不超过1
bool check2(){
    int cnt = 0;
    for(int i = 1; i <= n * m; i ++ ) cnt += (!ind[i]);
    return cnt <= 1;
}

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        cin >> n >> m;
        for(int i = 1; i <= n; i ++ ) cin >> g[i], g[i] = " " + g[i];
        for(int i = 1; i <= n * m; i ++ ) fa[i] = i, ind[i] = 0;

        for(int i = 1; i <= n; i ++ )    // 在输入 a_{i,j} 时就开始合并
            for(int j = 1; j <= m; j ++ ){
                int c = mp[g[i][j]], d; cin >> d;
                int ni = i + d * dx[c], nj = j + d * dy[c];
                if(ni < 1 || ni > n || nj < 1 || nj > m) continue; // 出界
                merge(getID(i, j), getID(ni, nj));
                ind[getID(ni, nj)] ++ ;
            }

        cout << ((check1() & check2()) ? "Yes" : "No") << "\n";
    } 

    return 0;
}

F 不动的大图书馆想要出门

题意描述

给定一个 $n$ 个节点 $m$ 条有向边的有向图，边的长度未知。构造每条边的长度使得从 $1$ 号点到达其他所有点的最短路唯一，且所有边的长度范围需要控制在 $[1, k]$ 。「YAC Round 7」不动的大图书馆想要出门

解题思路 最短路 + 贪心 + 构造

我们可以先将每条边的长度都设置为 $1$，然后在这个初始的图上跑最短路。数据量较大，建议使用 堆优化 $\text{dijkstra}$ 算法。

最主要的问题就是如何使得最短路唯一。$\text{dijkstra}$ 算法的原理是不断将点进行扩展加入到从源点开始的一个最短路径网络中，假设源点为 $1$，当从 $u$ 扩展到点 $v$ 并且需要加入 $v$ 到最短路径网络中时，此时 $1 \sim v$ 的最短路也就确定了。

设 $dist[v]$ 为点 $1$ 到 $v$ 的最短路长度，显然，为了使得最短路唯一，在扩展过程中我们不容许出现 $dist[v] == dist[u] + 1$。基于贪心的思想，我们此时可以将 $w_{u, v}$ 进行 $+ 1$ 的操作，这样就可以避免存在相同的最短路出现。

在进行 $+1$ 操作中，如果出现了 $w_{u,v} > k$ 的情况，表示已经超过了限制 $k$，那么直接判定无解；如果跑完整个图都没有出现此情况，那么就是有解，并且一个合法的带权有向图也就构造出来了，最终依次输出边权即可。

代码整体基本上只是在 $\text{dijkstra}$ 最短路计数的基础上做了些修改，整体不难。最短路计数不熟悉的可以做一下 P1144 最短路计数

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef pair<int, int> pii;
const int N = 3e5 + 10, M = (N << 1);

int h[N], e[M], ne[M], w[M], idx; // 链式前向星
int dist[N], n, m, K;
bool st[N];

void add(int a, int b, int c){
    e[ ++ idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}

bool dijkstra(){
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    priority_queue<pii, vector<pii>, greater<pii> > q; 
    q.push({dist[1], 1});

    while(q.size()){
        auto [d, u] = q.top();
        q.pop();

        if(st[u]) continue;
        st[u] = true;

        for(int i = h[u]; i; i = ne[i]){
            int v = e[i];
            if(dist[v] > dist[u] + w[i]){
                dist[v] = dist[u] + w[i];
                q.push({dist[v], v});
            }else if(dist[v] == dist[u] + w[i]){
                w[i] ++ ;
                if(w[i] > K) return false;
            }
        }
    }

    return true;
}

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        cin >> n >> m >> K;
        memset(h, 0, sizeof(h)), idx = 0;
        for(int i = 1; i <= m; i ++ ){
            int u, v; cin >> u >> v;
            add(u, v, 1);
        }

        bool flag = dijkstra();

        cout << (flag ? "Yes" : "No") << '\n';
        if(flag){
            for(int i = 1; i <= m; i ++ ) cout << w[i] << ' ';
            cout << '\n';
        } 
    }

    return 0;
}

G 永远鲜红的幼月

题意描述

给定一个大小为 $n \times m$ 的方格图，设被红雾占据为 x，未被占据为 o，初始情况下全部为 o。现有 $q$ 次操作，分为两种操作：

• 1 x y，表示在位置 $(x, y)$ 朝上下左右四个方向释放无限长的红雾，注意 $(x, y)$ 不被红雾占据；

• 2 x1 y1 x2 y2，表示询问以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的方形区域中，被红雾占据的位置数量。

「YAC Round 7」永远鲜红的幼月

解题思路 线段树 + 容斥原理

本题只需要用一维线段树就可以解决。

我们假设区域范围内的被红雾占据的位置个数为 $s$。

令 $sx$ 为区域范围内释放过红雾的 行数，$sy$ 为区域范围内释放过红雾的 列数。$k$ 为一个抵消的位置数量。

那么 $s$ 的公式大概可以表示为：

$$s = sx \times (y_2 - y_1 + 1) + sy \times (x_2 - x_1 + 1) - k$$

而最关键的地方就在于求出抵消的位置数量 $k$。首先，在计算行列数量时，每一个交叉点多计算了一次，因此需要减去一次交叉的点数；而由于题中所描述的 释放位置不被红雾占据 以及红雾 相遇抵消，所以需要再减去一次交叉的点数。总计要减去两次交叉的点数，而交叉的点数就是 $sx \times sy$ 。故最后我们的公式如下：

$$s = sx \times (y_2 - y_1 + 1) + sy \times (x_2 - x_1 + 1) - 2 \times sx \times sy$$

观察公式我们可以发现，只要有了 $x$ 和 $y$ 相关的数量就可以求出区域范围内的红雾占据位置数量。故我们只需要实现两个单点修改、区间询问的线段树，一个线段树维护占据的行数，另一个维护占据的列数。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ls (u << 1)
#define rs (u << 1 | 1)

typedef long long ll;
const int N = 1e5 + 10;

int sum[2][N << 2], n, m, q; // 0 维护 x, 1 维护 y

void pushup(int c, int u){ sum[c][u] = sum[c][ls] + sum[c][rs]; }

void modify(int c, int u, int l, int r, int k){
    if(l == r){ sum[c][u] ^= 1; return; }
    int mid = l + r >> 1;
    if(k <= mid) modify(c, ls, l, mid, k);
    else modify(c, rs, mid + 1, r, k);
    pushup(c, u);
}

ll query(int c, int u, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr) return sum[c][u];
    int mid = l + r >> 1;
    ll res = 0;
    if(ql <= mid) res += query(c, ls, l, mid, ql, qr);
    if(qr > mid) res += query(c, rs, mid + 1, r, ql, qr);
    return res;
}

int main(){
    ios;

    cin >> n >> m >> q; // 初始全部为0 不需要事先建树
    while(q -- ){
        int op; cin >> op;
        if(op == 1){
            int x, y; cin >> x >> y;
            modify(0, 1, 1, n, x);  // 单点修改 x
            modify(1, 1, 1, m, y);  // 单点修改 y
        }else{
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            ll sx = query(0, 1, 1, n, x1, x2), sy = query(1, 1, 1, m, y1, y2);
            int lx = x2 - x1 + 1, ly = y2 - y1 + 1;
            cout << sx * ly + sy * lx - sx * sy * 2 << "\n"; // 容斥原理
        }
    }

    return 0;
}