CodeForce刷题表

Day11

1605C - Dominant Character

题意:

字符串有a、b、c三种字符：

  • a的绝对数量大于b
  • a的绝对数量大于c
  • 最少有两个字符
  • 可以删除字符串前面和后面任意连续的字符

问最短的满足条件的串有多长？

思路：

其实只有有限的情况：

aa aba aca abca acba abbacca accabba

只有上面的7种情况，其他的情况可能包含有上面的情况。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7; 
int main(){
	int _;cin>>_;
	while(_--) {
		string s,ss;
		int len;
		cin>>len;
		cin>>s;
		int res = -1;
		for(int i=0;i<len-6;i++) {
			ss = s.substr(i,7);
			if(ss=="abbacca"||ss=="accabba")
				res = 7;
		}
		for(int i=0;i<len-3;i++) {
			ss = s.substr(i,4);
			if(ss=="abca"||ss=="acba")
				res = 4;
		}
		for(int i=0;i<len-2;i++) {
			ss = s.substr(i,3);
			if(ss=="aba"||ss=="aca")
				res = 3;
		}
		for(int i=0;i<len-1;i++) {
			ss = s.substr(i,2);
			if(ss=="aa")
				res = 2;
		}
		cout<<res<<endl;
	} 
	return 0;
}

总结：

试着手写一下情况，说不定只有有限个情况。