2024 YAC Round 13 题解

A 欢迎来到夜雀食堂

出题人：MarisaMagic

题意描述

输出 Welcome to Touhou Mystia's Izakaya. 「YAC Round 13」欢迎来到夜雀食堂

解题思路

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

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

void marisa(){
    puts("Welcome to Touhou Mystia's Izakaya.");
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

B 好评热火朝天

出题人：MarisaMagic

题意描述

给定 $n$ 个字符串，求最大连续出现 pink 的次数。「YAC Round 13」好评热火朝天

解题思路 （模拟）

定义一个计数 $cnt$ 累计 pink 出现的次数。遍历 $n$ 个字符串，如果遇到 pink 计数 $\text{+1}$，并更新答案；否则计数清 $0$。

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

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

void marisa(){
    int n, mx = 0, cnt = 0; cin >> n;
    for(int i = 1; i <= n; i ++ ){
        string s; cin >> s;
        if(s[0] == 'p') cnt ++ , mx = max(mx, cnt);
        else cnt = 0;
    }
    cout << mx << "\n";
}

int main(){
    ios;

    int T = 1; // cin >> T;
    while(T -- ) marisa();

    return 0;
}

C 逆转天地

出题人：MarisaMagic

题意描述

对于一个长度为 $n$ 的字符串 $s$，另一个长度相同的字符串 $t$ 的 不相似度 定义为：不同位置上的不同字符的对数。给定一个 $s$，构造一个长度相同的 $t$ 使得不相似度最大化。「YAC Round 13」逆转天地

解题思路 （字符串，贪心，构造）

考虑将 $t$ 的每一个位置上的不相似度最大化，也就是让每个位置上的字符和 $s$ 中其他位置的字符尽可能都不相同。

对于 $t$ 的位置 $i$ 上的字符，直接将其设定为 $s$ 中 除了 $i$ 以外 的 所有位置上出现次数最少的字符 即可。字符串只包含小写字母，故可以预处理统计 $s$ 中每个字符的个数，在枚举 $t$ 的每个位置时，枚举 $s$ 中其他位置 $26$ 个字符哪个出现次数最少。

需要注意的是，枚举出现次数最少的字母时，$s$ 中当前位置的字母出现次数需要 $\text{-1}$。

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

void marisa(){
    int n; cin >> n;
    string s; cin >> s;
    vector<int> cnt(26);
    for(const auto &ch : s) cnt[ch - 'a'] ++ ;
    for(const auto &ch : s){
        int mn = 1e9; char res;
        for(int i = 0; i < 26; i ++ )
            if(mn > cnt[i] - (ch - 'a' == i)){
                mn = cnt[i] - (ch - 'a' == i);
                res = 'a' + i;
            }
        cout << res;
    }
}

int main(){
    ios;

    int T = 1; //cin >> T;
    while(T -- ) marisa();

    return 0;
}

D 露易兹的旅行博客

出题人：MarisaMagic

题意描述

给定一个 $n \times m$ 的矩阵，每一步只能向右或向下移动一次，遇到 0 加 $0$ 分；遇到 1 加 1 分；遇到 ? 可以使用一次拍照的机会加 $1$ 分，也可以不使用拍照的机会加 $0$ 分。求使用不超过 $p$ 次拍照机会从 $(1, 1)$ 移动到 $(n, m)$ 的最大得分。「YAC Round 13」露易兹的旅行博客

解题思路 （动态规划）

考虑动态规划，设 $dp_{i,j,k}$ 表示走到 $(i, j)$ 且使用不超过 $k$ 次拍照机会获得的最大得分。有如下状态转移方程：

• 当遇到字符 $0$ 或 $1$ 时

  $$dp_{i,j,k} = \begin{cases} \max(dp_{i-1, j, k}, dp_{i, j-1, k}) + 1, \ g_{i,j} = 1 \\\\ \max(dp_{i-1, j, k}, dp_{i, j-1, k}), \ g_{i, j} = 0 \end{cases}$$

• 当遇到字符 $?$ 时，可以不使用机会

  $$dp_{i, j, k} = \max(dp_{i-1, j, k}, dp_{i, j-1, k})$$

  也可以使用一次机会加 1 分

  $$dp_{i, j, k} = \max(dp_{i-1, j, k-1}, dp_{i, j-1, k-1}) + 1, \ k > 0$$

最终答案就是 $dp_{n, m, p}$。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 510, M = 310;

string g[N];
int n, m, p, f[N][N][M];

void marisa(){
    cin >> n >> m >> p;
    for(int i = 1; i <= n; i ++ ) cin >> g[i], g[i] = " " + g[i];
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            for(int k = 0; k <= p; k ++ ){
                if(g[i][j] != '?'){
                    if(g[i][j] == '1'){
                        f[i][j][k] = max(f[i - 1][j][k], f[i][j - 1][k]) + 1;
                    }else{
                        f[i][j][k] = max(f[i - 1][j][k], f[i][j - 1][k]);
                    }
                }else{
                    f[i][j][k] = max(f[i - 1][j][k], f[i][j - 1][k]);
                    if(k > 0){
                        f[i][j][k] = max(f[i - 1][j][k - 1], 
                        f[i][j - 1][k - 1]) + 1;
                    }
                }
            }

    cout << f[n][m][p] << "\n";
}

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ) marisa();

    return 0;
}

