2024 YAC Round 4 题解

A. 在扬大寻求算竞是否搞错了什么

题目描述

判断输入的正整数是否 $\le 4$，若 $\le 4$ 输出 OI；否则输出 ACM。「YAC Round 4」在扬大寻求算竞是否搞错了什么

解题思路 基本语法

基本语法题。

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

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

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        int x; cin >> x;
        cout << (x <= 4 ? "OI" : "ACM") << '\n';
    }

    return 0;
}

B. 灵梦的香火钱

题目描述

给定 $n$ 个元素，将这 $n$ 个元素两两进行配对，两个元素配对之后得到的值为对应数字首尾拼接得到的数字。求出最多能够凑出多少 $3$ 的倍数。https://www.luogu.com.cn/problem/T425162

解题思路 数学

我们可以假设当前配对的两个数字分别为 $x_1$ 和 $x_2$。我们可以进行对 $3$ 取模运算后，可以将两个数字分解后表示如下：

$$x_1 = k_1 \times 3 + r_1$$

$$x_2 = k_2 \times 3 + r_2$$

其中，$r$ 为 $x$ 对 $3$ 取模后得到的余数。

我们将 $x_1$ 的尾部和 $x_2$ 的首部进行拼接，同时我们可以假设 $x_2$ 的数字长度为 $m$，那么也就是说拼接后得到的数字将会是 $x_1 \times 10^m + x_2$，即：

$$(k_1 \times 3) \times 10^m + r_1 \times 10^m + k_2 \times 3 + r_2$$

取模运算是符合加法和乘法运算的，故我们对当前拼接后得到的数字的各个部分进行对 $3$ 取模:

$$(k_1 \times 3) \times 10^m \bmod 3 = k_1 \times 3 \bmod 3 = 0$$

$$r_1 \times 10^m \bmod 3 = r_1$$

$$k_2 \times 3 \bmod 3 = 0$$

$$r_2 \bmod 3 = r_2$$

因此，拼接后得到数字对 $3$ 取模后即：$r_1 + r_2$。（会发现，拼接得到数字模3的结果和相加是一样的）

那么，要使得拼接后为 $3$ 的倍数，显然 $r_1 + r_2 = 0$ 或者 $r_1 + r_2 = 3$，所以要么 $r_1$ 和 $r_2$ 都为 $0$；要么 $r_1$ 和 $r_2$ 中一个为 $1$ 另一个为 $2$。

也就是余数为 $0$ 的只可以和余数同样是 $0$ 的相匹配；余数为 $1$ 或 $2$ 的，只可以和 $2$ 或 $1$ 匹配。对于前者，由于我们不匹配的数字不算，所以 $r_1 + r_2 = 0$ 最多可以匹配出 $\left \lfloor \frac{cnt_0}{2} \right \rfloor$ 个 $3$ 的倍数；对于后者，则为 $\min(cnt_1, cnt_2)$ 。

故我们只需要统计每个余数有多少个元素，最后输出答案为 $\left \lfloor \frac{cnt_0}{2} \right \rfloor + \min(cnt_1, cnt_2)$ 。

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

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

int main(){
    ios;

    vector<int> cnt(3);
    int n; cin >> n;
    while(n -- ){
        int x; cin >> x;
        cnt[x % 3] ++ ;
    }
    cout << (cnt[0] / 2 + min(cnt[1], cnt[2])) << '\n';

    return 0;
}

C. 青春异或少年不会遇到按位与学姐

题目描述

给定一个正整数 $x$，找出最小的满足以下条件的正整数 $y$：

• $x$ $\text{and}$ $y > 0$

• $x$ $\text{xor}$ $y > 0$

「YAC Round 4」青春异或少年不会遇到按位与学姐

解题思路 位运算 + 贪心

对于第一个条件，两个数字 $x$ 和 $y$ 按位与大于 $0$，显然 $x$ 和 $y$ 的对应二进制位中至少需要有 $1$ 位同时是 $1$，那么为了让 $y$ 尽可能小，我们取 $x$ 最后一位 $1$ 即前面位的所有 $0$ 即可。例如 $10 = (1010)_2$，此时取 $2 = (10)_2$ 即可，也就是 $\text{lowbit} (10)$。 浅谈lowbit运算 - Seaway-Fu - 博客园

