2024 YAC Round 6 题解

A. 琪露诺的超级⑨拆分

题目描述

定义 $k$ 阶数字为：每一位都是 $9$ 的，且位数为 $k$ 的倍数的正整数。给定多次询问，每次询问一个数字 $n$，判断这个数字是否可以拆成若干个 $k$ 阶数字的和。「YAC Round 6」琪露诺的超级⑨拆分

解题思路 数学

我们可以发现，比最小 $k$ 阶数字大的 $k$ 阶数字，都是最小 $k$ 阶数字的倍数。

例如，$k = 3$，那么最小 $k$ 阶数字就是 $999$，比它大的 $k$ 阶数字有 $999999$、$999999999$ 等等，而且也都是最小 $k$ 阶数字的倍数。

因此，我们要判断用若干个 $k$ 阶数字去凑成数字 $n$ 时，只需要用最小 $k$ 阶数字去凑即可。

我们的问题就转换为：判断数字 $n$ 是否是最小 $k$ 阶数字的倍数。

注意数据范围，需要开 $\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;

bool check(ll k, ll n){
    ll c = 0;
    while(k -- ) c = c * 10 + 9; // 得到最小k阶数字
    return n % c == 0;
}

int main(){
    ios;

    int q; cin >> q;
    while(q -- ){
        ll k, n; cin >> k >> n;
        cout << (check(k, n) ? "aya" : "baka") << '\n';
    }

    return 0;
}

B. 琪露诺的实力隐藏法

题目描述

给定一个长度为 $n$ 的数组，找到一个排序方法使得数组中最大的 $a_i - a_{i + 1}$ 最小。「YAC Round 6」琪露诺的实力隐藏法

解题思路 贪心

我们发现将数组 $a$ 从小到大排序后，满足所有的 $a_i - a_{i + 1} \le 0$ ，即全部为非正数；否则，一定会存在一个 $a_i - a_{i + 1} > 0$，从而导致数组中最大的 $a_i - a_{i + 1}$ 增大，变为了一个正数。

所以，将数组从小到大排序即为最优策略。最后枚举 $a_i - a_{i+1}$ 取最大值即可。

#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; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    
    sort(a.begin() + 1, a.end());
    
    int mx = -1e9;
    for(int i = 1; i < n; i ++ ) mx = max(mx, a[i] - a[i + 1]);
    cout << mx << '\n';

    return 0;
}

C. 琪露诺的完美算术教室

题目描述

询问一个区间 $[L, R]$，这个区间中有多少个数字 $X$ 满足存在自然数 $a, b, c, d$ 使得 $X = 2^a \times 3^b \times 5^c \times 7^d$ 。「YAC Round 6」琪露诺的完美算术教室

解题思路 预处理 + 快速幂

询问的区间的数据范围为 $[1, 10^9]$，直接去判断区间内每个数字是否可以凑成 $2^a \times 3^b \times 5^c \times 7^d$ 显然是会超时的。

因此，我们可以预处理 $[1, 10^9]$ 范围内所有的 $2^a \times 3^b \times 5^c \times 7^d$。我们把 $2、3、5、7$ 看作是四个因子。

对于每个因子 $p$，最多不会超过 $\left \lfloor \log_p 10^9 \right \rfloor$ 次方。预处理枚举过程中将所有符合要求的数字放到一个容器中（因为都是质数，所以仔细想想发现是不会出现重复的数字的，不需要用集合 $\text{set}$）。最后经过预处理后发现符合要求的数字并不是很多。

对于询问区间，枚举容器中存储的数字判断是否在 $[L, R]$ 范围内即可。

使用 $\text{C++}$ 的同学需要注意一点，函数 $pow$ 可能存在精度缺失问题，不建议使用。因此，我们 $\text{C++}$ 选手可能还需要用到快速幂。

在预处理枚举的过程中，我们需要提前判断每个因子的次方相乘是否已经超过了 $10^9$，因为如果不提前判断，可能会出现多个将近 $10^9$ 的数字相乘，这时候连 $\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;
const int N = 1e9 + 2;

vector<int> v;
// 快速幂
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