E 月都全能特训

出题人：MarisaMagic

题意描述

有 $n$ 个技能，$m$ 个月光草。第 $i$ 个月光草可以在技能 $t_i$ 上提升 $c_i$ 的能力值。求在不连续使用两个相同对应技能的月光草的情况下，使得 $n$ 个技能的提升能力值都 至少 达到 $k$ 所需的最少月光草个数。 「YAC Round 13」月都全能特训

解题思路 （排序，贪心）

对于每个技能，选择更大提升值的月光草，到达 $k$ 所需的月光草更少。可以用 pair 存储每个月光草的 $t_i$ 和 $c_i$，然后按照 $c_i$ 为第一关键字从大到小排序。从 $1$ 枚举到 $m$ 累计每个技能的提升值，并记录每个技能所需的最少月光草数量 $need_i$。枚举完后所有技能所需的月光草数量记为 $ans$。

首先每个技能的提升值要确保能到达 $k$。在贪心枚举的过程中，统计一下到达 $k$ 的技能数量是否有 $n$ 个即可。如果无法满足，输出 $-1$。

现在考虑是否可满足交叉使用不同对应技能的月光草，记所需最多数量月光草为 $need_{\max}$，对应技能编号为 $id_{\max}$。有一个性质即 $2 \times need_{\max} - 1 \le ans$ 时，这 $ans$ 个可以实现交叉使用（可以自行模拟验证）：

• 如果 $2 \times need_{\max} - 1 \le ans$，我们已经可以交叉使用了。故此时的答案就是 $ans$；

• 如果 $2 \times need_{\max} - 1 > ans$，我们还需要再多使用 除 $id_{\max}$ 之外 的其它种类种任意 $2 \times need_{\max} - 1 - ans$ 个月光草就可以刚好实现交叉。

  我们可以累计其它种类剩余的月光草数量，记为 $le$。若 $2 \times need_{\max} - 1 - ans \le le$，就可以刚好交叉。故此时答案为 $2 \times need_{\max} - 1$；否则，还是无法满足交叉，此时输出 $-1$。

#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
using pii = pair<int, int>;

void marisa(){
    int n, m, k; cin >> n >> m >> k;
    vector<pii> p(m + 1);
    vector<int> cnt(n + 1); // 统计每种月光草的数量
    for(int i = 1; i <= m; i ++ ) cin >> p[i].fi, cnt[p[i].fi] ++ ;
    for(int i = 1; i <= m; i ++ ) cin >> p[i].se;
    sort(begin(p) + 1, end(p), [](pii &x, pii &y){
        return x.se > y.se; 
    });
    
    int ans = 0, mx_need = 0, mx_id = 0, tot = 0;
    vector<int> sum(n + 1), need(n + 1); // 每个技能提升值和所需数量
    for(int i = 1; i <= m; i ++ ){
        auto [id, c] = p[i];
        if(sum[id] >= k) continue; // 已经达到k就跳过

        sum[id] += c;
        if(sum[id] >= k) tot ++ ; // 记录满足大于等于k的技能数

        need[id] ++ ;
        if(need[id] > mx_need){ // 记录所需月光草最大的数量及其种类编号
            mx_need = need[id]; 
            mx_id = id;
        }

        ans ++ ;
    }

    if(tot < n){ // 无法使得所有技能满足大于等于k
        cout << -1 << "\n";
        return;
    }

    if(mx_need * 2 - 1 <= ans){ // 已经可以交叉
        cout << ans << "\n";
        return;
    }

    int le = 0; // 剩余的其他题目的数量
    for(int i = 1; i <= n; i ++ ) if(i != mx_id) le += cnt[i] - need[i];
    if(mx_need * 2 - 1 - ans <= le) cout << mx_need * 2 - 1 << "\n"; 
    else cout << -1 << "\n";
}

