题目地址 https://codeforces.com/contest/2048/problem/C
题意:给定一个字符串,字符串第一个是1,其他的都是0或1。问如何从该字符串中取两段,使得两段异或最大,两段可以重叠
字符串的长度设为size
因为字符串第一个是1,所以必定有一段是 1 size
O(n)解法:
第一段连续的0的长度设为cnt,第一段连续0的最后一个0的位置设为p;
字符串默认从1开始
第一种情况:当第一段连续0的长度 >= 第一段连续1的长度,即2*cnt>=p
时
输出 1
size-p+cnt
第二种情况:当第一段连续0的长度 < 第一段连续1的长度,即 2*cnt<p
时
输出p-2*cnt+1
size-cnt
特判,没有0的时候,当然是输出1 size 和 1 1;
标签:Binary,cnt,Global,28,连续,字符串,长度,第一段,size From: https://www.cnblogs.com/Reisentyan/p/18619553