首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。