Codeforces Round #821 (Div. 2) D1. Zero-One (Easy Version)
Codeforces div version round One Easy Zero
2023-09-11 14:14:52 时间
题意:
给定两个01串s和t,每次操作可以选择 l 和 r ,并将s[l]和s[r]取反。若r==l+1,则代价为x,否则代价为y,问你把01串从s变到t的最少的代价
思路:
贪心,考虑贡献
首先判无解的情况,当需要修改的数的个数为奇数时显然无解
若x<y,则尽可能使用相邻的取反操作,若碰到相邻的则一定使用相邻取反操作,否则只能进行代价为y的操作
若x>y,则不管相邻还是不相邻,都用y操作就足以把所有需要修改的数都修改掉(因为需要修改的数的个数一定是偶数)
注意特判需要修改的数的个数只有2个时的条件,此时再对x和2*y进行讨论
如果x>2*y,则直接使用相邻的操作即可
否则,任选一个数,做两次代价为y的操作即可
Code:
#include <bits/stdc++.h>
using namespace std;
const int mxn=3e3+10;
#define int long long
string s,t;
int n,x,y,sum=0;
int ok[mxn];
void solve(){
s.clear(),t.clear();
sum=0;
memset(ok,0,sizeof(ok));
cin>>n>>x>>y;
cin>>s>>t;
s=" "+s;t=" "+t;
for(int i=1;i<=n;i++){
if(s[i]!=t[i]) ok[i]=1,sum++;
}
if(sum%2==1){
cout<<-1<<'\n';
return;
}
if(sum==2){
if(x<2*y){
for(int i=2;i<=n;i++){
if(ok[i]&&ok[i-1]){
cout<<x<<'\n';
return;
}
}
cout<<y<<'\n';
return;
}else{
for(int i=2;i<=n;i++){
if(ok[i]&ok[i-1]){
cout<<y*2<<'\n';
return;
}
}
cout<<y<<'\n';
return;
}
}
int ans=0;
if(x<y){
for(int i=2;i<=n;i++){
if(ok[i]&&ok[i-1]){
ans+=x;
sum-=2;
ok[i]=ok[i-1]=0;
}
}
ans+=(sum/2)*y;
}else{
ans+=(sum/2)*y;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--)solve();
return 0;
}
相关文章
- codeforces C. Diverse Permutation(构造)
- 【Codeforces Round #695 (Div. 2) B】Hills And Valleys
- 【Educational Codeforces Round 88 (Rated for Div. 2) E】Modular Stability
- 【Codeforces Round #493 (Div. 2) B】Cutting
- 【Codeforces Round #499 (Div. 1) B】Rocket
- 【Codeforces Round #476 (Div. 2) [Thanks, Telegram!] B】Battleship
- 【Codeforces Round #460 (Div. 2) C】 Seat Arrangements
- 【Codeforces Round #447 (Div. 2) B】Ralph And His Magic Field
- 【Codeforces Round #299 (Div. 2) E】Tavas and Pashmaks
- 【15.93%】【codeforces 672D】Robin Hood
- 【codeforces 701C】They Are Everywhere
- 【codeforces 768D】Jon and Orbs
- 【Codeforces Beta Round #45 D】Permutations
- 【codeforces 794A】Bank Robbery
- Codeforces Round #FF (Div. 1)-A,B,C
- Codeforces Round #250 (Div. 2)—A. The Child and Homework
- Codeforces Round #277.5 (Div. 2)部分题解
- Codeforces Beta Round #25 (Div. 2)--A. IQ test
- Educational Codeforces Round 40 (Rated for Div. 2)
- Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)
- Educational Codeforces Round 33 (Rated for Div. 2)
- Educational Codeforces Round 31
- Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017)
- Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals)