HDU 6103 Kirinriki（尺取法）

http://acm.hdu.edu.cn/showproblem.php?pid=6103

题意：

给出一个字符串，在其中找两串互不重叠的子串，计算它们之间的dis值，要求dis值小于等于m，求能选的子串的最大长度。

思路：

由于这两个子串是互不重叠的，那么这两个子串之间的间隔可以是奇数也可以是偶数，针对这两种情况我们枚举中心点，然后尺取法处理，具体看代码就懂了。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,ll> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 int n, m;

 int cnt;

 int ans;

 char s[maxn];

 int tmp[maxn];

 void check()

 {

     int l=,r=;

     int dis=;

     while(r<cnt)

     {

         dis+=tmp[++r];

         while(dis>m)   dis-=tmp[++l];

         ans=max(ans,r-l);

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&m);

         scanf("%s",s+);

         n=strlen(s+);

         ans=;

         for(int i=;i<=n;i++)  //中间相隔奇数

         {

             int l=i-,r=i+;

             cnt=;

             while(l> && r<=n)  {tmp[++cnt]=abs(s[l]-s[r]);l--;r++;}

             check();

         }

         for(int i=;i<=n;i++) //中间相隔偶数

         {

             int l=i,r=i+;

             cnt=;

             while(l> && r<=n)  {tmp[++cnt]=abs(s[l]-s[r]);l--;r++;}

             check();

         }

         printf("%d\n",ans);

     }

     return ;

 }