hiho一下第164周《Ordered Binary String》题目分析

3
0

修改后的有序01串一共只有|S|+1种可能情况:

0000...000
0000...001
0000...011
   ....
0111...111
1111...111

我们可以枚举最后的有序01串,那么就可以通过逐位比较计算出需要修改的字符数目。复杂度O(|S|^2)。

如果我们通过预处理,计算出初始01串的每个前缀和后缀分别有多少个0,多少个1。那么我们就不用O(|S|)的逐位比较,可以直接根据前缀中1的数目和后缀中0的数目计算出需要修改的字符数目。这样总时间复杂度可以降为O(|S|)。

3 answer(s)

0

请问这道题都涉及哪些知识点呀?我刚学完谭浩强的C语言,字符串处理函数也不太会用,好像看不太懂。

  • 需要非常熟练的运用for、if和字符串(字符数组)。你可以先写一个程序,输入一个01串,统计它有几个0几个1。然后改成输入2个01串,统计它们之间有几个位置不同(其中一个是0,另一个是1)。最后再完成本题。

  • 对初学者很有用,非常感谢!

  • 添加评论
  • reply
2

最终总会按照某位分段,前面位0,后面为1。那么改动的次数,就是分段的那位前面的1的个数和后面的0的个数的和。统计每一位前面的1的个数个后面的0的个数,找出和的最小值,就可以了。不需要考虑这一位本身是1还是0,因为不管是0还是1都不需要改变。 比如:

               0 0 1 0 1 0 0 1 0 1 1 1 0 1
前面的1的个数: 0 0 0 1 1 2 2 2 3 3 4 5 6 6
后面的0的个数: 6 5 5 4 4 3 2 2 1 1 1 1 0 0
个数和:        6 5 5 5 5 5 4 4 4 4 5 6 6 6

最小的和为4

0

这。。。不是某场cf div2的题么

write answer 切换为英文 切换为中文


转发分享