本文主要是介绍2017多校联合第六场1008/hdu 6103,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Kirinriki
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1084 Accepted Submission(s): 430
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.
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
1 5 abcdefedcb
5Hint[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
题意 : 给出一串字符串,从中选出两个不重叠的字符串,使得两个字符串的距离和 <= m 的最长字符串长度,A,B 串中的字符距离计算为 disA,B=∑i=0n−1|Ai−Bn−1−i|
题解 :
因为字符串长度很小,故我们可以枚举其每一个前缀与每一个后缀,
然后在枚举的子串内利用尺取法将区间等分,
利用差值之和不大于 m
的条件双指针同时遍历两个区间,更新最大值即可。
(关于为什么字符串需要反转再处理一次)
因为第一次我们处理的是字符串的前缀,反转相当于处理它的后缀。
假设该字符串为 abcdefghi
,最终答案为 def
与 ghi
,
我们处理的前缀要想包含这两个子串,其区间必须是 [a-i]
,且在尺取法进行过程中我们是围绕中心轴改变子串长度的,
此时的中心轴所在位置为 e
这一点,也就是说我们得到的结果可能是 bcd
与 fgh
(两个长度相等且位置关于中心轴对称),
对于每一个前缀来说,其中心轴位置都靠左,所以显然得不到上面所说的答案,
于是我们需要利用同样的方法处理其所有后缀,最终结果会在 [d-i]
这段区间中得到。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <list>
#include <bitset>
#include <stack>
#include <stdlib.h>
#define lowbit(x) (x&-x)
#define e exp(1.0)
//ios::sync_with_stdio(false);
// auto start = clock();
// cout << (clock() - start) / (double)CLOCKS_PER_SEC;
typedef long long ll;
typedef long long LL;
using namespace std;
const int maxn=5000+10;
char s[maxn];
int len,m,ans;
void solve()
{for(int i=2;i<=len;i++){int l=0,n=0,sum=0;for(int j=0;j<i/2;j++){sum+=abs(s[j]-s[i-j-1]);if(sum<=m){n++;ans=max(ans,n);}else{sum-=abs(s[l]-s[i-l-1]);sum-=abs(s[j]-s[i-j-1]);j--;l++;n--;}}}
}
int main()
{int T;scanf("%d",&T);while(T--){cin>>m>>s;len=strlen(s);ans=0;solve();reverse(s,s+len);solve();cout<<ans<<endl;}return 0;
}
这篇关于2017多校联合第六场1008/hdu 6103的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!