Broken Necklace - nazgul's Blog

Broken Necklace

nazgul posted @ 2011年2月21日 03:03 in USACO , 1420 阅读

USACO TRAINING Section 1.1

Broken Necklace

You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.
Example

For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration will include the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.
PROGRAM NAME: beads
INPUT FORMATLine 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w

SAMPLE INPUT (file beads.in)
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
SAMPLE OUTPUT (file beads.out)
11
OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****

题目大意：你有一个项链，项链上的珠子颜色有红白蓝三种颜色，将项链从一个地方断开，然后展开成直线，然后从一头开始收集珠子，直到碰到其他颜色的，然后在另一头也一样收集。当从某个地方断开时，可以收集到最多的珠子，问最多收集到多少个。
注意：白色的珠子可以算成红色的或者是蓝色的。
样列：
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
从倒数6和7中间断开，可以收集到最多的个数11

1。最简单的方法就是从每个地方断开，然后统计最多的，复杂度O(n^2)。
2。贪心：输入的s是一个环，所以前后可以相连，为了方便，再复制一份在原来的后面成ss，这样收集到的珠子就应该是相邻的。为了收集到最多，断开点绝对不会是同一种颜色的珠子中间，只能是在边界上断开。因此直观的思想就是先计算在一起的相同颜色的有多少个，然后取相邻2种不同颜色最多的个数。比如题目中的样列brbrrrbbbrrrrrbrrbbrbbbbrrrrb，先复制成ss，brbrrrbbbrrrrrbrrbbrbbbbrrrrbbrbrrrbbbrrrrrbrrbbrbbbbrrrrb
统计在一起的相同颜色的珠子个数：1b1r1b3r3b5r1b2r2b1r4b4r2b1r1b3r3r5r1b2r2b1r4b4r1b，然后取相邻2种不同颜色最多的个数。由于白色的可以表示成红色或蓝色，所以白色的要特殊处理。但是像bbwwwbb中间的www应该直接算作b，这样才能取到最多。
下面代码中pre数组用于记录，pre[i]表示与s[i]颜色不同的珠子最近的位置，所以i-pre[i]就是这种颜色在一起的个数，再加上pre[i]到pre[pre[i]]的个数，就是能收集到的个数。其他解释见代码。


#include <stdio.h>
#include <string.h>

char s[701] = {0}, cur, flag; //cur用于标记当前珠子的颜色
int n, pre[701];

int main()
{
	int i, nn, t, k;
	freopen( "beads.in", "r", stdin );
	freopen( "beads.out", "w", stdout );
	memset( pre, -1, sizeof( pre ) );
	scanf( "%d%s", &n, s );
	//将s复制成ss
	for ( flag = cur = i = 0; i < n; ++i )
	{
		s[n+i] = s[i];
		//找到最开始的颜色		
		if ( !cur && s[i] != 'w' ) cur = s[i];
		//flag用于标示s是否只有一种颜色		
		if ( s[i] != s[0] ) flag = 1;
	}
	//如果只有一种颜色
	if ( !cur || !flag )
	{
		printf( "%d\n", n ); return 0;
	}
	//t用于记录当前颜色出现的开始位置
	i = 1; t = 0; k = -1; nn = ( n<<1 )-1;
	//k用于记录w是否可以表示成2种颜色，如果w是在同一种颜色的中间，k为-1,否则k为可以表示成2种颜色的最开始出现的位置
	//比如rrwwwb,则要记录最开始w出现的位置
	while ( i < nn )
	{
		if ( s[i]=='w' || s[i] == cur )
		{
			if ( k == -1 && s[i] == 'w' )
				k = i;
			else k = -1;
			i++;
		}
		else
		{
			pre[i-1] = t-1; cur = s[i];
			if ( k != -1 )
			{
				i = k; pre[i-1] = t-1;
			}
			t = ++i-1;
		}
	}
	t = 0;
	for ( i = 0; i < nn; ++i )
		if ( pre[i] != -1 )
		{
			k = i - pre[pre[i]];
			if ( t < k ) t = k;
		}
	printf( "%d\n", t );
	return 0;
}

[回复]

seo service london 说:
2023年12月11日 22:49

Thank you very much. Can I refer to your post on my website? Your post touched me a lot and helped me a lot. If you have any questions, please visit my site and read what kind of posts I am posting. I am sure it will be interesting.

[回复]

토블리보증업체 说:
2023年12月14日 13:32

It is an excellent blog, I have ever seen. I found all the material on this blog utmost unique and well written. And, I have decided to visit it again and again

[回复]

솔카지노도메인 说:
2023年12月14日 14:16

I am very happy to discover your post as it will become on top in my collection of favorite blogs to visit

