`

【水题】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的算法//无法用语言表达啊

……感觉飞一般的繁琐!
虽然1次A……但是写代码时感觉很是不爽


/*
ID: 1006100071
PROG: beads
LANG: 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[30] = {0};
	string s;
	cin >> len >> s;
	s = s + s;    //实现首尾相接
	maxs = 1, change = start = 0;
	len <<= 1;    //串长加倍
	if (s[0] != 'w')
		hash[s[0]-'a'] = true, change = 1;
	for (i = 1; i < len; i++)
	{
		//cout << i << ' ' << change << ' ' << s[i]-'a' << endl;
		if (s[i] != 'w' && !hash[s[i]-'a'])
			memset (hash, false, sizeof(hash)), hash[s[i]-'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[start] != 'w')
				hash[s[start]-'a'] = true, change = 1;
		}
	}
	if (maxs > len / 2)   //最多取所给原来的串长
		maxs = len / 2;
	cout << maxs << endl;
	return 0;
}
  • 大小: 20.5 KB
分享到:
评论

相关推荐

    USACO题目Broken Necklace (beads)及代码解析

    本题是USACO竞赛中的一个经典题目,名为"Broken Necklace (beads)",主要涉及字符串处理、动态规划以及贪心算法。题目要求寻找最优的断点,使得收集到相同颜色珠子的最大数量。以下是相关知识点的详细说明: 1. ...

    Broken Necklace(参考解析)

    综上所述,这段代码实现了一个解决方案来解决“Broken Necklace”问题,即如何从一条断开的项链中选取最长的一段连续的红色或蓝色珠子。通过双向遍历的方式统计不同颜色珠子的数量,并最终确定最长的连续段。

    [USACO 1.1.4]破碎的项链.cpp

    [USACO 1.1.4]破碎的项链.cpp

    USACO官网93题fps格式 OJ题库

    USACO 官网第一到 五章 练习题中文语言官方数据 fps格式支持导入所有OJ 1 [1.1] 你的飞碟在这儿 Your Ride Is Here 2 [1.1] 贪婪的送礼者Greedy Gift Givers 3 [1.1] 黑色星期五Friday the Thirteenth 4 [1.1] 坏掉...

    USACO英汉对照题目

    1.1.4 "Broken Necklace" 可能涉及字符串操作和链表处理。 1.2.1 "Milking Cows" 可能与数组和排序有关,可能是优化挤牛奶的效率问题。 1.2.3 "Name That Number" 可能是关于数字表示和逻辑推理的问题。 1.2.4 ...

    USACO所有题目题解

    4. **Broken Necklace (beads)**: 这道题涉及项链上的珠子排列问题,原解法是O(n^2),但可以通过类似动态规划的方法优化到O(n)。关键在于将项链视为线性结构,分别记录向左和向右收集蓝红珠子的最优情况。可以使用...

    USACO题解(NOCOW整理版)1

    具体包括了几个不同难度级别的问题,如“Your Ride Is Here”,“Greedy Gift Givers”,“Friday the Thirteenth”和“Broken Necklace”。每个问题的解析都提供了算法思想和解决方案,有的通过简单的数学计算,有...

    usaco题目的副本1

    在"Greedy Gift Givers"这个题目中,可能需要使用哈希表来统计礼物的分布情况,或者在"Broken Necklace"题目中,利用哈希表记录不同颜色的珠子的数量。 2. **Python内置函数`ord()`和`chr()`**:`ord()`函数用于...

    USACO(Train)解题报告.doc

    ### Chapter 1 Section 1.2 - Broken Necklace (beads) 这道题涉及搜索和优化。标准的搜索算法复杂度为O(n^2),但可以通过动态规划或类似策略优化到O(n)。定义四个数组`bl`, `br`, `rl`, `rr`来记录项链中不同方向...

    USACO全部题目

    #### Broken Necklace 该题目涉及的是循环链表和字符串匹配的问题。主要目标是找到一种方法,能够将一条断裂的项链重新连接起来,使其恢复原状。解决方案可能包括使用KMP算法、Rabin-Karp算法或者其他字符串匹配...

    第1章总结1

    同时,"Friday the Thirteenth"题目引入了模运算,"Broken Necklace"则涉及到数组的使用。 接着,1.2节重点是完整搜索,如"Milking Cows"中运用离散化技术,"Transformations"和"Name That Number"通过枚举解决,而...

Global site tag (gtag.js) - Google Analytics