int main(){
    ios;

    int T = 1; //cin >> T;
    while(T -- ) marisa();

    return 0;
}

F 樱花树下的欲望之果

出题人：MarisaMagic

题意描述

给定一个数组 $a_1, a_2, \ldots, a_n$，求有多少个子区间 $[l, r]$ $(1 \le l \le r \le n)$ 满足区间所有数的乘积 $\prod_{i=l}^{r}a_i$ 是一个完全平方数。「YAC Round 13」樱花树下的欲望之果

解题思路 （质因数分解，前缀异或和，动态规划，状态压缩）

可以发现，一个数是完全平方数时，它的所有质因子的指数都为偶数。因此，我们可以预处理对每个 $a_i$ 进行质因数分解（$a_i$ 范围比较小），并计算每种质因子的指数前缀和，可以判断每个子区间的乘积是否时完全平方数。但是，枚举子区间是 $\mathcal{O}(n^2)$ 的，会超时。

我们可以用 状态压缩 来 存储每个数质因子的指数的奇偶性，$a_i$ 最大只有 $30$，因此我们用 $30$ 位就可以表示每个质因子指数的奇偶性（当然也可以预处理 $30$ 以内质数，用更小的位数表示），$1$ 表示指数为奇数，$0$ 表示指数为偶数。

当一个区间 $[l, r]$ 所有质因子指数和都是偶数时，前缀异或和 $pre_{\text{xor}}[r]$ 和 $pre_{\text{xor}}[l - 1]$ 的状态表示显然是一样的。

故考虑动态规划，从 $1$ 到 $n$ 遍历数组，边遍历边计算每个数 $a_i$ 得到的质因子指数状态，并计算前缀异或和。设 $dp_x$ 为遍历到当前位置之前前缀异或和 $x$ 出现的次数，故只要在遍历过程中累加 $dp_x$，再更新 $dp_x \text{+=} 1$ 即可。（由于数字比较大，需要用 map 实现 $dp_x$）

时间复杂度为 $\mathcal{O}(n\sqrt{a_{\max}})$，其中 $a_{\max}$ 为所有 $a_i$ 的最大值。

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

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

void marisa(){
    int n; cin >> n;
    vector<int> s(n + 1); // 每个数质因子指数状态
    for(int i = 1, x; i <= n; i ++ ){ // 质因数分解，状态压缩
        cin >> x;
        for(int p = 2; p * p <= x; p ++ )
            while(x % p == 0) x /= p, s[i] ^= (1 << p);
        if(x > 1) s[i] ^= (1 << x);
    }

    long long ans = 0;
    unordered_map<int, int> dp; // 统计前面前缀异或和出现次数
    dp[0] = 1; // 注意 dp[0] 赋值为 1
    for(int i = 1; i <= n; i ++ ){
        s[i] ^= s[i - 1]; // 前缀异或和
        ans += dp[s[i]] ++ ; // 累加答案并更新异或和出现次数
    }
    cout << ans << "\n";
}

int main(){
    ios;

    int T = 1; //cin >> T;
    while(T -- ) marisa();

    return 0;
}

G 超级tag料理大赛

出题人：MarisaMagic

题意描述

有一个数轴，数轴上有 $n$ 个不同的整数点，分为蓝色和红色。有 $q$ 次操作，维护一个可重集合存放线段：

• 1 l r：将所有 $l \le x \le y \le r$ 且 $x, y$ 均为整数的线段 $[x, y]$ 放到集合中。

• 2 k：撤销第 $k$ 次操作中添加的所有线段。

