Codeforces Round #734 (Div. 3) 题解

Hello大家好，今天给大家带来的是 Codeforces Round #734 (Div. 3) 的全题目讲解。

本文链接：https://www.lanqiao.cn/questions/204012

感谢蓝桥云课的 Lqyk 同学提供的题解。

A. Polycarp and Coins

题目链接

https://codeforces.com/contest/1551/problem/A

题目大意

有一个人买东西付钱只用一元钱和二元钱，现在他要付 (n) 元，他使用一元钱的数量和二元钱数量的差值要最小，问他付 (n) 元使用了多少一元钱和二元钱？

解题思路

差值最小的话一元钱和二元钱的数量比例要接近 (1 : 1) ，那么总共三元钱，那么每份都使用的 (n / 3) ,最后只要判断一下剩下的钱是(0, 1, 2) 元的情况即可。

AC_Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        ll a = n / 3;
        ll b = n / 3;
        if(n % 3 == 2) b++;
        else if(n % 3 == 1) a++;
        cout << a << " " << b << endl;
    }
    return 0;
}

B1. Wonderful Coloring - 1

题目链接

https://codeforces.com/contest/1551/problem/B1

题目大意

(n) 个字符要么染成红绿俩种颜色，要么不染色。

相同颜色的字符俩俩不同。

红绿俩种颜色的字符数量相同。

满足以上三个条件，每种颜色被染色的字符数量是多少？

解题思路

相同的字符每种颜色最多染一个，因此只要对出现次数 $ geq 2$ 的字符和出现一次的字符分别讨论就行。

出现次数 $ geq 2$ 的字符, 每种颜色都能分到一个，答案加上这些字符的种类数。

出现一次的，红一个，绿一个，答案加上这些字符种类数除以二（向下取整）。

AC_Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        map<char, int> mp;
        int ans = 0;
        for(int i = 0;i < s.size();i++) mp[s[i]]++;
        int cnt = 0;
        for(auto i : mp){
            if(i.second >= 2) ans++;
            else cnt++;
        }
        cout << ans + cnt / 2 << endl;
    }
    return 0;
}

B2. Wonderful Coloring - 2

题目链接

https://codeforces.com/contest/1551/problem/B2

题目大意

(n) 个数字，染成 (k) 种颜色，要么不染色。

相同颜色的数字的值是俩俩不同的。

所有的 (k) 种颜色的数字数量应该相同。

染色的数字的数量要最多。

用 (0 - k) 表示染色的颜色种类 ((0) 表示不染色) ，求满足上述条件的染色方案。

解题思路

和 (B1) 一样的思路，考虑将出现次数$ geq k$ 的数字和出现次数 (< k) 的分开讨论。

出现次数 $ geq k$ 的字符, 每种颜色都能分到一个, 所以把位置存储下来直接染色即可。

出现次数 (< k) 的集中到一起，为了防止相同的数字染成同一种颜色，所以先排序在按顺序对下标染色。

