广工新生赛G

广工新生赛 - 闪闪发光心动不已！

题意：

题意不清楚，刚开始读错题了，但是赛后还是读明白了。

给一个字符串，求若干个后若干个 ==子串== 长度的最大值。

思路：

首先求得子串不是连续的，所以用的会暴毙

只好用dp求，这种变量比较少，我喜欢用cnt_k, cnt_ki, cnt_kir, cnt_kira

然后有了下面代码

标签：

dp，前缀和。

    int cnt_k = 0, cnt_ki = 0, cnt_kir = 0, cnt_kira = 0;
    for (int i = 0; i < n; i++) {
        if(s[i] == 'k')
            cnt_k++;
        else if(s[i] == 'i') {
            cnt_ki = min(cnt_k, cnt_ki + 1);
        }
        else if(s[i] == 'r') {
            cnt_kir = min(cnt_ki, cnt_kir + 1);
        }
        else if(s[i] == 'a') {
            cnt_kira = min(cnt_kir, cnt_kira + 1);
        }
        pre[i] = cnt_kira;
    }

==这样是不对的==

这个字符串求出来的结果是2个子串kira，但是只有一个。

所以有了下面改后的代码

    int cnt_k = 0, cnt_ki = 0, cnt_kir = 0, cnt_kira = 0;
    for (int i = 0; i < n; i++) {
        if(s[i] == 'k')
            cnt_k++;
        else if(s[i] == 'i') {
            if(cnt_k)
                cnt_ki++;
        }
        else if(s[i] == 'r') {
            if(cnt_ki)
                cnt_kir++;
        }
        else if(s[i] == 'a') {
            if(cnt_kir) {
                cnt_k = 0;
                cnt_ki = 0;
                cnt_kir = 0;
                cnt_kira++;
            }
        }
        pre[i] = cnt_kira;
    }

如果产生完整子串，变量重新初始化。

还有一个细节就是pre[i] 表示0 - i, last[i]就得表示 i + 1 - n，不然如果第一个子串的最后一个字母与第二个子串的第一个字母相同时，就会出错。

然后这样交上去，75%

因为子串的前提是要先出现kira。特判一下输出就行。

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve() {
	int n;
	cin >> n;

	string s;
	cin >> s;
	vector<int>pre(n, 0);
	vector<int>last(n, 0);
	
	int cnt_k = 0, cnt_ki = 0, cnt_kir = 0, cnt_kira = 0;
	for (int i = 0; i < n; i++) {
		if(s[i] == 'k')
			cnt_k++;
		else if(s[i] == 'i') {
			cnt_ki = min(cnt_k, cnt_ki + 1);
		}
		else if(s[i] == 'r') {
			cnt_kir = min(cnt_ki, cnt_kir + 1);
		}
		else if(s[i] == 'a') {
			if(cnt_kir) {
				cnt_k = 0;
				cnt_kira++;
			}
		}
		pre[i] = cnt_kira;
 	}
	
	int cnt_i = 0, cnt_oki = 0, cnt_doki = 0;
	cnt_ki = 0;

	for (int i = n - 1; i >= 0; i--) {
		if(s[i] == 'i') {
			cnt_i++;
		}
		else if(s[i] == 'k') {
			cnt_ki = min(cnt_i, cnt_ki + 1);
		}
		else if(s[i] == 'o') {
				if(cnt_ki) 
					cnt_oki++;
		}
		else if(s[i] == 'd') {
			if(cnt_oki) {
				cnt_i = 0;
				cnt_ki = 0;
				cnt_oki = 0;
				last[i] = cnt_doki++;
				continue;
			}
		}
		last[i] = cnt_doki;
	}	

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if(pre[i])
			ans = max(ans, (pre[i] + last[i]) * 4);
	}
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int T = 1;
	while(T--) {
		solve();
	}

	return 0;
}

教训：

• 统计不连续的子串方式。记得清零

• 记得看一眼题要不要先出现第一个子串的条件。