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 个字符要么染成红绿俩种颜色，要么不染色。
相同颜色的字符俩俩不同。
红绿俩种颜色的字符数量相同。

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

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

出现次数 ≥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 一样的思路，考虑将出现次数 ≥k 的数字和出现次数 <k 的分开讨论。

出现次数 ≥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 的值从大到小排序，不断加入字符串, 保持总和 ≥0 即可。

#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×2 (横着)或者 2×1（竖着）的多米若骨牌，在 n * m 为偶数的情况下，是否能恰好放 k 个横着的多米洛骨牌。

考虑为什么题意给的是 n*m 都是偶数，而不是 n、m 都是偶数。
当 n、m 都为偶数的时候， 2×2 的方格可以任意放 2 个 1×2 横着的或者 2×1 竖着的，并且它们都是偶数成对出现的，因此我们就可以分割图面为若干个 2×2的网格，此时 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\n";
            continue;
        }
        cout << "YES\n";
    }
    return 0;
}

D2. Domino (hard version)

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

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

D1 的思路能讨论出来后，就按照讨论分别构造即可。
首先先判断有没有奇数的行、列，从 a - z 任意找俩个个字符填充完。
然后将这多的行列暂时删去，当成 n,m 都为偶数填充。
先填充 k 个横着的，剩下的 2×2 填充竖着的即可，唯一的问题就是相邻的字符会重复的问题，我们可以根据下标的奇偶关系来交替填充不同字符，当然字符从 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\n";
            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\n";
        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\rightarrow 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。

因为本题的数据范围不大 $1\leq k\leq n\leq 2\times10^3$ ，所以不难想到用 dp 来解决。
定义 $f_{i,j}$ 表示数组 a 的前 i 个数，删除了j 个后， $b_h=h(1\leq h\leq 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 << '\n';
            flag = 1;
            break ;
        }
        if(!flag) cout << -1 << '\n';
    }
    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] (j\geq2)$

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

选择第 j 个有效分支： $dp[u][j][k] = dp[u][j - 1][k - 1] \times C_{f[v][d-1]}^{1} = dp[u][j - 1][k - 1] \times 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 ，uu 对答案的贡献为 $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 << '\n';
            continue ;
        }
        dfs(1, 0) , dfs1(1, 0);
        cout << res << '\n';
    }
    return 0;
}

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

本文作者：Lqyk

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

Codeforces Round #734 (Div. 3) 题解

Codeforces Round #734 (Div. 3) 题解

A. Polycarp and Coins

AC_Code

B1. Wonderful Coloring - 1

AC_Code

B2. Wonderful Coloring - 2

AC_Code

C. Interesting Story

D1. Domino (easy version)

AC_Code

D2. Domino (hard version)

AC_Code

E. Fixed Points

AC_Code

F. Equidistant Vertices

AC_Code

Recommend

This week’s top stories: iOS 14.7 release, iPad mini and Apple external display...

Hands-on: How Apple’s new iPhone 12 MagSafe Battery Pack compares to Anker’s for...

美国经济见顶了吗？

涨停股复盘丨震荡市，这个指标很好用（短线）

iOS 优化 - 瘦身

Mini/Micro LED | 第二届全球显示领袖峰会将举办

Linux内核TCP网络连接关联进程

Edge Wealth Management

投资虚拟币花了二十多万后平台打不开了

Gurman: iPhone 13 event likely to be virtual as Apple delays return to in-person...

About Joyk