AC_Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
struct node{
    int id, val;
    bool operator < (const node &p) const{
        return val < p.val;
    }
};
vector<int> num[maxn]; //统计某种数字出现的次数
vector<node> q; //集中<k的数字
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<int> ans(n + 1, 0), vis(n + 1, 0), a(n + 1);
        for(int i = 1;i <= n;i++) num[i].clear(); q.clear();
        for(int i = 1;i <= n;i++){
            cin >> a[i];
            num[a[i]].push_back(i);
        }
        for(int i = 1;i <= n;i++){
            if(num[i].size() >= k){
                for(int j = 0;j < num[i].size();j++){
                    ans[num[i][j]] = j + 1;
                }
                vis[i] = 1;//标记是否>=k
            }
        }
        for(int i = 1;i <= n;i++){
            if(!vis[a[i]]){
                q.push_back({i, a[i]});
            }
        }
        sort(q.begin(), q.end());
        int sum = q.size() / k * k, v = 1;//取整，从1开始染色
        for(int i = 0;i < sum;i++){
            ans[q[i].id] = v++;
            if(v == k + 1) v = 1;
        }
        for(int i = 1;i <= n;i++){
            if(ans[i] > k) cout << 0 << " ";//大于K都是多的，都不染色
            else cout << ans[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

C. Interesting Story

题目链接

https://codeforces.com/contest/1551/problem/C

题目大意

从 (n) 个只包含 (a、b、c、d、e) 的字符串中选择若干个，使得某一个单一字符的出现次数大于其余四个总和，问最多可以选多少个字符串。

解题思路

我们可以记录每个字符串 (a、b、c、d、e) 出现的次数，然后枚举 (a、b、c、d、e) 分别作为大于其他四个字符总和的情况。

假设当前枚举 (a) 第 (i) 个字符串 (a) 出现的次数为 (sum), 其余四个总和为 (now) ,那么他们的差值 (sum - now) 为正的时候是可以选的，为了选择更多，我们贪心的将 (sum - now) 的值从大到小排序，不断加入字符串, 保持总和 $geq 0 $即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;
int a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];
int n;
int get_a(){
    vector<ll> ans;
    for(int i = 0;i < n;i++){
        ll sum = a[i];
        ll now = b[i] + c[i] + d[i] + e[i];
        ans.push_back(sum - now);
    }
    sort(ans.rbegin(), ans.rend());
    ll k = 0;
    int cnt = 0;
    for(int i = 0;i < n;i++){
        if(k + ans[i] > 0LL) {
            cnt++;
            k += ans[i];
        }
        else break;
    }
    return cnt;
}
int get_b(){
    vector<ll> ans;
    for(int i = 0;i < n;i++){
        ll sum = b[i];
        ll now = a[i] + c[i] + d[i] + e[i];
        ans.push_back(sum - now);
    }
    sort(ans.rbegin(), ans.rend());
    ll k = 0;
    int cnt = 0;
    for(int i = 0;i < n;i++){
        if(k + ans[i] > 0LL) {
            cnt++;
            k += ans[i];
        }
        else break;
    }
    return cnt;
}
int get_c(){
    vector<ll> ans;
    for(int i = 0;i < n;i++){
        ll sum = c[i];
        ll now = a[i] + b[i] + d[i] + e[i];
        ans.push_back(sum - now);
    }
    sort(ans.rbegin(), ans.rend());
    ll k = 0;
    int cnt = 0;
    for(int i = 0;i < n;i++){
        if(k + ans[i] > 0LL) {
            cnt++;
            k += ans[i];
        }
        else break;
    }
    return cnt;
}
int get_d(){
    vector<ll> ans;
    for(int i = 0;i < n;i++){
        ll sum = d[i];
        ll now = a[i] + b[i] + c[i] + e[i];
        ans.push_back(sum - now);
    }
    sort(ans.rbegin(), ans.rend());
    ll k = 0;
    int cnt = 0;
    for(int i = 0;i < n;i++){
        if(k + ans[i] > 0LL) {
            cnt++;
            k += ans[i];
        }
        else break;
    }
    return cnt;
}
int get_e(){
    vector<ll> ans;
    for(int i = 0;i < n;i++){
        ll sum = e[i];
        ll now = a[i] + b[i] + c[i] + d[i];
        ans.push_back(sum - now);
    }
    sort(ans.rbegin(), ans.rend());
    ll k = 0;
    int cnt = 0;
    for(int i = 0;i < n;i++){
        if(k + ans[i] > 0LL) {
            cnt++;
            k += ans[i];
        }
        else break;
    }
    return cnt;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0;i <= n;i++) a[i] = b[i] = c[i] = d[i]= e[i] = 0;
        for(int i = 0;i < n;i++){
            string s;
            cin >> s;
            for(int j = 0; j < s.size();j++){
                if(s[j] == 'a') a[i]++;
                else if(s[j] == 'b') b[i]++;
                else if(s[j] == 'c') c[i]++;
                else if(s[j] == 'd') d[i]++;
                else if(s[j] == 'e') e[i]++;
            }
        }
        int ans = 0;
        ans = max(ans, get_a());
        ans = max(ans, get_b());
        ans = max(ans, get_c());
        ans = max(ans, get_d());
        ans = max(ans, get_e());
        cout << ans << endl;
    }
    return 0;
}

D1. Domino (easy version)

题目链接

https://codeforces.com/contest/1551/problem/D1

题目大意