[回复]

밀라노도메인 说:
2023年12月14日 14:55

Nice to be visiting your blog again, it has been months for me. Well this article that i've been waited for so long. I need this article to complete my assignment in the college, and it has the same topic with your article. Thanks, great share

[回复]

토토배너순위 说:
2023年12月14日 15:12

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free

[回复]

먹튀사냥꾼보증업체 说:
2023年12月14日 15:27

That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea. thanks once more

[回复]

안전놀이터검증 说:
2023年12月14日 15:37

Awesome Website. Keep up the good work.

[回复]

링크모음사이트 说:
2023年12月14日 15:56

Thanks for every other informative site. The place else may just I get that kind of information written in such an ideal means? I have a venture that I’m just now operating on, and I have been on the look out for such information

[回复]

안전토토사이트 说:
2023年12月14日 15:56

I've found this interesting! Check it out!

[回复]

파워볼게임 说:
2023年12月14日 16:18

On that website page, you'll see your description, why not read through this

[回复]

메이저놀이터 说:
2023年12月14日 16:28

I got too much interesting stuff on your blog. I guess I am not the only one having all the enjoyment here! Keep up the good work

[回复]

토토사이트 说:
2023年12月14日 16:33

I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post

[回复]

메이저놀이터 说:
2023年12月14日 16:36

I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post

[回复]

사설토토사이트 说:
2023年12月14日 16:48

It is an excellent blog, I have ever seen. I found all the material on this blog utmost unique and well written. And, I have decided to visit it again and again

[回复]

양방배팅적발 说:
2023年12月14日 16:54

I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post

[回复]

에볼루션바카라 说:
2023年12月14日 16:58

I am very happy to discover your post as it will become on top in my collection of favorite blogs to visit

[回复]

토토사이트 사장 说:
2023年12月14日 17:50

[回复]

토토마켓가입 说:
2023年12月14日 17:53

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information

[回复]

부자카지노 먹튀 说:
2023年12月14日 18:04

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free

[回复]

토토실험실 说:
2023年12月14日 18:07

Really a great addition. I have read this marvelous post. Thanks for sharing information about it. I really like that

[回复]

양방배팅 说:
2023年12月14日 18:23

[回复]

얀카지노검증 说:
2023年12月14日 18:30

I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post

[回复]

스카이파크가입 说:
2023年12月14日 18:33

I’m happy I located this blog! From time to time, students want to cognitive the keys of productive literary essays composing. Your first-class knowledge about this good post can become a proper basis for such people. nice one

[回复]

엠카지노주소 说:
2023年12月14日 18:40

Really a great addition. I have read this marvelous post. Thanks for sharing information about it. I really like that

[回复]

실시간파워볼 说:
2023年12月14日 19:02

I truly welcome this superb post that you have accommodated us. I guarantee this would be valuable for the vast majority of the general population. I am reading your writing well. I know a site that might be helpful for your writing. please read my article and tell us your impressions. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article . This is an excellent post I seen thanks to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post . Really i appreciate the effort you made to share the knowledge. The topic here i found was really effective to the topic which i was researching

[回复]

먹튀검증사이트안전놀이터 说:
2023年12月14日 19:21

I think this is a really good article. You make this information interesting and engaging. You give readers a lot to think about and I appreciate that kind of writing

[回复]

메이저토토 说:
2023年12月14日 19:23

Really a great addition. I have read this marvelous post. Thanks for sharing information about it. I really like that

[回复]

먹튀제보 说:
2023年12月14日 19:33

Every one of the substance you said in post is too great and can be extremely helpful. I will remember it, much obliged for sharing the data continue upgrading, looking forward for more posts.Thanks . Decent to be going to your web journal once more, it has been months for me. Well this article i’ve been sat tight for so long. I require this article to finish my task in the school, and it has same theme with your article. Much obliged, awesome offer. This is such an extraordinary asset, to the point that you are giving and you give it away for nothing. I cherish seeing sites that comprehend the benefit of giving a quality asset to free. It is the old what circumvents comes around schedule

[回复]

카지노사이트 说:
2023年12月14日 19:45

Thank you so much as you have been willing to share information as ABC.

[回复]

단폴되는사이트추천 说:
2023年12月14日 19:47

I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post

[回复]

먹튀검증사이트 说:
2023年12月14日 20:00

I think this is a really good article. You make this information interesting and engaging. You give readers a lot to think about and I appreciate that kind of writing

[回复]

먹튀테일 说:
2023年12月14日 20:00

The PCSO Lotto Result today and yesterday this October 2023 is here! Refresh page for official winning numbers - 6/58, 6/55, 6/49, 6/45, 6/42, Swertres

