HDU 6103 Kirinriki

本文由 Ocrosoft 于 2017-08-12 12:00:35 发表

Kirinriki

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

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
 

Solution
2017 Multi-University Training Contest – Team 6
题意:
标题提示我们回文串。

两个不重合的子串向中心一起延长会形成奇偶长度两种合串。

枚举一下中心向外延伸,如果和超过了阈值弹掉中心处的位置。双指针维护。

时间复杂度O(n^{2})O(n2)

另解:

枚举[1,i],[j,n]用同样方法往内缩。

时间复杂度O(n^{2})O(n2)

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e5 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define _link(x) x&&x
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
template<class T>inline T read(T &num)
{
	char CH; bool F = false;
	for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
	for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
	F && (num = -num);
	return num;
}
template<class T>inline T read()
{
	T num;
	return read(num);
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
	read(t);
	read(args...);
	return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
	int stk[70], tp = 0;
	if (p < 0) { putchar('-'); p = -p; }
	if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
	while (p) stk[++tp] = p % 10, p /= 10;
	while (tp) putchar(stk[tp--] + '0');
	if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
	print(t, '\0');
	if (sizeof...(args))putchar(' ');
	else putchar('\n');
	print(args...);
}
#endif
#pragma endregion

char s[20010];
int main()
{
	int N; read(N);
	while (N--)
	{
		int m; read(m);
		scanf("%s", s);
		int ans = 0;
		auto Solve = [m, &ans](char *_stl, char *_str)
		{
			char *edl = _stl, *edr = _str;
			char *stl = _stl, *str = _str;
			int sum = 0;
			do
			{
				if (sum + abs(*edl - *edr) <= m) // 满足要求
					sum += abs(*edl - *edr), ans = max((int)(stl - edl + 1), ans);
				else // 不满足要求
					sum -= abs(*stl-- - *str++), edl++, edr--; // 不加edl++, edr--;会漏算
			} while (edl-- != s && *++edr != '\0');
		};
		for (char *it = s; *(it + 1) != '\0'; ++it) // 枚举中点
		{
			Solve(it, it + 1);
			if (it != s)Solve(it - 1, it + 1);
		}
		print(ans);
	}
	return 0;
}
 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 6103 Kirinriki

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址