Codeforces Round #734 (Div. 3)个人题解
Codeforces Round #734 (Div. 3)个人题解
博主前言：萌新第一次写题解，还请dalao们轻点喷QAQ
比赛链接：Codeforces Round #734 (Div. 3)
A题 Polycarp and Coins
题目大意：
你有两种硬币，一种是一元的，一种是两元的，给你一个数，让你用这两种硬币来表示，并使这两种硬币数量差值最小，输出这个最小数量。
思路解析：
首先两种硬币面值之和为3，所以如果给出的面值 n 为3的整数倍，我们就可以用相同的两种硬币数量来表示，即 ans = n / 3 ，否则 n 对 3 取模，如果为 1 ，我们就可以增加一个1元面值的硬币，如果为 2 ，就可以增加一个2元面值的硬币。
AC代码：
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int main(){
int t;
cin>>t;
while(t--){
ll n;
cin>>n;
int ans=n/3;
if(n%3==0)
cout< B题 Wonderful Coloring - 1(easy)
题目大意：
我们需要给一个字符序列染色，对于每个字符元素，我们有三种选择，要么涂红色，要么涂绿色，要不什么也不涂，并且要求满足字符序列中相同字母不会被涂成同一颜色，而且涂红色的次数和绿色相等，求红色最多涂了多少。
思路解析：
我们首先可以对序列中的字符分成两类，一类是数量大于2的字符，一种是数量为1的字符，对于数量大于二的字符，我们可以让其中的两个分别涂成红色和绿色，多出来的只能选择不涂，对于数量为1的字符，我们可以把他们归为一类，并且给他们两两分组，分别涂红色绿色，如果分不完，有单个剩下的，那么剩下的这一个只能不涂，才能保证最大化红色的数量。
AC代码：
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
ll a[maxn],sum[maxn];
int main(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
memset(sum,0,sizeof sum);
int a=0,b=0;
for(int i=0;i=2)b++;
}
cout< B2题 Wonderful Coloring - 2(hard)
题目大意：
这是B1更复杂的版本，相比B1，他将红绿两种颜色拓展为k种颜色，更加不同的是，在这一个版本中，你需要输出你的涂色方案。
思路解析：
我们可以类比B1的做法，同样讲元素分成两类，一类是数目大于等于k的，一种是数目小于k的，对于数目大于等于k的，我们可以将其中的k个分别涂k种颜色，而其他多出来的，只能不涂，对于数目小于k的，我们将它们放在一起涂色，而这里为了保证相同数字涂不同颜色，我们可以对这些元素先排序，再分别给她们涂色，这样就能保证所给的条件。
AC代码：
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int a[maxn];
int sum[maxn],p[maxn],vis[maxn],ans[maxn];
struct node{
int val,rank,vis,ans;
}b[maxn];
bool cmp(node x,node y){
return x.val>t;
while(t--){
memset(sum,0,sizeof sum);
memset(vis,0,sizeof vis);
memset(p,0,sizeof p);
int n,k,maxx=0;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[a[i]]++;
}
for(int i=1;i<=n;i++){
if(sum[a[i]]>=k)vis[i]=1;
}
int now=0,tot=0;
for(int i=1;i<=n;i++){
if(vis[i]){
if(p[a[i]] C题 Interesting Story
题目大意：
一个作家有n个单词，每个单词只由 a，b，c，d，e 组成，并写一个故事。而一个有趣的故事需要满足：故事中存在一个字母的个数比其他字母个数的总和还更多，比如：bac,aaada,e 三个单词，a 出现的次数比其他 4 种单词出现次数都多，我们需要求最多的单词数量来使故事有趣。
思路解析：
我们可以直接枚举每种字符作为文章中出现最多的字符，然后对于每个单词来说我们可以把其他字符大于出现最多字符的单词叫做可删单词，然后贪心的去掉可删字符直到满足文章有趣的条件，如果都无法满足有趣条件，就输出0。（代码参考dalao代码QAQ我太菜了QAQ）
AC代码：
#include
using namespace std;
const int maxn=1e6+5;
const int L = 5;
vector balance[L];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 0; i < L; i++)
balance[i].clear();
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
int initBalance = -(int)s.length();
for (int j = 0; j < L; j++)
balance[j].push_back(initBalance);
for (auto c : s)
balance[c - 'a'].back() += 2;
}
int bestCount = 0;
int bestLetter = 0;
for (int i = 0; i < L; i++)
{
auto& b = balance[i];
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
if (b[0] <= 0) continue;
int sumBalance = b[0];
int j = 1;
for (; j < n && sumBalance > 0; j++)
sumBalance += b[j];
if (sumBalance <= 0) j--;
if (j > bestCount)
{
bestCount = j;
bestLetter = i;
}
}
cout << bestCount << endl;
}
return 0;
}
D1题 Domino (easy version)
题目大意：
我们有一个 n * m （ n * m 为偶数即 n 和 m 至少有一个偶数）的格子图，我们需要用多米诺骨牌来铺满这个图，每个骨牌占据两个格子的空间，我们放置骨牌有两种方式，一种是竖着放，一种是横着放，骨牌不可以重叠，给你横着的骨牌的数量，问你是否有方案可行，只需输出 YES 或者 NO。
思路解析：
我们可以分成三种情况考虑：1. n ，m 都为偶数 2. n为偶数，m 为奇数 3. n 为奇数，m 为偶数。然后我们考录，如果格子是一个 22 的格子图，我们可以用两个竖着的骨牌或者横着的骨牌来铺满它。基于这种防暑，我们来分别考虑三种情况：1. 可以直接转化成多个 22 正方块的叠加，我们就可以求出最多的横骨牌数量，与给定数量比较即可。 2. 因为 m 为奇数，我们把他看成情况一外加一列格子来表示，而多出的一列只能用竖着的骨牌来填满 3. 因为 n 为奇数，我们把他看成情况一外加一行格子来表示，而多出的一行只能用横着的骨牌来填满（三种情况示意图如下）计算最大横着的骨牌数量分别与给定数量比较即可。
AC代码：
#include
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
if(n%2==0){
int sum=(n/2)*(m/2);
if(k>sum*2){
cout<<"NO"<sum*2||k D2题 Domino (hard version)
题目大意：
在D1的基础上，我们需要输出骨牌铺满格子的方案。
思路解析：
在D1中，我们已经有了如何构造的方式，按D1思路构造即可。
AC代码：
#include
using namespace std;
const int maxn=1005;
char a[maxn][maxn];
int ck(int n,int m,int k){
if(n%2==0){
int sum=(n/2)*(m/2);
if(k>sum*2)return 0;
else {
if(k%2==0)return 1;
else return 0;
}
}
else {
int sum=(n/2)*(m/2)+m/2;
if(k>sum*2||k>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
if(ck(n,m,k)){
cout<<"YES"< E题 Fixed Points
题目大意：
给定一个长度为 \(n\) 的数组 \(a\) 和一个常数 \(k\)
现在有一个操作，删除 \(a\) 数组的任意一个，使得右边的数向左移动一位，即右边的所有的数的下标 \(-1\)
求最少进行多少次操作能使得最终的数组 \(b\) 中至少有 \(k\) 个数的 \(b[i] = i\)
思路解析：
数据范围为 \(1≤k≤n≤2×10^3\) ，所以我们很容易想到用 dp 来解决这个问题
状态定义：\(dp[i][j]\) 表示前 \(i\) 个数中，删除 \(j\) 个数能得到的 \(b[h] = h(1<=h<=n)\)的最大个数
对于当前的每个 \(a[i]\) 我们有两种决策：
- 删除 \(a[i]\),删除 \(a[i]\) 对其没有影响，所以可以得到转移 ：\(dp[i][j]=dp[i-1][j-1]\)
- 不删 \(a[i]\),由于 \(a[i]\) 不删，所以删掉的 \(j\) 个就是在i - 1之前删的，所以 \(a[i]\) 的下标变成了 \(i-j\) ，所以我们可以得到转移：\(dp[i][j]=dp[i-1][j]+(a[i]==i-j)\)
AC代码：
#include
using namespace std;
typedef long long ll;
const int maxn=2050;
int a[maxn];
int dp[maxn][maxn];
int main(){
int t;
cin>>t;
while (t--) {
int n,k;
cin>>n>>k;
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==0)dp[i][j]=dp[i-1][j]+(a[i]==i);
else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]);
}
}
int ans=-1;
for(int i=0;i<=n;i++){
if(dp[n][i]>=k){
ans=i;
break;
}
}
cout<