首页 > 其他分享 >题解:CF997A Convert to Ones

题解:CF997A Convert to Ones

时间:2024-08-20 17:57:20浏览次数:11  
标签:Convert 花费 题解 取反 long 一个 Ones 字符串 操作

题意

给定一个长度为 \(n\) 的01字符串,有以下两种操作:

  1. 将一个子串翻转,花费 \(X\)
  2. 将一个子串进行取反,花费 \(Y\)

求把原字符串变为全是 \(1\) 的字符串的最小代价。

思路

只有 \(2\) 操作的情况下

贪心策略。考虑到任意范围取反的花费相同,我们可以将相同的部分合并,如下图

合并以后,会形成一个如 \(101010\dots\) 一样的字符串,每个 \(0\) 和 \(1\) 代表一个区间。此时,每个 \(0\) 代表一次操作。如果有 \(K\) 个 \(0\),那么总共花费为 \(K \times Y\)。

有 \(1\) 操作

刚刚的方法并不能保证是最小花费。
执行 \(1\) 操作,将其中的一个 \(1\) 和 \(0\) 进行翻转后,如下图

把相同的合并

就在刚刚的操作中减少了一个 \(0\),这相当于把一个 \(0\) 直接取反

所以,一个 \(1\) 操作和一个 \(2\) 操作本质上是相同的。
当然,执行到最后只剩下一个 \(0\) 时,必须使用一次 \(2\) 操作,使原字符串全部为 \(1\)。
得本题的答案为
设:原字符串中有 \(k\) 段 \(0\),\(A\) 和 \(B\) 代表操作 \(1\) 和 \(2\)

\[\min(A,B)\times(k-1)+B \]

AC code

#include<bits/stdc++.h>
using namespace std;
string s;
long long n,x,y,sum=0;
int main(){
	cin>>n>>x>>y;
	cin>>s;
	s[n]='1';
	for(int i=0;i<n;i++){
		if(s[i]=='0'&&s[i+1]=='1') sum++;
	}
	if(sum==0) cout<<0;
	else cout<<(sum-1)*min(x,y)+y;
	return 0;
}

注意

要开 long long,如果没有原字符串中没有 \(0\),则直接输出 \(0\)。

标签:Convert,花费,题解,取反,long,一个,Ones,字符串,操作
From: https://www.cnblogs.com/bubble-sort/p/18369949

相关文章

  • 题解:P10696 [SNCPC2024] 写都写了,交一发吧
    前置知识位运算按位与的运算规则:二进制下,相同位的两个数字都为\(1\),则为\(1\);若有一个不为\(1\),则为\(0\)。分析由按位与的运算规则可以得到:\(A\&A=A\),而题目中的两次提交可以是相同的,所以两次都只需要取\(n\)个数中最大的数即可。ACcode#include<bits/stdc++.h>us......
  • 题解:UVA486 English-Number Translator
    这是一道模拟题。前置知识数级思路当读取到了thousand和million时,计数器要乘上对应的值并累加到最终答案里,并且把计数器归零(因为该数级已经计算完了)。当读取到hundred时,只要计数器乘上\(100\)。否则如果是其他数,则直接累加到计数器即可。ACcode#include<bits/st......
  • 题解:P10722 [GESP202406 六级] 二叉树
    思路朴素做法当输入\(a_i\)后,直接将它及它的子树进行变换。而这样时间会超时。预计得分\(40\)pts。正解统计每次变换的节点编号,第\(i\)个节点作为根节点进行子树变换的次数为\(rec_i\)。最后从这棵树的根节点\(1\)开始向下dfs,则每个节点变换的次数为\[rec_i+k_j\]......
  • 题解:UVA12398 NumPuzz I
    题意给你一个操作顺序,每个字母代表一个格子的操作。每次操作都会将一个格子及它相邻的格子的值\(-1\),如果格子的值为\(0\),则会变成\(9\)。已知操作完成后的所有格子值都为\(0\),求最开始每个格子的值为多少。思路模拟过程。倒推出得出答案。如果原操作\(-1\),那么现操作在......
  • 题解:UVA13026 Search the Khoj
    题意&翻译输入\(T\)组数据,每行数据有\(n\)个电话号码,最后再输入一行电话号码\(t\)。输出前面与\(t\)相差不超过一个字符的电话号码。思路把前面的\(n\)个电话号码逐个与\(t\)比较即可。ACcode#include<bits/stdc++.h>usingnamespacestd;intT,n;stringm[10......
  • 题解:P8887 [DMOI-R1] 柯基棋
    本题题意小A和小B在一个\(n\timesn\)的棋盘里下柯基棋,当一个人不能再放下棋子时,他就输了。问谁会有必胜策略。思路先不考虑小C的捣乱。分类讨论当\(n\)为奇数时,不难得出:当小A第一步放在棋盘的正中心时,以后不管小B放在哪里,小A只要放在它的对称处就行了。这......
  • 题解:CF644A Parliament of Berland
    本题题意有\(n\)个议员,编号为\(1\simn\),就坐在\(a\timesb\)的礼堂里,求如何安排座位能够使得任意两个相邻的座位上的议员奇偶性不相同。思路无解情况当\(n>a\timesb\)时,必定无法满足,则直接输出-1。有解情况打表找规律。我们发现,只要让奇数行正着就坐,偶数......
  • 题解:CF1032B Personalized Cup
    本题题意给一个字符串,将其分成等长度的字符串,但是分的行数不能超过\(5\)行,每行的长度不得超过\(20\)。如果无法等分的,则用*来补足长度。输出在行数最小的前提下,列数最少的一种方案。思路由于字符串范围最多也就\(20\times5\),直接分类讨论即可。ACcode#include<bits/st......
  • 题解:P9944 [USACO21FEB] Comfortable Cows B
    思路由于每次输入\(x\)和\(y\)只改变其上下左右的值,所以每次只要更新其相邻的值即可。当某个位置相邻的奶牛数达到\(3\)时,舒适度加一。当某个位置相邻的奶牛数达到\(4\)时,舒适度减一。注意:每增加一头奶牛以后,如果该位置相邻正好有三头奶牛,则舒适度也要加一。ACcod......
  • 题解:P8690 [蓝桥杯 2019 国 B] 填空问题
    试题\(\mathrm{A}\):平方序列枚举\(x\),通过\(x^2-2019^2\)求出它们的公差\(c\),再计算\(x^2+c\)是否为完全平方数即可。code#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ for(inti=2020;1==1;i++){ intc=i*i-2019*2019; i......