Hdu6103 Kirinriki（2017多校第6场）

最新推荐文章于 2019-08-25 17:57:00 发布

Jelly_acm

最新推荐文章于 2019-08-25 17:57:00 发布

阅读量443

点赞数

分类专栏： HDU ----尺取

本文链接：https://blog.csdn.net/Jelly_acm/article/details/77074210

版权

HDU 同时被 2 个专栏收录

181 篇文章

订阅专栏

----尺取

9 篇文章

订阅专栏

Kirinriki

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 600 Accepted Submission(s): 231

Problem Description

We define the distance of two strings A and B with same length n is

disA,B=∑i=0n−1|Ai−Bn−1−i|
The difference between the two characters is defined as the difference in ASCII.
You should find the maximum length of two non-overlapping substrings in given string S, and the distance between them are less then or equal to m.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integers m : the limit distance of substring.
Then a string S follow.

Limits

T≤100

0≤m≤5000
Each character in the string is lowercase letter,

2≤|S|≤5000

∑|S|≤20000

Output

For each test case output one interge denotes the answer : the maximum length of the substring.

Sample Input

  
  
   
   1
5
abcdefedcb

Sample Output

  
  
   
   5


   
   
    
    
     
     Hint
    
    [0, 4] abcde
[5, 9] fedcb
The distance between them is abs('a' - 'b') + abs('b' - 'c') + abs('c' - 'd') + abs('d' - 'e') + abs('e' - 'f') = 5

Source

2017 Multi-University Training Contest - Team 6

——————————————————————————————————

题目的意思是给出一个字符串，选择两个不相交的长度一样的子串，要求两个的差别不大于给出的m，差别计算是第一个子串由前往后，后一个字符串由后往前依次相差的大小之和，求最长取多少

思路：先把字符串逆序，然后枚举每次错位下最长最长长度，一次错位下最长长度由尺取解决。注意重叠的判定

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <unordered_map>
#include <functional>

using namespace std;

char s1[5009],s2[5009];
int m;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%s",&m,s1+1);
        int n = strlen(s1 + 1);
        for(int i=1; i<=n; i++) s2[i]=s1[n-i+1];
        s2[n+1]='\0';
        int ma=0;
        for(int i=1; i<=n; i++)
        {
            int l=1,r=1,k=0;
            while(1)
            {
                while(k+abs(s1[i+r-1]-s2[r])<=m&&r+r+i-1<=n)
                {
                    k+=abs(s1[i+r-1]-s2[r]);
                    r++;
                }
                ma=max(ma,r-l);
                if(r+r+i-1>n) break;
                k-=abs(s1[i+l-1]-s2[l]);
                l++;
            }
        }
        for(int i=1; i<=n; i++)
        {
            int l=1,r=1,k=0;
            while(1)
            {
                while(k+abs(s2[i+r-1]-s1[r])<=m&&r+r+i-1<=n)
                {
                    k+=abs(s2[i+r-1]-s1[r]);
                    r++;
                }
                ma=max(ma,r-l);
                if(r+r+i-1>n) break;
                k-=abs(s2[i+l-1]-s1[l]);
                l++;
            }
        }
        printf("%d\n",ma);
    }
    return 0;
}