域名被墙检测网站,阜新本地网站建设平台,大作设计网站作品,沧州网站推广优化商集客电话正题
题目链接:https://www.luogu.org/problemnew/show/P3514 题目大意
一个12序列#xff0c;若干个询问求有没有一个子串之和为kkk 解题思路
首先感谢ZYCdalaoZYCdalaoZYCdalao的温馨提示。
然后进入正题 首先我们考虑一个串的和为kkk 那么最边的数的情况(1,1),(1,2),(2…正题
题目链接:https://www.luogu.org/problemnew/show/P3514 题目大意
一个12序列若干个询问求有没有一个子串之和为kkk 解题思路
首先感谢ZYCdalaoZYCdalaoZYCdalao的温馨提示。
然后进入正题 首先我们考虑一个串的和为kkk 那么最边的数的情况(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2) 后三种情况将其中一个2去掉第一种情况把两边去掉那么和就变成了k−2k-2k−2
那么我们可以求一个最长的和为偶数和和为奇数的串开始推导就好了。 codecodecode
#includecstdio
#includealgorithm
using namespace std;
const int N1000100;
int n,q,ansl[2*N],ansr[2*N],z;
char s[N];
void get_ans(int l,int r,int num)
{while(num0){ansl[num]l;ansr[num]r;if(s[l]T) l;else if(s[r]T) r--;else l,r--; num-2;}
}
int main()
{scanf(%d%d,n,q);scanf(%s,s1);for(int i1;in;i)z(s[i]T?2:1);int l1,rn;get_ans(1,n,z);for(l1;lns[l]T;l);for(rn;r1s[r]T;r--);if(n-r1l)get_ans(1,r-1,z-(n-r)*2-1);elseget_ans(l1,n,z-l*21);for(int i1;iq;i){scanf(%d,l);if(!ansl[l]) printf(NIE\n);else printf(%d %d\n,ansl[l],ansr[l]);}
}
