hdu6103 Kirinriki(尺取法)

题意:

在一个长度为 n 的字符串中找两个长度相同、不重叠的子串,这两个子串的距离不超过 m 。求出子串的最长长度。两个子串的定义:
disA,B=n1i=0|AiBn1i|

分析:

比赛时的思路是二分答案。可在判断每个二分值上没想出好办法,只能枚举两个起点,再算距离。这样是O(n^3)的复杂度。显然不行。

官方题解给出的方法很巧妙,后来知道了这叫尺取法。

像判断回文数那样,枚举一下中心向外延伸,如果和超过了阈值就删掉靠近中心的两个数,然后继续往头加数字。双指针维护。像这样反复地推进头和尾的方法,叫尺取法。

代码:
#include iostream
#include algorithm
#include queue
#include stack
#include vector
#include set
#include cmath
#include cstdlib
#include cstring
#include cstdio
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int MAXN = 5005;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;
char s[MAXN];
int m, n;
int main() {
    int T;
    scanf("%d", T);
    while (T--) {
        scanf("%d", m);
        scanf("%s", s);
        n = strlen(s);
        int ans = 0;
        for (int mid = 0; mid  n; mid++) {
            int tail = mid - 1, head = mid + 1;
            int tot = 0, cnt = 0;
            for (int i = tail, j = head; i = 0  j  n; i--, j++) {
                cnt++;
                tot += abs(s[i] - s[j]);
                if (tot = m)   ans = max(ans,cnt);
                if (tot  m) {
                    tot -= abs(s[tail] - s[head]);
                    tail--;
                    head++;
                    cnt--;
                }
            }
        }
        for (int lmid = 0, rmid = 1; lmid  n - 1; lmid++, rmid++) {
            int tail = lmid, head = rmid;
            int tot = 0, cnt = 0;
            for (int i = tail, j = head; i = 0  j  n; i--, j++) {
                cnt++;
                tot += abs(s[i] - s[j]);
                if (tot = m)   ans = max(ans,cnt);
                if (tot  m) {
                    tot -= abs(s[tail] - s[head]);
                    tail--;
                    head++;
                    cnt--;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
最新回复(0)
/jishu1mP6saInchaSiJxutXCaoJGh2HOBzXUsPkgEMiVbBlg_3D4794995
8 简首页