Codeforces Round 855 (Div. 3) 题解集

目录

• CF1800A Is It a Cat?
• • _Description_
  • _Solution_
  • _Code_
• CF1800B Count the Number of Pairs
• • _Description_
  • _Solution_
  • _Code_
• CF1800C1&C2 Powering the Hero
• • _Description_
  • _Solution_
  • _Code_
• CF1800D Remove Two Letters
• • _Description_
  • _Solution_
  • _Code_
• CF1800E1&E2 Unforgivable Curse
• • _Description_
  • _Solution_
  • _Code_

题目链接&比赛链接

CF1800A Is It a Cat?

洛谷链接

Description

给定一个字符串及其长度，如果满足下列条件输出 YES否则输出 NO。

• 该字符串由四部分组成
• 每部分有且仅有一种字母（不分大小写），依次为 m,e,o,w。

共 $t$ 组数据。

Solution

条件包含两部分，有且仅有这四种字母出现，并且可以分成四个字母块（每个字母块有且仅有一种字母，且字母块排列必须是给定顺序）。

详见代码。

Code

#include
using namespace std;
#define ll long long
int t;
int a[10][10];
bool vis[10];
ll read(){ll x=0,f=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
void solve(){int n,ans=0;string s;cin>>n;cin>>s;memset(a,-1,sizeof(a)); //a[1~4][0/1] 表示四种字母第一个出现的位置和最后一次出现的位置，记得初始化数组for(int i=0;i<n;i++){if(s[i]=='m'||s[i]=='M'){if(a[1][1]==-1) a[1][1]=i; //第一次出现a[1][2]=i; //只要是该字母就要更新最后出现的位置ans++; //ans记录这四种字母出现的总数}else if(s[i]=='e'||s[i]=='E'){if(a[2][1]==-1) a[2][1]=i;a[2][2]=i;ans++;}else if(s[i]=='o'||s[i]=='O'){if(a[3][1]==-1) a[3][1]=i;a[3][2]=i;ans++;}else if(s[i]=='W'||s[i]=='w'){if(a[4][1]==-1) a[4][1]=i;a[4][2]=i;ans++;}}if(a[1][1]!=0||a[2][1]!=a[1][2]+1||a[3][1]!=a[2][2]+1||a[4][1]!=a[3][2]+1||a[4][2]!=n-1||ans!=n){ //满足条件肯定是四种字母按顺序头连尾，尾连头且ans一定等于ncout<<"NO"<<endl;}else cout<<"YES"<<endl;
}
int main(){t=read();while(t--){solve();}return 0;
}

CF1800B Count the Number of Pairs

洛谷链接

Description

给定 $n$，$k$，长度为 $n$ 的字符串 $s$。

一个大写的字母和一个小写格式的该字母可以合并，合并后消失，且分值加一。

一次操作定义为将一个字母改变其大小写格式（大写转小写，小写转大写）。

求在不超过 $k$ 次操作后，该字符串的分值的最大值。

共 $t$ 组数据。

Solution

设 a 1 , a 2 a_1,a_2 a1​,a2​ 表示字母 a的大小写数量。

为了让分值最大，所以要让大小写数量之差越小，这样才能使能合并的对数越多。

一种字母最多能有 ⌊ ( a 1 + a 2 ) ÷ 2 ⌋ \lfloor(a_1+a_2)\div 2\rfloor ⌊(a1​+a2​)÷2⌋ 对大小写能合并，而达到这个数量需要 a d d = ⌊ ( a 1 + a 2 ) ÷ 2 ⌋ − min ⁡ ( a 1 , a 2 ) add=\lfloor(a_1+a_2)\div 2\rfloor-\min(a_1,a_2) add=⌊(a1​+a2​)÷2⌋−min(a1​,a2​)（操作后的对数减去原来就有的对数就是操作中改动的对数）次操作。将二十六种字母的 $add$ 加起来，与 $k$ 取较小值（这就是在不超过操作 $k$ 次能增加的对数）加上原来就有的对数（ min ⁡ ( a 1 , a 2 ) + min ⁡ ( b 1 , b 2 ) + ⋯ + min ⁡ ( z 1 , z 2 ) \min(a_1,a_2)+\min(b_1,b_2)+\dots+\min(z_1,z_2) min(a1​,a2​)+min(b1​,b2​)+⋯+min(z1​,z2​)），这就是最终答案。

Code

#include
using namespace std;
#define ll long long
int t;
int a[30],b[30];
ll read(){ll x=0,f=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
void solve(){int n=read(),k=read(),ans=0;string s;cin>>s;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=0;i<n;i++){if(s[i]<='z'&&s[i]>='a') a[s[i]-'a'+1]++;else if(s[i]>='A'&&s[i]<='Z') b[s[i]-'A'+1]++;}for(int i=1;i<=26;i++){ans+=min(a[i],b[i]);//操作前就有的分值ans+=min(abs(a[i]-b[i])/2,k);//操作后增加的分值k-=min(abs(a[i]-b[i])/2,k);//减去该字母耗费的操作数}cout<<ans<<endl;
}
int main(){t=read();while(t--){solve();}return 0;
}

CF1800C1&C2 Powering the Hero

洛谷链接(easy version)
洛谷链接(hard version)

Description

简单版和困难版的唯一区别在于 $n$ 和 $t$ 的数据范围。

桌上有 $n$ 张牌每张牌都有一个能量值 s i s_i si​，英雄牌的能量值为 $0$，加分牌的能量值为正整数。

每次从桌上的牌堆顶部拿一张牌直到无牌可拿。

• 若该牌为加分牌，你可以将其放在加分牌堆的顶部或丢弃此牌。
• 若该牌为英雄牌，那么加分牌堆堆顶的牌的能量值将赋予该英雄牌，英雄牌加入军队，且该加分牌丢弃。

问军队的总能量值的最大值。

共 $t$ 组数据。

Solution

每次取当前还在加分牌堆顶的最大值即可。

例：1187090

若所有加分牌都加入堆的话第一张英雄牌取得的是 7，而当前最大值为 8，明显在取 7时弃牌即可。

例：1187010

将所有加分牌放入堆时，第一张英雄牌的当前最大值为 8，而想要取到只可能弃 7，此时军队最大值为 15，明显不是最优。其实换个角度想，第一张英雄牌取 7，第二张英雄牌取 8，本质相同。

总结，若第 $i,j(i<j)$ 两张英雄牌（可以扩展到多张牌），$j$ 取 $i$ 前面的牌最优，就说明 $i,j$ 中没有加分牌能在前 $i-1$ 张牌中在前二大（例子中第二大为 7而 $i,j$ 中只有 1，取 $j$ 时最大为 7，实则为 8），否则说明 $i,j$ 中有更大的牌，定为 $j$ 时最大的牌（因为前 $i-1$ 的最大 8已经取走）。

所以满足取当前加分牌堆最大值的结论，即使当时那张英雄牌取不到（例子二），但后面的英雄牌仍能补上。

取最大值用大根堆维护。

时间复杂度：$O(n\log n)$，明显可以过简单版和困难版。

Code

#include
using namespace std;
#define ll long longint t;
int a[500500];
ll read(){ll x=0,f=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
void solve(){int n=read();long long ans=0;priority_queue<int> q;for(int i=1;i<=n;i++){a[i]=read();if(a[i]>0) q.push(a[i]);else if(a[i]==0) {if(q.size()>0){ans+=q.top(),q.pop();//记得弹出}}}cout<<ans<<endl;
}
int main(){t=read();while(t--){solve();}return 0;
}

CF1800D Remove Two Letters

洛谷链接

Description

给定 $n$ 和一个长度为 $n$ 的字符串 $s$。

令 s ′ s' s′ 为 $s$ 删去两个连续字符后剩余的字符串，问共有多少个不同的 s ′ s' s′。

共 $t$ 组数据。

Solution

例：aabacac

可以发现去掉第二三字母和去掉三四字母是一样的。

我们将整个字符串分成 a，aba，cac三个部分，由于只改动二三四这三个字母，所以第一三部分忽略。删二三时，第二部分变成第四个字母 a，而删三四时，第二部分变成 第二个字母 a，所以如果 s i = s i + 2 s_i=s_{i+2} si​=si+2​，那么删 $i,i+1$ 和 $i+1,i+2$ 时剩余字母相同。

枚举重复的数量，即 s i = s i + 2 s_i=s_{i+2} si​=si+2​ 的数量，再用总数量 $\left|s\right|-1$ 减去重复数量即可。

Code

#include
using namespace std;
#define ll long longint t;
int a[3005];
ll read(){ll x=0,f=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
void solve(){int n=read(),ans=0;string s;cin>>s;for(int i=2;i<n;i++){if(s[i]==s[i-2]) ans++;}cout<<n-1-ans<<endl;
}
int main(){t=read();while(t--){solve();}return 0;
}

CF1800E1&E2 Unforgivable Curse

洛谷链接(easy version)
洛谷链接(hard version)

Description

简单版和困难版的唯一区别在于 $k$ 的数据范围，简单版中，保证 $k=3$。

给定 $n$，$k$，及两个长度为 $n$ 的字符串 $a$，$b$。

问能否在通过若干次操作后使 $a$ 改为 $b$。

在一次操作中，你可以交换 a i , a j ( i < j ) a_i,a_j(iai​,aj​(i<j) 当且仅当 $\left|i-j\right|=kork+1$。

共 $T$ 组数据。

Solution

我们以 $k=3$ 来找规律。

首先当 $n\le 3$ 时，任何字母都无法操作，所以 $a$ 和 $b$ 要完全相同才可行。

$n=4$ 时 a 2 , a 3 a_2,a_3 a2​,a3​（以一为字符串开始下标）是无法移动的，而 a 1 , a 4 a_1,a_4 a1​,a4​ 可以交换。

$n=5$ 时 a 3 a_3 a3​ 无法移动，换言之其他字母也无法到 a 3 a_3 a3​。其他的位置可以任意交换：

• a 1 → a 2 a_1\rightarrow a_2 a1​→a2​：先到 a 4 a_4 a4​ 再到 a 2 a_2 a2​。
• a 1 → a 3 o r a 4 a_1\rightarrow a_3\space or\space a_4 a1​→a3​ or a4​：一步到达，其他位置同理。

$n=6$ 时，任意字母可以到达任意位置。

如果 a i → a i + j a_i\rightarrow a_{i+j} ai​→ai+j​，向右移 $4$ 步再往左移 $3$ 步，重复 $j$ 次即可，如果越界，适量减少重复次数，调整右移左移步数及顺序，显然可以到达任意位置（ a 5 a_5 a5​ 到 a 6 a_6 a6​ 的顺序为 a 5 → a 2 → a 6 a_5\rightarrow a_2\rightarrow a_6 a5​→a2​→a6​）。 a i − j a_{i-j} ai−j​ 同理。

总结规律，只要 a i a_i ai​ 可以进行操作（$i-k\ge 1$ 并且 $i+k\le n$），它就可以移到任意字母，任意字母也可以移到这个位置上。

只需判断那些不能移动的位置上更改前和更改后是否相同。

记得保证该字母在 $a$ 中出现过，记录每种字母修改前后的数量是否一致即可。

简单版和困难版皆可通过。

Code

#include
using namespace std;
#define ll long longint t;
int vis1[30],vis2[30];
ll read(){ll x=0,f=1;char ch;ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
void solve(){int n=read(),k=read();string a,b;cin>>a>>b;memset(vis1,0,sizeof(vis1));memset(vis2,0,sizeof(vis2));for(int i=0;i<n;i++){vis1[a[i]-'a'+1]++;vis2[b[i]-'a'+1]++;}for(int i=1;i<=26;i++) {if(vis1[i]!=vis2[i]){//数量不同无法实现cout<<"NO"<<endl;return ;}}for(int i=0;i<n;i++){if(i+k>=n&&i-k<0){//无法操作if(a[i]!=b[i]){cout<<"NO"<<endl;return ;}}}cout<<"YES"<<endl;
}
int main(){t=read();while(t--){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！