void work(int n){
    for(int a = 0; a <= (int)(log(n) / log(2)) + 1; a ++ ){
        ll c2 = qmi(2, a);
        if(c2 >= n) break;
        for(int b = 0; b <= (int)(log(n) / log(3)) + 1; b ++ ){
            ll c3 = qmi(3, b);
            if(c2 * c3 >= n) break; // 提前判断
            for(int c = 0; c <= (int)(log(n) / log(5)) + 1; c ++ ){
                ll c5 = qmi(5, c);
                if(c2 * c3 * c5 >= n) break;  // 提前判断
                for(int d = 0; d <= (int)(log(n) / log(7)) + 1; d ++ ){
                    ll c7 = qmi(7, d);
                    if(c2 * c3 * c5 * c7 >= n) break;
                    v.push_back(c2 * c3 * c5 * c7);
                }
            }
        }
    }
}

int main(){
    ios;

    work(N);

    int res = 0, l, r; cin >> l >> r;
    for(auto &x : v)
        if(x >= l && x <= r) res ++; 
        
    cout << res << '\n';

    return 0;
}

D. 琪露诺的Homo馆攻坚战

题目描述

自己手中有 $m$ 张符卡，可以把它们随意分配到 $1 \sim n$ 个城堡，即分配为 $a_1, a_2, \ldots, a_n$。每轮进攻中，如果 $a_i$ 严格大于 $2 \times b_i$，那么就可以获得 $i$ 分。每轮进攻的分配方案必须一致，已知 $s$ 轮的 $b_1, b_2, \ldots, b_n$，求最大的总得分。「YAC Round 6」琪露诺的Homo馆攻坚战

解题思路 分组背包 + 贪心 + 排序

可以用动态规划来解决这个问题，用 $dp[i][j]$ 表示进攻前 $i$ 轮进攻，每轮进攻都使用 $j$ 张符卡的最大总得分。一共有 $s$ 轮进攻，每轮进攻有 $m$ 张符卡。

对于第 $i$ 个城堡。如果要得到 $i$ 分，那么我们基于贪心的策略，最少需要分配 $2 \times b_i + 1$ 张符卡。我们可以先对每个城堡 $i$ 的所有 $s$ 轮的 $b_i$ 进行从小到大排序。经过排序后，如果分配的 $a_i$ 为 $2 \times b_{ik} + 1$，也就是说在 $s$ 轮进攻中在城堡 $i$ 上分配的符卡有 $k$ 次可以击败对方，那么在城堡 $i$ 上就可以得到 $k \times i$ 的分数。（$b_{ik}$ 为所有 $s$ 轮的 $b_i$ 排序后的第 $k$ 个）

因此，我们可以把符卡的数量 $m$ 看作是背包容量，共 $n$ 组物品，每组中的物品是对应的第 $i$ 座城堡所有的 $b_i$ 构成的，每组物品共 $s$ 个物品，第 $k$ 个物品的体积为 $2 \times b_{ik} + 1$，价值为 $k \times i$ 。每组物品最多选择一个。这就是典型的分组背包模型了。

最后，我们套用分组背包的模板即可。（本题解的分组背包模板加上了空间优化，通过逆向枚举背包容量省去了第一个维度）AcWing 分组背包模板

#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 = 2e4 + 10;

int s, n, m;
int g[110][110];
ll dp[N];

int main(){
    ios;

    cin >> s >> n >> m;
    for(int i = 1; i <= s; i ++ )
        for(int j = 1; j <= n; j ++ ) cin >> g[i][j];

    for(int i = 1; i <= n; i ++ ){
        // 分为 n 组，分组背包
        vector<int> b(s + 1); // 每组s个物品
        for(int j = 1; j <= s; j ++ ) b[j] = g[j][i];
    
        sort(b.begin() + 1, b.end()); // 排序

        for(int j = m; j >= 0; j -- )     // 同组内最多只选一个
            for(int k = 1; k <= s; k ++ ) // 有 k 轮可以攻下城堡 i
                if(j >= 2 * b[k] + 1)     // 严格大于镇守人数的两倍
                    dp[j] = max(dp[j], dp[j - (2 * b[k] + 1)] + k * i);
    }

    cout << dp[m] << '\n';

    return 0;
}