在 $n * m $ 的网格图放 (1 imes2) (横着)或者 (2 imes1)（竖着）的多米若骨牌，在 (n * m) 为偶数的情况下，是否能恰好放 (k) 个横着的多米洛骨牌。

解题思路

考虑为什么题意给的是 (n*m) 都是偶数，而不是 (n、m) 都是偶数。

当 (n、m) 都为偶数的时候， (2 imes2) 的方格可以任意放 $2 $ 个 (1 imes2) 横着的或者 (2 imes 1)竖着的，并且它们都是偶数成对出现的，因此我们就可以分割图面为若干个 (2 imes2)的网格，此时 (k) 为偶数才能满足条件。

假设若 (n) 为奇数，画图不难发现必定要放 (m/2) 个横着的，同理，若 (m) 为奇数，必定要放(n / 2) 个竖着的，多出来的行列铺满横的或者竖的后就转化偶数情况。

因此只要判断总得减去必定放的是否放得下 (k)个并且 (k) 要大于必定放横的数量。

AC_Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        int n, m, k;
        cin >> n >> m >> k;
        int tot = n * m / 2;
        if(n % 2){
            k -= m / 2;
            tot -= m / 2;
        }
        if(m % 2) tot -= n / 2;
        if(k < 0 || k % 2 || k > tot){
            cout << "NO
";
            continue;
        }
        cout << "YES
";
    }
    return 0;
}

D2. Domino (hard version)

题目链接

https://codeforces.com/contest/1551/problem/D2

题目大意

在 $n imes m $ 的网格图放 (1 imes2) (横着)或者 (2 imes1)（竖着）的多米若骨牌，在 (n imes m) 为偶数的情况下，是否能恰好放 (k) 个横着的多米洛骨牌,用字符输出摆放图案。

解题思路

(D1) 的思路能讨论出来后，就按照讨论分别构造即可。

首先先判断有没有奇数的行、列，从 (a - z) 任意找俩个个字符填充完。

然后将这多的行列暂时删去，当成 $n,m $ 都为偶数填充。

先填充 (k) 个横着的，剩下的 (2 imes2) 填充竖着的即可，唯一的问题就是相邻的字符会重复的问题，我们可以根据下标的奇偶关系来交替填充不同字符，当然字符从(a - z) 自己挑。

AC_Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200;
char ans[maxn][maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        int n, m, k;
        cin >> n >> m >> k;
        int tot = n * m / 2;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                ans[i][j] = '#';
            }
        }
        int nn = n, mm = m;
        if(n % 2){
            k -= m / 2;
            tot -= m / 2;
            int cnt = 1;
            for(int j = 1;j <= m;j += 2){//最后一行放满横的
                if(cnt % 2) ans[n][j] = ans[n][j + 1] = 'o';
                else ans[n][j] = ans[n][j + 1] = 'p';
                cnt++;
            }
            n--;
        }
        if(m % 2){
            tot -= n / 2;
            int cnt = 1;
            for(int i = 1;i <= n;i += 2){
                if(cnt % 2) ans[i][m] = ans[i + 1][m] = 'x';
                else ans[i][m] = ans[i + 1][m] = 'y';
                cnt++;
            }
            m--;
        }
        if(k < 0 || k % 2 || k > tot){
            cout << "NO
";
            continue;
        }
        int cnt = 1;
        for(int j = 1;j <= m;j += 2){
            cnt ++;
            for(int i = 1;i <= n;i++){
                if(k != 0){
                    if((i + cnt) & 1) ans[i][j] = ans[i][j + 1] = 'a';
                    else ans[i][j] = ans[i][j + 1] = 'b';
                    k--;
                }
                if(!k) break;
            }
            if(!k) break;
        }
        for(int i = 1;i <= n;i += 2){
            cnt++;
            for(int j = 1;j <= m;j++){
                if(ans[i][j] == '#'){
                    if((j + cnt) & 1) ans[i][j] = ans[i + 1][j] = 'k';
                    else ans[i][j] = ans[i + 1][j] = 'v';
                }
            }
        }
        cout << "YES
