破碎的项链USACO问题 [英] Broken Necklace USACO Problem
问题描述
破碎的项链
您有一条由N个红色，白色或蓝色珠子（3 <= N <= 350）组成的项链，其中一些是红色的， ，和其他白色，随机排列。以下是n = 29的两个示例：
1 2 1 2
rbbrbrbb
rbbb
rrbr
rrwr
brww
bbrr
bbbb
bbrb
rrbr
brrr
brrr
rrrb
rbrrrw
图A图B
r red bead
b blue bead
w white bead
珠子被认为是第一和第二
图A中的配置可以表示为b和r的字符串，其中b表示蓝色珠子， r代表一个红色的，如下所示：brbrrrbbbrrrrrbrrbbrbbbbrrrb。
假设你要在某一点打破项链，直接放置，然后收集相同颜色的珠子从一端直到你到达不同颜色的珠子，并做同样的另一端（这可能不是与之前收集的珠子相同的颜色）。
确定项链应折断的点，以便收集最多的珠子。
示例
例如，对于图A中的项链，可以收集8个珠子，断裂点在珠子9和珠子10之间，或者在珠子24和珠子25之间。
在某些项链中，包括白色珠子，如上图B所示。当收集珠子时，遇到的白色珠子可以被处理为红色或蓝色，然后涂上所需的颜色。代表这个配置的字符串将包括三个符号r，b和w。
这是一个USACO训练问题，我有麻烦;我得到不正确的答案。 ...请不要告诉我这是愚蠢的或愚蠢的;这不是帮助！ ：D
嘿，我是这个，但我没有打扰到它。
首先，你不需要存储所有的珠子颜色（去澳大利亚拼写！），你只需要存储多少相同颜色的珠子在一排。因此：
RRBBBWRR
您只需存储：
2R 3B 1W 2R
$ b
$ b RRBBBRR
存储为
4R 3B
或
3B 4R
同样的事情。注意，这样做的原因不是节省内存或任何东西，而是要确保彼此相邻的磁珠是不同的颜色。
接下来是每一个：
- 如果它是红色的，你加起来所有的那些，之后，直到你找到一个蓝色，然后继续添加，直到你找到另一个红色
- 如果它是蓝色，除了颠倒以外类似
- 如果它是白色，那么下一个珠将是红色或蓝色。除了添加白色珠子的数量以外，请按照上述操作
以下是一些示例。
B | RB | R
我们找到一个R，然后是一个B，然后是另一个R.因此，我们必须停止在B.在
B | RWRB | R
找到一个R，然后另一个R，但我们还没有找到一个B，所以我们继续。然后我们找到一个B，然后找到另一个R.这一次，因为我们发现一个B，我们必须停止。
B | RBW | R
我们找到一个R然后是一个B，但我们可以继续，因为下一个是W，那么我们找到另一个R，所以我们必须停止。在
B | WRBWB | R
我们计数W，然后我们找到R.因此，我们继续，直到我们找到一个B，然后继续，直到我们找到另一个R.这
B | WBRWR | B
是相反的情况。
现在你要做的就是实现它：D。当然，这没有考虑R，B和W中的珠的实际数目，并且仅仅是单个珠序列的实例。你必须检查所有可能的序列。
最后，您可能会注意到，这个算法有时是浪费的，但是N < 350因此即使一个O（N ^ 3）应该工作在1秒钟。也许2.反正，我相信这是O（N ^ 2）所以你应该能够在一秒钟内运行这个程序350次 。请评论如果有什么混乱，因为我不是最好的解释。快乐编码。
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.
This is a USACO training problem i'm having trouble with; i keep getting incorrect answers. ...and please don't tell me this is stupid or silly; that's not helping! :D
解决方案 Heh, I'm up to this one but I haven't been bothered to code it up. Anyway, my ideas are this.
Firstly, you don't need to store all the bead colours (Go Australian spelling!), you just need to store how many beads of the same colour are in a row. So for:
RRBBBWRR
you just need to store:
2R 3B 1W 2R
One thing to note is if the ending and the starting beads are the same colour you have to account for that, so
RRBBBRR
should be stored as
4R 3B
or
3B 4R
Same thing. Note that the reason for this is not to save memory or anything, but to ensure that beads next to each other are different colours. We have done this by combining beads of the same colour.
Next is you go through each one:
- If it's red, you add up all the ones after that till you find a blue and then continue adding until you find another red
- If it's blue, do similarly except reversed
- If it's white, then the next bead will be red or blue. Do as above except with the number of white beads added
Here are some examples. The |'s mark where the sequence begins and ends.
B|RB|R
we find a R then a B then another R. Therefore we have to stop at the B. In
B|RWRB|R
We find an R and then another R but we haven't found a B yet so we continue. Then we find a B and then another R. This time, since we've found a B we have to stop.
B|RBW|R
we find a R then a B but we can continue since the next one is a W, then we find another R so we have to stop. In
B|WRBWB|R
we count the W then we find a R. Therefore we continue till we find a B and then continue till we find another R. This
B|WBRWR|B
is a reverse case.
Now all you have to do is implement it :D. Of course this doesn't take into account the actual number of beads in the the R, B and W and are just examples of single bead sequences. You will have to check all possible sequences. You also have to take care of the sequences which wrap around from the back to the start.
Lastly, you may notice that this algorithm is sometimes wasteful but N < 350 so even an O(N^3) should work in 1 second. Maybe 2. Anyway, I believe this is O(N^2) so you should be able to run this program 350 times in one second. Please comment if something's confusing because I'm not the best explainer. Happy coding.
这篇关于破碎的项链USACO问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