对于第二个条件，两个数字 $x$ 和 $y$ 按位异或大于 $0$，那么我们至少需要有一位二进制位不同。在第一个条件下我们取了 $y^{'} = \text{lowbit}(x)$ 。如果此时 $y^{'} \not = x$，那么就取此时的 $y = y^{'}$ 即可。

如果 $y^{'} = x$，说明此时取的 $y^{'}$ 和 $x$ 每一位都一样，为了使得 $y$ 尽量小，我们只需要让此时 $y^{'}$ 的最低位的 $0$ 为 $1$ 即可。一般情况下，我们只要使得 $y^{'}$ 的最低位变为 $1$ 即可，也就是 取 $y = y^{'} + 1$ 即可。

但是，当 $x = 1$ 时，需要特殊判断一下，此时为了满足第一个条件，$y^{'} = 1$，为了满足第二个条件，由于最低位取 $1$，故只能使得第二位为 $1$，也就是取 $y = 3$。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define lowbit(x) (x) & (-x)
typedef long long ll;

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        ll x; cin >> x;
        if(x == 1){
            cout << 3 << '\n';
            continue;
        }
        ll y = lowbit(x);
        cout << y + (y == x) << '\n';
    }

    return 0;
}

D. K-ON!

题目描述

给定 $n$ 个社团，每个社团有一个表演时间 $a_i$，按照下标顺序上台表演，舞台可以同时容纳多个是社团进行表演（即舞台有一个大小）。给定一个总时间限制 $t$，在所有社团表演总时间不超过 $t$ 的情况下，使得舞台大小最小化。「YAC Round 4」K-ON!

解题思路 二分 + 堆

可以发现舞台越大，总时间必定越少；反之亦然。

显然问题具有二段性，因此我们考虑二分答案（即舞台大小）。

假设二分时的舞台大小为 $k$。在二分的判断函数中，我们需要每次取出当前 $k$ 个社团中最早表演完的一个社团让其下场，同时按照编号顺序让下一个要上场的社团上场开始表演。故我们可以用堆（优先队列）维护当前 $k$ 个社团表演结束时间，因为要取最小值，所以我们选用的是小根堆来进行模拟。

如果在模拟过程中，当前要上场的社团表演时间大于总时间限制时，就返回 $\text{false}$；模拟到最后都没有出现超过时间限制的社团，那么就返回 $\text{true}$ 。

PS：题目保证一定有解，所以不用担心一开始就出现无法表演结束的社团。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e4 + 10;
int a[N], n, t;

bool check(int k){
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i = 1; i <= k; i ++ ) q.push(a[i]);
    for(int i = k + 1; i <= n; i ++ ){
        int now = q.top();
        q.pop();
        if(now + a[i] > t) return false; // 超出时间限制
        q.push(now + a[i]);
    }
    return true;
}

int main(){
    ios;

    cin >> n >> t;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    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;
}

E. 早苗的机动战士高达梦

题目描述

给定一个图，图中构成多个连通块。先输出当前图中的连通块个数，然后给定 $k$ 次询问，每次去除一个点及其邻接的边，问去除当前这个点时图中有多少连通块。「YAC Round 4」早苗的机动战士高达梦

解题思路 并查集

我们可以用并查集维护连通块个数。

如果我们正向考虑这个问题，那么我们每次询问都需要重新建立关系，然后得到去除当前点后的连通块个数，这显然是会超时的。

故我们考虑逆向思考这个问题。预先将所有的边都存起来。我们可以先得到经过最后一次操作后，图中还有多少连通块。然后，每一次还原一个点，相当于每次加入一个点及其邻接边，逆向还原每次操作之前图中的连通块个数。

答案存储在数组中，最后输出即可。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define fi first
#define se second
const int N = 4e5 + 10;

int n, m, k, fa[N], a[N], res[N];
int h[N], e[N], ne[N], idx;
bool ban[N];

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

int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main(){
    ios;

    cin >> n >> m;
    while(m -- ){
        int u, v; cin >> u >> v;
        add(u, v), add(v, u);
    }
    cin >> k;
    for(int i = 1; i <= k; i ++ ) cin >> a[i], ban[a[i]] = true;
    for(int i = 0; i < n; i ++ ) fa[i] = i;

    // 先得到最后一次询问之后的连通块个数
    int tot = n - k; // 最后一次询问之后图中共有 n - k 个点
    for(int u = 0; u < n; u ++ ){
        if(ban[u]) continue;
        for(int i = h[u]; i; i = ne[i]){
            int v = e[i];
            if(ban[v]) continue;
            int fx = find(u), fy = find(v);
            if(fx != fy) fa[fy] = fx, tot -- ; // 合并两个连通块
        }
    }
    res[k + 1] = tot;

    // 逆向还原
    for(int j = k; j; j -- ){
        int u = a[j];
        ban[u] = false; // 加入点
        tot ++ ;   // 一个点一个连通块
        for(int i = h[u]; i; i = ne[i]){
            int v = e[i];
            if(ban[v]) continue;
            int fx = find(u), fy = find(v);
            if(fx != fy) fa[fy] = fx, tot -- ; // 合并两个连通块
        }
        res[j] = tot;
    }

    // 输出答案
    for(int i = 1; i <= k + 1; i ++ ) cout << res[i] << '\n';

    return 0;
}

F. 爱丽丝送给魔理沙的手链

题目描述

假设 $b$ 为蓝色，$g$ 为金色。给定一个长度 $n$，求出用 $b$ 和 $g$ 可以构造出的相邻元素不能同时为金色，即不能同时为 $g$（或者说相邻元素至少有一个为蓝色，即至少有一个为 $b$） 的长度为 $n$ 的 环状 字符串方案数。「YAC Round 4」爱丽丝送给魔理沙的手链

