题意
给定一个只包含'X'和'.'的串和整数k，可以对串进行k次替换，每次把一个'.'替换成'X'。
串的长度和k的范围都是2e5级别。
问：替换完成后，最多有多少个连续的'X'？
题解
公理1：最多替换k次。
公理2：复杂度支持遍历串的所有'.'，进行滑动窗口。
性质1：最终替换结果一定是"靠在"一个比较长的"X串"上。
性质2：每个'.'都有左边和右边的X数量，数量从0到|S|-1。
性质3：尽可能多地替换'.'，答案才能最优。
答案1（公理2、性质3）：要做一个滑动窗口，尽可能的统计答案。每次统计替换了'.'之后的'X'的连续数量。
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; const int MAXN = 3e5; char s[MAXN]; struct Point { int lastNum;//前面的'X'数量 int nextNum;//后面的'X'数量 }p[MAXN]; int cnt = 0;//点数量 int main() { scanf("%s", &s); int k; scanf("%d", &k); int len = strlen(s); int xCnt = 0;//X数量 int tmpAns = 0; for (int i = 0; i < len; i++) { if (s[i] == '.') { p[++cnt].lastNum = xCnt; tmpAns = max(tmpAns, xCnt); xCnt = 0; }else { xCnt++; } } int tmpCnt = cnt; xCnt=0; for (int i = len-1; i >=0; i--) { if (s[i] == '.') { p[tmpCnt].nextNum = xCnt; tmpAns = max(tmpAns, xCnt); tmpCnt--; xCnt = 0; } else { xCnt++; } } if (cnt<=k) { printf("%d\n",len); return 0; } if (k == 0) { //返回最大连续子段和 printf("%d\n", tmpAns); return 0; } //lastNum 前面的'X'数量 //nextNum 后面的'X'数量 int l=1,r; int totX=p[l].lastNum+1;//总共能够覆盖的X数量 int ans=totX; //第一次拓展 for(r = l+1; r <= l+k-1&&r<=cnt; r++) { totX++;//本身 totX+=p[r].lastNum; if(r==l+k-1){ totX+=p[r].nextNum; } ans=max(ans,totX); } r--; //边缘拓展 拓展cnt-len次 for (int i = 1; i <= cnt-k; i++) { totX-=p[l].lastNum; l++; r++; totX+=p[r].nextNum; ans=max(ans,totX); } printf("%d\n",ans); return 0; }
TRANSLATE with