网站站点怎么做,设计平面广告,软件开发分类,网络营销案例介绍题目#xff1a;小A很喜欢字母N#xff0c;他认为连续的N串是他的幸运串。有一天小A看到了一个全部由大写字母组成的字符串#xff0c;他被允许改变最多2个大写字母#xff08;也允许不改变或者只改变1个大写字母#xff09;#xff0c;使得字符串中所包含的最长的连续的…题目小A很喜欢字母N他认为连续的N串是他的幸运串。有一天小A看到了一个全部由大写字母组成的字符串他被允许改变最多2个大写字母也允许不改变或者只改变1个大写字母使得字符串中所包含的最长的连续的N串的长度最长。你能帮助他吗时间限制C/C 1秒其他语言2秒空间限制C/C 64M其他语言128M输入描述输入的第一行是一个正整数T0 T 20表示有T组测试数据。对于每一个测试数据包含一行大写字符串S0 |S| 50000|S|表示字符串长度。 数据范围 20%的数据中字符串长度不超过100 70%的数据中字符串长度不超过1000 100%的数据中字符串长度不超过50000。输出描述对于每一组测试样例输出一个整数表示操作后包含的最长的连续N串的长度。示例1输入例子3 NNTN NNNNGGNNNN NGNNNNGNNNNNNNNSNNNN输出例子4 10 18题解经典滑动窗口类题型我们可以维护一个窗口先不断扩充该窗口统计窗口内字符非“N”的数目为cnt如果cnt超过2那么该窗口无效需要窗口左边界向右移动至cnt2,用双指针right和left,right向右移动至cnt2时判断左边界的字符是否非“N”是则说明该字符是通过消耗了一次改变机会现在窗口向右移动该次机会又会还回来。right指针每次向右移动时更新最长连续N串的值。#include bits/stdc.h using namespace std; int main() { int T; cinT; string s; while(T--) { cins; int ns.size(); int left0,right0,cnt0,ans0; for(;rightn;right) { if(s[right]!N) cnt; while(cnt2) { if(s[left]!N) cnt--; left; } ansmax(ans,right-left1); } coutansendl; } } // 64 位输出请用 printf(%lld)