解题思路 dp + 矩阵加速

我们可以先考虑一下 $n \le 10^6$ 时如何解决这个问题。显然，我们可以用动态规划解决这个子问题。

用 $dp[i][0]$ 表示构造的长度为 $i$ 且第 $i$ 个宝石选用 金色宝石 的方案数； $dp[i][1]$ 表示构造的长度为 $i$ 且第 $i$ 个宝石选用 蓝色宝石 的方案数。

题中要求相邻的两个不能同时为金色。对于 $dp[i][0]$ ，第 $i$ 个选择了金色，那么前一位只能用蓝色；对于 $dp[i][1]$，第 $i$ 个选择了蓝色，那么前一位选择蓝色或金色都可以。 故状态转移方程如下：

$$\begin{cases} dp[i][0] = dp[i - 1][1] \\\\ dp[i][1] = dp[i - 1][0] + dp[i - 1][1] \end{cases}$$

由于是 环状 的，我们还需要进行一下初始化的分类讨论。

• 如果第 $1$ 个选择金色宝石，那么第 $n$ 个宝石只能选择蓝色宝石（因为环形连接处也需要满足条件），故此情况答案为 $dp[n][1]$

• 如果第 $1$ 个选择蓝色宝石，那么第 $n$ 个宝石两种颜色都可以选择，故此情况答案为 $dp[n][0] + dp[n][1]$

解决 $n \le 10^6$ 的子任务，只需要分情况跑两次线性dp，然后答案就是两种情况相加。

以下是解决子任务的代码。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 1e6 + 10, mod = 1e9 + 7;
int dp[N][2], n;

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ){
        cin >> n;
        ll res = 0;

        dp[1][0] = 1, dp[1][1] = 0;    // 第一个为金色宝石
        for(int i = 2; i <= n; i ++ ){
            dp[i][0] = dp[i - 1][1] % mod;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
        }
        res = (res + dp[n][1]) % mod;  // 最后一个只能选蓝色

        dp[1][0] = 0, dp[1][1] = 1;    // 第二个为蓝色宝石
        for(int i = 2; i <= n; i ++ ){
            dp[i][0] = dp[i - 1][1] % mod;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
        }
        res = (res + dp[n][0] + dp[n][1]) % mod; // 最后一个两种颜色皆可选

        cout << res << '\n';
    }

    return 0;
}

但是，$n \le 10^{18}$，用普通的线性动态规划显然无法解决这个问题。

因此我们需要用到一个比较进阶的技巧，矩阵加速 。

我们假设一个行向量为 $\begin{bmatrix}dp_{i,0} & dp_{i,1}\end{bmatrix}$，由先前的状态转移方程，我们可以构造一个矩阵实现 $\begin{bmatrix}dp_{i,0} & dp_{i,1}\end{bmatrix}$ 到 $\begin{bmatrix}dp_{i+1,0} & dp_{i+1,1}\end{bmatrix}$ 的线性变换。

可以构造矩阵得到线性变换如下：

$$\begin{bmatrix} dp_{i,0} & dp_{i,1} \end{bmatrix} \begin{bmatrix} 0 & 1 \\\\ 1 & 1 \end{bmatrix} = \begin{bmatrix} dp_{i + 1,0} & dp_{i + 1,1} \end{bmatrix}$$

分两种初始情况用矩阵快速幂就可以顺利解决这个问题，时间复杂度为 $O(t^3 \log n)$，其中 $t = 2$（ $t$ 为矩阵大小）。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mst(a, x) memset(a, x, sizeof(a))
typedef long long ll;
const int mod = 1e9 + 7;

struct Matrix{
    ll mat[2][2];
    Matrix(){ mst(mat, 0); }
    Matrix operator * (const Matrix &b){
        Matrix res;
        for(int i = 0; i < 2; i ++ )
            for(int j = 0; j < 2; j ++ )
                for(int k = 0; k < 2; k ++ )
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * b.mat[k][j] % mod) % mod;
        return res;
    } 
}ans, base;

void init(int flag){
    mst(base.mat, 0), mst(ans.mat, 0); // 初始化
    base.mat[0][1] = base.mat[1][0] = base.mat[1][1] = 1;
    if(!flag) ans.mat[0][0] = 1;  // 第一个为金色宝石
    else ans.mat[0][1] = 1;       // 第一个为蓝色宝石
}

void mat_qmi(ll n){
    while(n){
        if(n & 1) ans = ans * base;
        base = base * base;
        n >>= 1;
    }
}

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        ll n; cin >> n;
        n -- ;       // 快速幂相当于要跑 n-1 次方
        ll res = 0;

        // 第一个为金色宝石
        init(0);
        mat_qmi(n);
        res = (res + ans.mat[0][1]) % mod;

        // 第一个为蓝色宝石
        init(1);
        mat_qmi(n);
        res = (res + ans.mat[0][0] + ans.mat[0][1]) % mod;

        cout << res << '\n';
    }

    return 0;
}