开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Codeforces Round #734 (Div. 3) 题解 -> 正文阅读

[数据结构与算法]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$ 表示不染色) ，求满足上述条件的染色方案。

解题思路

和 $B 1$ 一样的思路，考虑将出现次数$ \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$ 出现的次数为 $s u m$ , 其余四个总和为 $n o w$ ,那么他们的差值 $s u m ? n o w$ 为正的时候是可以选的，为了选择更多，我们贪心的将 $s u m ? n o w$ 的值从大到小排序，不断加入字符串, 保持总和 $\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\times2$ (横着)或者 $2\times1$ （竖着）的多米若骨牌，在 $n ? m$ 为偶数的情况下，是否能恰好放 $k$ 个横着的多米洛骨牌。

解题思路

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

当 $n 、 m$ ? 都为偶数的时候， $2\times2$ ? 的方格可以任意放 $2 $ 个 $1\times2$ 横着的或者 $\times 1$ ?竖着的，并且它们都是偶数成对出现的，因此我们就可以分割图面为若干个 $2\times2$ 的网格，此时 $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 \times m $ 的网格图放 $1\times2$ (横着)或者 $2\times1$ （竖着）的多米若骨牌，在 $\times m$ 为偶数的情况下，是否能恰好放 $k$ 个横着的多米洛骨牌,用字符输出摆放图案。

解题思路

$D 1$ 的思路能讨论出来后，就按照讨论分别构造即可。

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

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

先填充 $k$ ? 个横着的，剩下的 $2\times2$ 填充竖着的即可，唯一的问题就是相邻的字符会重复的问题，我们可以根据下标的奇偶关系来交替填充不同?字符，当然字符从 $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$ ，所以不难想到用 $d p$ 来解决。

定义 $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$ 个作为方案。定义这些分支为有效分支，并有效分支的个数为 $c n t$ ，那么能带来的方案数为 $C_{cnt}^{K}$ ？不对，因为某些有效分支中可能不仅仅存在一个与 $u$ 距离大于等于 $d$ 的节点，它们所能带来的方案数不能被忽略，也不好直接计算，于是考虑 $d p$ ！

我们先定义 $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)$

$(j\geq2)$

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

选择第 $j$ 个有效分支： $\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$ 个有效分支： $d p [u] [j] [k] = d p [u] [j ? 1] [k]$

对于每次枚举的距离 $d$ ， $u$ 对答案的贡献为 $d p [u] [c n t] [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;
}