首页 > 代码库 > 2014 Super Training #1 C Ice-sugar Gourd 模拟,扫描线

2014 Super Training #1 C Ice-sugar Gourd 模拟,扫描线

原题 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 100007char 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 = 0;        for(i=0;i<len;i++)        {            if(ss[i] == H)                H++;            else                T++;        }        if(H%2 || T%2)        {            puts("-1");            continue;        }        int mid = len/2;        h = t = 0;        for(i=0;i<mid;i++)        {            if(ss[i] == H)                h++;            else                t++;        }        if(h == H/2 && t == T/2)        {            puts("1");            printf("%d\n",mid);            continue;        }        ka = 0;    //尾端        kb = mid;  //前端        int flag = 0;        while(ka < mid-1)        {            if(ss[ka] == H)  //尾端扫出去的字母                h--;            else                t--;            if(ss[kb] == H)  //前端扫进来的字母                h++;            else                t++;            ka++,kb++;   //            if(h == H/2 && t == T/2)            {                flag = 1;                break;            }        }        if(flag)        {            puts("2");            printf("%d %d\n",ka,kb);        }        else            puts("-1");    }    return 0;}
View Code