正题

题目链接:https://www.luogu.org/problemnew/show/P3514

---

题目大意

一个12序列，若干个询问求有没有一个子串之和为$k$

---

解题思路

首先感谢$ZYCdalao$的温馨提示。

然后进入正题
首先我们考虑一个串的和为$k$
那么最边的数的情况$(1,1),(1,2),(2,1),(2,2)$
后三种情况将其中一个2去掉，第一种情况把两边去掉那么和就变成了$k-2$

那么我们可以求一个最长的和为偶数和和为奇数的串开始推导就好了。

---

$code$

#include<cstdio> #include<algorithm> using namespace std; const int N=1000100; int n,q,ansl[2*N],ansr[2*N],z; char s[N]; void get_ans(int l,int r,int num) {while(num>=0){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",s+1);for(int i=1;i<=n;i++)z+=(s[i]=='T'?2:1);int l=1,r=n;get_ans(1,n,z);for(l=1;l<=n&&s[l]=='T';l++);for(r=n;r>=1&&s[r]=='T';r--);if(n-r+1<l)get_ans(1,r-1,z-(n-r)*2-1);elseget_ans(l+1,n,z-l*2+1);for(int i=1;i<=q;i++){scanf("%d",&l);if(!ansl[l]) printf("NIE\n");else printf("%d %d\n",ansl[l],ansr[l]);} }

总结

以上是生活随笔为你收集整理的P3514-[POI2011]LIZ-Lollipop【思路题】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。