E. 琪露诺的小球猜猜游戏

题目描述

有 $n$ 个杯子排成一行，其中有一些杯子底下藏有小球，可以花费 $c_{i, j}$ 的代价知道区间 $[l, r]$ 内小球总数的奇偶性。求出准确知道每个杯子下是否有小球的最小花费。「YAC Round 6」琪露诺的小球猜猜游戏

解题思路 最小生成树

准确知道每个杯子下是否有小球，相当于我们需要知道每个杯子里小球个数的奇偶性。杯子下有小球，则为奇；杯子下无小球，则为偶。

我们可以发现，当知道了区间 $[l, r_1]$ 和区间 $[l, r_2]$ 的奇偶性后，我们可以推导出区间 $[r_1 + 1, r_2]$ 的奇偶性。所以，考虑将 $n$ 个杯子看作是 $n$ 个点，将知道区间 $[l, r]$ 内小球数量的奇偶性看作是点 $l$ 到 点 $r$ 连边。那么，图中存在边 $(l, r_1)$ 和 $(l, r_2)$，相当于有边 $(r_1 + 1, r_2)$。

可是，如果按照上述模型去建图，并不能很好的构造出连通性，因此我们可以稍稍地改变一下建边方式。

我们可以将知道区间 $[l, r]$ 内小球个数的奇偶性看作是从 $l - 1$ 到 $r$ 连边。那么，图中存在边 $(l, r_1)$ 和 $(l, r_2)$（知道了区间 $[l + 1, r_1]$ 和 $[l + 1, r_2]$ 的奇偶性），相当于有边 $(r_1, r_2)$（知道了区间 $[r_1 + 1, r_2]$ 的奇偶性，$r_1$ 到 $r_2$ 通过两条边连通）。这样就可以就顺畅很多。

我们再重新聚焦一下我们的最终目的，即知道每个杯子里小球个数的奇偶性，那么其实就是知道所有的 $[i, i]$ 的奇偶性。也就是说，我们要使得所有的 $i - 1$ 到 $i$ 连通，其实就是让整个图连通（注意此时的图多了一个 $0$ 点，共 $n + 1$ 个点）。

按照更改后的方式去建图，对每个给出的区间 $[l, r]$ 构建一个 $l - 1$ 到 $r$ 的权值为 $c_{l, r}$ 的边。为了使得整个图连通，并且花费最小，这显然只需要我们求一下所建图的最小生成树即可。

本题解采用 $\text{kruskal}$ 求解最小生成树，相对简单。也可以使用 $\text{prim}$。

#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 = 2010, M = N * N;

int n, m, fa[N];
ll res;
struct node{int u, v, w;}e[M];

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

void kruskal(){
    for(int i = 1; i <= n; i ++ ) fa[i] = i;
    sort(e + 1, e + m + 1, [](node &a, node &b){
        return a.w < b.w;
    });
    for(int i = 1; i <= m; i ++ ){
        int fx = find(e[i].u), fy = find(e[i].v);
        if(fx == fy) continue;
        fa[fy] = fx;
        res += e[i].w;
    }
}

int main(){
    ios;

    cin >> n;
    for(int l = 1; l <= n; l ++ )
        for(int r = l; r <= n; r ++ ){
            int x; cin >> x;
            e[ ++ m] = node{l - 1, r, x};
        }

    kruskal();

    cout << res << '\n';

    return 0;
}

F. 琪露诺的妖精舞踏会

题目描述

给定很多对相互跳过舞的男女，要求选择的人中的任何一对男女都是互相没有跳过舞的。求最多可以邀请多少人。「YAC Round 6」琪露诺的妖精舞踏会

解法一 二分图染色 + 匈牙利算法 + 最大独立集

我们可以将问题构建为是一个二分图。我们可以把男生看作是左部节点，将女生看作是右部节点，男生 $u$ 和女生 $v$ 之间跳过舞看作是左部点 $u$ 和右部点 $v$ 存在一条边。而我们要求得一个点集，点集中所有点互相之间不能存在关系。这个时候我们需要引入一个定义，也就是二分图的最大独立集：一个最大的点的集合，该集合内的任意两点没有边相连。