初始情况下和每次操作后，可以任意次选择线段。每次选出一条线段 $[x, y]$，需要满足 位于端点 $x$ 和 $y$ 上 的整数点均为红点。选出后，线段区间 $[x, y]$ 内所有蓝点均会变成红点。

在初始情况下和每次操作后，判断是否能够找到至少一种合法的选择方案使得所有 $n$ 个整数点都变成红点。

「YAC Round 13」超级tag料理大赛

各组询问之间独立。

解题思路 （线段树，离散化，二分）

题目看似每次增加了很多线段，但实际上除了 $n$ 个整数点之外的点都无意义，且操作中最有用的线段只有那个 端点均为红点 且可以覆盖最大范围的线段，大范围一定是可以覆盖小范围的。因此，每次操作只需要考虑一个线段即可。

故我们可以将增加操作看作每次增加一条 $[l, r]$ 范围内端点为红点的最长线段 $[x, y]$，将区间 $[x, y]$ 的蓝点都变成红点。

我们每次增加的线段都是覆盖范围最大的，而又存在撤销操作，故我们可以将这一区间修改操作看作是在 $[x, y]$ 的每个整数点上 $+1$。撤销操作也很简单，只需要记录每一次增加的 $[x, y]$，当出现撤销操作时，取出并将区间 $[x, y]$ 整数点都 $-1$ 即可。
每次询问只需要判断整个数轴上的最小值是否 $\le 0$ 即可判断是否还存在没有被覆盖到的蓝点。如果还存在蓝点，那么就集合中的所有线段无法使得所有点变成红点。

因此，我们考虑用线段树维护区间最小值，支持区间修改。每次询问查询 $n$ 个整数点的最小值是否 $\le 0$ 即可。

如何实现找到最大覆盖范围的线段 $[x, y]$ ？我们可以离散化所有的初始红色点，每次操作后二分区间范围找到第一个大于等于 $l$ 的位置的红点和最后一个小于等于 $r$ 的位置的红点即可。

时间复杂度为 $\mathcal{O}(n \log{n})$。

#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)
#define mid (l + r >> 1)
const int N = 5e5 + 10;

int n, m, q, a[N], p[N], b[N], id[N], mn[N << 2], lazy[N << 2];
pair<int, int> ops[N];

inline void pushup(int u){ mn[u] = min(mn[ls], mn[rs]); }

inline void pushdown(int u){
    if(lazy[u]){
        lazy[ls] += lazy[u], mn[ls] += lazy[u];
        lazy[rs] += lazy[u], mn[rs] += lazy[u];    
        lazy[u] = 0;
    }
}

void build(int u, int l, int r){
    if(l == r){ mn[u] = a[l]; return; }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int ql, int qr, int x){
    if(ql <= l && r <= qr){ mn[u] += x, lazy[u] += x; return; }
    pushdown(u);
    if(ql <= mid) modify(ls, l, mid, ql, qr, x);
    if(qr > mid) modify(rs, mid + 1, r, ql, qr, x);
    pushup(u);
}

int query(int u, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr) return mn[u];
    pushdown(u);
    int res = 1e9;
    if(ql <= mid) res = min(res, query(ls, l, mid, ql, qr));
    if(qr > mid) res = min(res, query(rs, mid + 1, r, ql, qr));
    return res;
}

int main(){
    ios;

    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ) cin >> p[i];
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        if(a[i]) b[ ++ m] = p[i], id[m] = i; // 离散化满足状态的红点
    }

    build(1, 1, n);
    cout << (query(1, 1, n, 1, n) <= 0 ? "No" : "Yes") << "\n";

    for(int i = 1, op, l, r, x, y, k; i <= q; i ++ ){
        cin >> op;
        if(op == 1){
            cin >> l >> r;
            x = id[lower_bound(b + 1, b + m + 1, l) - b]; // 二分找到最大范围可以染红的区间
            y = id[upper_bound(b + 1, b + m + 1, r) - b - 1];
            if(x && y && x <= y){
                modify(1, 1, n, x, y, 1);
                ops[i] = {x, y};
            }
        }else{
            cin >> k;
            auto [x, y] = ops[k];
            if(x && y && x <= y) modify(1, 1, n, x, y, -1);
        }
        cout << (query(1, 1, n, 1, n) <= 0 ? "No" : "Yes") << "\n";
    }

    return 0;
}