【水题】USACO Broken Necklace
进入USACO要注册才可看题: http://train.usaco.org/usacogate题目：【已翻译】http://www.wzoi.org/usaco/11%5C202.asp
SAMPLE INPUT (file beads.in)
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
SAMPLE OUTPUT (file beads.out)
11
又一水题……YY的算法//无法用语言表达啊
http://dl.iteye.com/upload/attachment/494721/fbe1ccf6-29de-31d2-a7d6-e2d6e1e93213.gif
……感觉飞一般的繁琐！
虽然1次A……但是写代码时感觉很是不爽
/*ID: 1006100071PROG: beadsLANG: C++*/#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <iomanip>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <ctype.h>using namespace std;int main(){freopen ("beads.in", "r", stdin);freopen ("beads.out", "w", stdout);int i, len, maxs, start, change;bool hash = {0};string s;cin >> len >> s;s = s + s; //实现首尾相接maxs = 1, change = start = 0;len <<= 1; //串长加倍if (s != 'w')hash-'a'] = true, change = 1;for (i = 1; i < len; i++){//cout << i << ' ' << change << ' ' << s-'a' << endl;if (s != 'w' && !hash-'a'])memset (hash, false, sizeof(hash)), hash-'a'] = true, change++;if (change > 2 || i == len-1){//cout << i - start << "-----------\n";if (maxs < i - start)maxs = i - start;change = 0;memset (hash, false, sizeof(hash));i = start;start++;if (s != 'w')hash-'a'] = true, change = 1;}}if (maxs > len / 2) //最多取所给原来的串长maxs = len / 2;cout << maxs << endl;return 0;}
页:
[1]