[回复]

먹튀대피소 说:
2023年12月14日 20:08

I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post

[回复]

카지노사이트 说:
2023年12月14日 20:18

I think that thanks for the valuabe information and insights you have so provided here.

[回复]

먹튀검증 说:
2023年12月14日 20:27

I've found this interesting! Check it out!

[回复]

꽁나라주소 说:
2023年12月14日 20:42

This may be the correct weblog for everyone who is hopes to discover this topic.

[回复]

토토사이트추천 说:
2024年1月21日 14:39

This is also a very good post which I really enjoyed reading. It is not every day that I have the possibility to see something like this..

[回复]

바카라사이트 说:
2024年1月21日 17:02

It is the plan to give significant data and best works on, including a comprehension of the administrative procedure.

[回复]

카지노 커뮤니티 说:
2024年1月21日 17:18

Great, thanks for sharing this article post.Really thank you! Really Cool

[回复]

먹튀검증 说:
2024年1月21日 17:54

Thank you for taking the time to publish this information very useful!

[回复]

바카라 사이트 说:
2024年1月21日 18:43

I think this is one of the most significant information for me. And i’m glad reading your article

[回复]

카지노 커뮤니티 说:
2024年1月21日 19:01

Thanks so much for the blog post.Really thank you! Much obliged

[回复]

꽁머니 说:
2024年1月21日 19:34

Appreciate it! A good amount of stuff.

[回复]

카지노사이트추천 说:
2024年1月21日 20:47

Your substance is completely splendid from various perspectives. I think this is drawing in and educational material. Much obliged to you such a great amount for thinking about your substance and your perusers.

[回复]

industrial outdoor s 说:
2024年1月21日 21:24

I favor the idea, such a good deal

[回复]

카지노커뮤니티 说:
2024年1月22日 14:09

Thank you so much for sharing these amazing tips. I must say you are an incredible writer, I love the way that you describe the things. Please keep sharing

[回复]

소액결제현금화 说:
2024年1月22日 14:40

I favor the idea, such a good deal

[回复]

고화질스포츠중계 说:
2024年1月22日 15:15

Very awesome!!! When I seek for this I found this website at the top of all blogs in search engine.

[回复]

카지노사이트 说:
2024年1月22日 15:51

Very good post.Really looking forward to read more. Really Great.

[回复]

카지노사이트 说:
2024年1月24日 16:41

This is exactly for that reason fabulous and additionally extremely creative. I simply absolutely love all the different shades and additionally anyone can get the software on the deliver would be happy.

[回复]

카지노 说:
2024年1月24日 18:17

This is a wonderful post. I came to this site first time and I really like your post. Keep posting it. I love seeing websites that understand the value of providing a quality resource for free.I will wait for your post. Thank you.

[回复]

바카라 说:
2024年1月26日 14:50

바카라 바카라사이트 우리카지노 카지노는 바카라, 블랙잭, 룰렛 및 슬롯 등 다양한 게임을 즐기실 수 있는 공간입니다. 게임에서 승리하면 큰 환호와 함께 많은 당첨금을 받을 수 있고, 패배하면 아쉬움과 실망을 느끼게 됩니다.

[回复]

하노이 가라오케 说:
2024年1月26日 14:54

하노이 꼭 가봐야 할 베스트 업소 추천 안내 및 예약, 하노이 밤문화 에 대해서 정리해 드립니다. 하노이 가라오케, 하노이 마사지, 하노이 풍선바, 하노이 밤문화를 제대로 즐기시기 바랍니다. 하노이 밤문화 베스트 업소 요약 베스트 업소 추천 및 정리.

[回复]

안전놀이터 说:
2024年1月29日 12:51

No.1 먹튀검증 사이트, 먹튀사이트, 검증사이트, 토토사이트, 안전사이트, 메이저사이트, 안전놀이터 정보를 제공하고 있습니다. 먹튀해방으로 여러분들의 자산을 지켜 드리겠습니다. 먹튀검증 전문 커뮤니티 먹튀클린만 믿으세요!!

[回复]

베트남 밤문화 说:
2024年1月29日 14:11

베트남 남성전용 커뮤니티❣️ 베트남 하이에나 에서 베트남 밤문화를 추천하여 드립니다. 베트남 가라오케, 베트남 VIP마사지, 베트남 이발관, 베트남 황제투어 남자라면 꼭 한번은 경험 해 봐야할 화끈한 밤문화로 모시겠습니다.

[回复]

IT technology 说:
2024年6月03日 16:24

The tech-original mission is to help you better understand technology, and make better decisions in the fields of IT, Tech, and Crypto.
https://www.tech-original.com/