";
        for(int i = 1;i <= nn;i++){
            for(int j = 1;j <= mm;j++){
                cout << ans[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}

E. Fixed Points

题目链接

https://codeforces.com/contest/1551/problem/E

题目大意

给定一个长度为 (n) 的数组 (a) 和一个常数 (k)。

现有一种操作，操作内容为选择数组 (a) 中任意一个数 (a_i) 并删除它，删除之后 (a_i) 右边的数将全部向右移动一位，即 (a_{i-1},a_i，a_{i+1},a_{i+2},...,a_n ightarrow a_{i-1},a_{i+1},a_{i+2},a_{i+3},...,a_{n})。

定义 (b_1,b_2,...,b_m) 为 (a) 进行若干次操作后的数组，问最少要进行多少次操作，可以使得 (b_i=i) 的个数大于等于 (k)。

解题思路

因为本题的数据范围不大 (1leq kleq nleq 2 imes10^3)，所以不难想到用 (dp) 来解决。

定义 (f_{i,j}) 表示数组 (a) 的前 (i) 个数，删除了(j) 个后， (b_h=h(1leq hleq i)) 的最大个数。

于是当前的这个数 (a_i)，有两种决策：

删除 (a_i)：删除 (a_i) 后 (a_i) 就带来任何贡献，即 (f_{i,j} = f_{i-1,j-1})。

不删除 (a_i)：此时已经删除了 (j) 个数，那么 (a_i) 的位置为 (i-j)，所以 (f_{i,j} = f_{i-1,j} + [a_i == i-j])

最后从小到大枚举删除的个数 (j)，若 (f_{n,j} geq k)，则该 (j) 为答案。

AC_Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int n , k , a[N], f[N][N];
signed main()
{
    int T = 1;
    cin >> T;
    while(T --)
    {
        cin >> n >> k;
        memset(f , 0 , sizeof(int) * n * n);
        for(int i = 1 ; i <= n ; i ++) cin >> a[i];
        for(int i = 1 ; i <= n ; i ++)
        {
            for(int j = 0 ; j <= i ; j ++)
            {
                if(!j) f[i][j] = f[i - 1][j] + (a[i] == i - j);
                else f[i][j] = max(f[i - 1][j - 1], f[i - 1][j] + (a[i] == i - j));
            }
        }
        bool flag = 0;
        for(int j = 0 ; j <= n ; j ++) if(f[n][j] >= k)
        {
            cout << j << '
';
            flag = 1;
            break ;
        }
        if(!flag) cout << -1 << '
';
    }
    return 0;
}

F. Equidistant Vertices

题目链接

https://codeforces.com/contest/1551/problem/F

题目大意

给定一个包含 (n) 个节点的树和一个常数 (K)，要求你树中选择 (K) 个节点并放入集合，使得集合内任意两点之间的距离都相等，问有多少种不同的选择方法。

解题思路

当 (K = 2) 时，无论怎么选取，集合内都只存在一种距离，满足条件，所以答案为 (C_{n}^{2})。

当 (K > 2) 时，则必然存在一个点 (u)，使得集合内的点分别位于 (u) 的不同分支上，且到 (u) 的距离相等（证明略），我们定义这样的 (u) 为集合的中心

我们以 (u) 作为集合的中心，枚举集合内的点到 (u) 的距离，设当前枚举的距离为 (d)。

那么在以 (u) 为根的树里，如果超过 (K) 个分支中存在与 (u) 的距离大于等于 (d) 的节点，则我们可以选择从这些分支中挑选 (K) 个作为方案。定义这些分支为有效分支，并有效分支的个数为 (cnt)，那么能带来的方案数为 (C_{cnt}^{K})？不对，因为某些有效分支中可能不仅仅存在一个与 (u) 距离大于等于 (d) 的节点，它们所能带来的方案数不能被忽略，也不好直接计算，于是考虑 (dp)！

我们先定义 (f[u][j]) 表示在以 (v) 为根的子树中，与 (v) 距离为 (j) 的节点的个数，那么：

当 (v) 为 (u) 儿子节点时，(f[u][j] = f[v,j-1])

当 (v) 为 (u) 父亲节点时：

(f[u][j] += f[v][j-1] ,(j=1))

(f[u][j] += f[v][j - 1] - f[u][j - 2] (jgeq2))

我们再定义 (dp[u][j][k]) 表示以 (u) 为根，从 (u) 的前 (j) 个有效分支中，选择 (k) 个有效分支的方案数，那么对于第 (j) 个有效分支（设为 (v)），有以下两种决策：

选择第 (j) 个有效分支：(dp[u][j][k] = dp[u][j - 1][k - 1] imes C_{f[v][d-1]}^{1} = dp[u][j - 1][k - 1] imes f[v][d-1]).

(f[v][d-1]) 表示 (v) 的子树中与 (v) 距离大于 (d-1) 的节点个数，即与 (u) 距离大于等于 (d) 的节点个数
(C_{f[v][d]}^1) 表示从这些节点中任意挑选一个

不选择第 (j) 个有效分支：(dp[u][j][k] = dp[u][j - 1][k])

对于每次枚举的距离 (d) ，(u) 对答案的贡献为 (dp[u][cnt][K])

AC_Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, mod = 1e9 + 7;
struct Edge
{
    int nex, to;
} edge[N << 1];
int head[N] , TOT;
int n , K , f[N][N];
long long res , dp[N][N][N];
void add_edge(int u, int v)
{
    edge[++ TOT].nex = head[u];
    edge[TOT].to = v;
    head[u] = TOT;
}
void init()
{
    for(int i = 0 ; i <= n + 1 ; i ++) head[i] = 0;
    TOT = 0;
}
void dfs(int u, int far)
{
    for(int i = head[u] ; i ; i = edge[i].nex)
    {
        int v = edge[i].to;
        if(v == far) continue ;
        dfs(v, u);
        for(int j = 1 ; j <= n ; j ++) f[u][j] += f[v][j - 1];
    }
    f[u][0] = 1;
}
void dfs1(int u , int far)
{
    memset(dp , 0 , sizeof(int) * n * n * n);
    for(int j = 1 ; j <= n ; j ++)
    {
        dp[u][0][0] = 1;
        int cnt = 0;
        for(int i = head[u] ; i ; i = edge[i].nex)
        {
            int v = edge[i].to;
            if(v == far)
            {
                if(j == 1)
                {
                    dp[u][++ cnt][0] = 1;
                    for(int k = cnt ; k >= 1 ; k --) dp[u][cnt][k] = (dp[u][cnt - 1][k] + dp[u][cnt - 1][k - 1]) % mod;
                }
                else
                {
                    if(f[far][j - 1] - f[u][j - 2] > 0)
                    {
                        dp[u][++ cnt][0] = 1;
                        for(int k = cnt ; k >= 1 ; k --) dp[u][cnt][k] = (dp[u][cnt - 1][k] + dp[u][cnt - 1][k - 1] * (f[far][j - 1] - f[u][j - 2]) % mod) % mod;
                    }
                }
            }
            else
            {
                if(f[v][j - 1])
                {
                    dp[u][++ cnt][0] = 1;
                    for(int k = cnt ; k >= 1 ; k --) dp[u][cnt][k] = (dp[u][cnt - 1][k] + dp[u][cnt - 1][k - 1] * f[v][j - 1] % mod) % mod;
                }
            }
        }
        res += dp[u][cnt][K] , res %= mod;
    }
    if(u != 1)
    {
        for(int j = n ; j >= 1 ; j --)
        {
            if(j == 1) f[u][j] += f[far][0];
            else f[u][j] += (f[far][j - 1] - f[u][j - 2]);
        }
    }
    for(int i = head[u] ; i ; i = edge[i].nex)
    {
        int v = edge[i].to;
        if(v == far) continue ;
        dfs1(v, u);
    }
}
signed main()
{
    int T = 1;
    cin >> T;
    while(T --)
    {
        init();
        res = 0;
        cin >> n >> K ;
        for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= n + 1; j ++) f[i][j] = 0;
        for(int i = 1 ; i < n ; i ++)
        {
            int u, v;
            cin >> u >> v;
            add_edge(u, v), add_edge(v, u);
        }
        if(K == 2)
        {
            cout << n * (n - 1) / 2 << '
';
            continue ;
        }
        dfs(1, 0) , dfs1(1, 0);
        cout << res << '
';
    }
    return 0;
}

如有编写错误或者疑惑请评论告诉我，我会第一时间回应的（如果代码在终测中挂掉了，也请评论告知我谢谢！！！）

本文作者：Lqyk

本文链接：https://www.lanqiao.cn/questions/204012