夕日的光辉
题目描述
Kanae 发现了一条写了 nn 个小写英文字母所组成的字符串 strstr 的纸条，她想要在纸条上找到自己最喜欢的单词 "pink" 并裁剪下来。在裁剪之前，Kanae 要先找到 "pink" 这个子序列。
形式化地，我们定义一个字符串 strstr 的子序列为在 strstr 中选取一部分组成的字符串。例如当 str =str=abc时，strstr 共有六个非空的子序列，分别是a、b、c、ab、bc、ac、abc。
现在将 pos(i)pos(i) 定义为 子序列 "pink" 的第 ii 个字符在原串 strstr 中的位置，Kanae 剪下单词 "pink" 的花费定义为：
\max\limits_{i \in {1,2,3}} {(pos(i+1)-pos(i)-1)}i∈1,2,3max?(pos(i+1)−pos(i)−1)
请你求出 Kanae 剪下单词 "pink" 的可能最大的花费。如果无法找到任何子序列 "pink" ，请你输出-1
输入描述
第一行有一个正整数 TT 代表一个文件有几组数据。
每个数据占 2 行。
第 1 行有 1 个整数 n，表示字符串的长度。
第 2 行有 1 个长度为 n 的字符串 str。
1≤T≤10^5
4≤n≤10^6
所有数据的 nn 总和不超过 10^6
输出描述
共 T 行。
第 i 行代表第 ii个数据的答案。
先判断是否存在“pink”，不存在的话就直接输出“-1”。
如果存在答案的话，可以发现最后对结果产生贡献的‘p’和‘k’肯定是从头开始的第一个p和从尾部开始的第一个k。用 p1 和 p4分别记录他们的位置， 然后再记录从p1开始的第一个i的位置p2和从p4开始到这找第一个n出现的位置。
接下来就是要找p1和从p3往前找的第一个“i” 的距离减一 、p4和p2开始第一个出现的“n”减一、p3 - p2 -1的最大值
时间复杂度O（n）
#include <stdio.h> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #pragma GCC optimize(2) #define mm(i,v) memset(i,v,sizeof i); #define mp(a, b) make_pair(a, b) #define one first #define two second using namespace std; typedef long long ll; typedef pair<int, int > PII; const int N = 1e6 + 5, mod = 1e9 + 9, INF = 0x3f3f3f3f; int t, n, p1, p2, p3, p4, flag; char s[N]; int main() { cin >> t; while (t--) { cin >> n; scanf("%s", s + 1); p1 = 0, p2 = 0, p3 = 0, p4 = 0; for (int i = 1; i <= n; ++i) { if (s[i] == ‘p‘) p1 = 1; if (s[i] == ‘i‘ && p1 != 0) p2 = 1; if (s[i] == ‘n‘ && p2 != 0) p3 = 1; if (s[i] == ‘k‘ && p3 != 0) { p4 = 1; break; } } if (p4 == 0) { puts("-1"); continue; } flag = 0; for (int i = 1; i <= n; ++i) { if (flag == 0) { if (s[i] == ‘p‘) { p1 = i; flag = 1; continue; } else { s[i] = ‘a‘; continue; } } else if (flag == 1) { if (s[i] == ‘i‘) { p2 = i; break; } else { s[i] = ‘a‘; continue; } } } flag = 0; for (int i = n; i >= 1; --i) { if (flag == 0) { if (s[i] == ‘k‘) { p4 = i; flag = 1; continue; } else { s[i] = ‘a‘; continue; } } else if (flag == 1) { if (s[i] == ‘n‘) { p3 = i; break; } else { s[i] = ‘a‘; continue; } } } int Max = p3 - p2 - 1; // cout << p3 << " " << p2 << endl; for (int i = p3 - 1; i >= 1; --i) { if (s[i] == ‘i‘) { if (i - p1 - 1 > Max) { Max = i - p1 - 1; } break; } } for (int i = p2 + 1; i <= n; ++i) { if (s[i] == ‘n‘) { if (p4 - i - 1 > Max) { Max = p4 - i - 1; } break; } } cout << Max << endl; } } /* 1 22 pinpipkinpkinpknninnpk */
友情提示，这个oj好像不能关闭cin cout 的同步流
就是因为这串代码我对着自己代码一度debug到怀疑人生
原文：https://www.cnblogs.com/mwh123/p/11823557.html