题目网址: http://codeforces.com/contest/1165/problem/C
题目大意: 给出一个串, length 是 n, 经过删除字符可得到一个子串, 且子串满足, a[1] ! = a[2],a[3] ! = a[4].......... 问最长的子串是多少? 输出删除字符的个数和子串.
题解: 直接历遍, 注意到子串的性质, 设子串长度是 k, 如果 k 是偶数, 要考虑字符相同的影响, 因为比如 x y t t d, 从左向右扫的时候, 第一个't'不能成为子串中的字符.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=2e5+7;
- char str[maxn],ans[maxn];
- int main()
- {
- int n,k;
- cin>>n;
- int tot=0;
- scanf("%s",str+1);
- for(int i=1;i<=n-1;i++) {
- if(str[i]==str[i+1]&&tot%2==0) continue;
- ans[++tot]=str[i];
- }
- ans[++tot]=str[n];
- if(tot&1) tot--;
- cout<<n-tot<<endl;
- for(int i=1;i<=tot;i++) printf("%c",ans[i]);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3063342.html