如何巧妙运用交替子序列技巧，解决Codeforces 604C长尾词问题？

本文共计533个文字，预计阅读时间需要3分钟。

pythondef find_longest_subsequence(s): # 初始化一个字典来存储每个字符出现的次数 count={} for char in s: if char in count: count[char] +=1 else: count[char]=1

# 初始化两个变量来存储最长的0-1子序列和最长的1-0子序列 max_01, max_10=0, 0

# 遍历字符计数字典 for char, cnt in count.items(): if char=='0': max_01 +=cnt else: max_10 +=cnt

# 返回最长子序列的长度 return max(max_01, max_10)

测试代码s=001100print(find_longest_subsequence(s)) # 输出应为 3

//思维可能就是找规律看谁找的快吧

原题链接：codeforces.com/problemset/problem/604/C

题意：给出一个0和1组成的字符串，可以对任意一段进行翻转，0变1，1变0。求翻转后的最长的交替子序列。

补充：交替子序列：相邻元素不同，可以不连续，但要保持原顺序。如，10011011，交替子序列为10101.

思路：无论如何翻转，对于子序列来说，最多增加一个01或10，所以结果为原来的交替子序列长度加2，再和总长n比较（有可能最长交替子序列就是其本身），取最小值。要找出最长的子序列串，只能翻转不是原来序列里的0和1，因为是0和1互变，翻转区间里原来不交替的翻转后也依然不交替，所以一次只能增加一个01或10。（大佬原话：我想要最长就只能翻转不在最长的01子序列范围内的1个0或1，构成01或10，就可以加二，构成01或10，但是不能超过字符串本来的长度，所以就是min(ct+2,n)//不得不说思路流畅，顺理成章）。

完整代码：

#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define N 100005 char s[N]; int main(){ int n,t,ct=1; scanf("%d%s",&n,&s); t=s[0]-‘0‘; for(int i=1;i<n;i++){ if((t^(s[i]-‘0‘))==1){ t=s[i]-‘0‘; ct++; } } cout<<min(ct+2,n)<<endl; return 0; }