原题 HDU 3363 http://acm.hdu.edu.cn/showproblem.php?pid=3363
给你一个串,串中有H跟T两种字符,然后切任意刀,使得能把H跟T各自分为原来的一半。
解法: 把串想象成一个环,只要满足H跟T都为偶数个,那么就可以做一条过圆心的直线把H跟T平分掉,过直线,只要考虑平分H或者T中的一个就可以了,因为直线本来就把环平分,而此时平分了H或者T,那么剩下的那个也是平分掉的。
具体证明: http://hi.baidu.com/superlong/item/fa552253eb9b71c09f266703
类似于维护这样一条扫描线:
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100007 char ss[N]; int main()
{
int len,ka,kb,i,j;
int h,t,H,T;
while(scanf("%d",&len)!=EOF && len)
{
scanf("%s",ss);
H = T = ;
for(i=;i<len;i++)
{
if(ss[i] == 'H')
H++;
else
T++;
}
if(H% || T%)
{
puts("-1");
continue;
}
int mid = len/;
h = t = ;
for(i=;i<mid;i++)
{
if(ss[i] == 'H')
h++;
else
t++;
}
if(h == H/ && t == T/)
{
puts("");
printf("%d\n",mid);
continue;
}
ka = ; //尾端
kb = mid; //前端
int flag = ;
while(ka < mid-)
{
if(ss[ka] == 'H') //尾端扫出去的字母
h--;
else
t--;
if(ss[kb] == 'H') //前端扫进来的字母
h++;
else
t++;
ka++,kb++; //转
if(h == H/ && t == T/)
{
flag = ;
break;
}
}
if(flag)
{
puts("");
printf("%d %d\n",ka,kb);
}
else
puts("-1");
}
return ;
}