二分图的最大独立集有一个定理，就是：$最大独立集 = n - 最大匹配$，其中 $n$ 表示图中节点个数。（最大独立集 OI Wiki）

因此，我们的问题就转换为求解二分图的最大匹配，最大匹配比较传统的方法就是 匈牙利算法， 最后用节点数量 $n$ 减去这个最大匹配即为答案。

但是，题目所给的关系并没有明确给出每个点是男生还是女生，故我们需要建图之后，对二分图进行染色，染色后颜色为 $1$ 的我们可以认为是左部点，颜色为 $2$ 认为是右部点。

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

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

int n, m;
int h[N], e[M], ne[M], idx;
int col[N], match[N];
bool st[N];

void add(int a, int b){
    e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}
// 染色
void get_col(int u, int c){
    col[u] = c;
    for(int i = h[u]; i; i = ne[i]){
        int v = e[i];
        if(col[v]) continue;
        get_col(v, 3 - c);
    }
}
// 匈牙利算法
bool find(int u){
    for(int i = h[u]; i; i = ne[i]){
        int v = e[i];
        if(!st[v]){
            st[v] = true;
            if(!match[v] || find(match[v])){
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main(){
    ios;

    cin >> n >> m;
    while(m -- ){
        int u, v; cin >> u >> v;
        u ++ , v ++ ;
        add(u, v), add(v, u);
    }

    for(int i = 1; i <= n; i ++ ) if(!col[i]) get_col(i, 1);

    int res = 0;
    for(int i = 1; i <= n; i ++ ){
        if(col[i] != 1) continue;
        memset(st, 0, sizeof st);
        res += find(i);
    }

    cout << n - res << '\n';

    return 0;
}

解法二 二分图染色 + 最大流 + 最大独立集

求二分图最大匹配也将二分图转换为最大流模型，所求最大流就是二分图最大匹配。（最大流算法较难，感兴趣的同学可以多了解了解）

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

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

const int inf = 0x3f3f3f3f;
const int N = 1010, M = N * N;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int src, des, res; // 源点 汇点 最大流
int now[M], d[N];  // 当前弧， 点的层次
int col[N];
int g[N][N];       // 预先存储关系


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

void get_col(int u, int c){
    col[u] = c;
    for(int v = 1; v <= n; v ++ ){
        if(!g[u][v] || col[v]) continue;
        get_col(v, 3 - c);
    }
}

bool bfs(){
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(src), d[src] = 0;
    now[src] = h[src];

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i], c = w[i];
            if(!c || ~d[v]) continue;

            q.push(v), d[v] = d[u] + c;
            now[v] = h[v];

            if(v == des) return true;
        }
    }

    return false;
}

int dfs(int u, int flow){
    if(u == des) return flow;
    int used = 0;
    for(int i = now[u]; ~i && used < flow; i = ne[i]){
        now[u] = i;
        int v = e[i], c = w[i];
        if(c && d[v] == d[u] + c){
            int f = dfs(v, min(c, flow - used));
            w[i] -= f, w[i ^ 1] += f;
            used += f;
        }
    }
    return used;
}

void dinic(){ // 最大流
    while(bfs()) res += dfs(src, inf);
}

int main(){
    ios;

    memset(h, -1, sizeof h);
    cin >> n >> m;

    src = 0, des = n + 1; // 源点 汇点
    while(m -- ){
        int u, v; cin >> u >> v;
        u ++ , v ++ ;
        g[u][v] = g[v][u] = 1;
    }

    for(int i = 1; i <= n; i ++ ) if(!col[i]) get_col(i, 1);

    for(int i = 1; i <= n; i ++ ){
        if(col[i] == 1) add(src, i, 1); // 源点连向左部点
        else add(i, des, 1);  // 右部点连向汇点
    }

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            if(col[i] == 1 && col[j] == 2 && g[i][j]) add(i, j, 1);

    dinic();

    cout << n - res << endl;

    return 0;
}