ZOJ - 3985 - String of CCPC （思维 + 暴力）

题意：

询问一共有有多少个CCPC，每个得1分，可以自己在任意位置添加字母，第i次添加需要耗费i-1分

思路：

既然每次添加需要耗分，添加第二个字母，相当于没有添加，所以只需要添加一次就好

先计算出原始字符串中的CCPC，在不破坏CCPC的前提下，添加字母即可

代码：

#include<iostream>

#include<cstdio>

using namespace std;

const int maxn = 2e5+10;

int flag[maxn];

char str[maxn];

int main() {

	int t, n, ans, temp;

	scanf("%d", &t);

	while(t--) {

		ans = temp = 0;

		scanf("%d %s", &n, str+1);

		for(int i = 1; i <= n; i++)

			flag[i] = 0;

		for(int i = 1; i <= n-3; i++) {

			if(str[i]=='C' && str[i+1]=='C' && str[i+2]=='P' && str[i+3]=='C')

				ans++, flag[i] = 1;

		}

		for(int i = 1; i <= n-2; i++) {

			if(flag[i] || temp) continue;

			if(str[i]=='C' && str[i+1]=='C' && str[i+2]=='C' && flag[i+1]==0) temp = 1;

			else if(str[i]=='C' && str[i+1]=='P' && str[i+2]=='C' && flag[i-1]==0) temp = 1;

			else if(str[i]=='C' && str[i+1]=='C' && str[i+2]=='P') temp = 1;

		}

		printf("%d\n", ans+temp);

	}

	return 0;

}

巴特西

ZOJ - 3985 - String of CCPC （思维 + 暴力）

题意：

思路：

代码：

最新文章

热门文章