项链断裂问题的答案不正确USACO [英] Incorrect Answer in Broken Necklace Problem USACO
问题描述
断项链
您的项链上有N条红色，白色或蓝色的珠子（3 <= N <= 350），其中一些是红色的，其他是蓝色的，以及其他白色，随机排列。以下是n = 29的两个示例：
1 2 1 2
rbbrbrrb
rbbb
rrbr $图$图B
$ br红色珠
b蓝色珠
w白色珠子
在下面的文字中被认为是第一和第二的珠子已在图片中标出。
图A中的配置可以表示为一串b和r，其中b表示蓝珠，r表示红珠，如下所示：brbrrrbbbrrrrrbrrbbrbbbbbrrrrb。 / p>
假设您要在某个时候折断项链，将其笔直摆放，然后从一端收集相同颜色的珠子，直到到达另一种颜色的珠子为止，并在另一端做同样的事情（可能与之前收集的珠子的颜色不同）。
确定项链应该折断的位置这样可以收集最多的珠子。
示例
例如，图中的项链A，可以收集8个珠子，断裂点在9号珠子和10号珠子之间，或者在24号珠子和25号珠子之间。
在某些项链中，如上图B所示，其中包含白色珠子。收集珠子时，遇到的白色珠子可以当作红色或蓝色，然后涂上所需的颜色。表示此配置的字符串将包含三个符号r，b和w。
编写程序以确定可以从所提供的项链上收集的最大珠子数量
输入格式
第1行：N，珠子的数量
第2行：a N个字符串，每个字符串为r，b或w
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
输出格式
单行包含可从提供的项链中收集的最大珠子数量。
11
输出说明
考虑两个小珠的复制（有点像能够绕过结束）。标记为11的字符串。
两个项链复制品在这里连接了
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb | wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** | *****
rrrrrb | bbbbb< -任务
5xr .....＃| ##### 6xb
5 + 6 = 11总计
这是我遇到麻烦的USACO培训问题；我一直得到不正确的答案。 ...而且请不要告诉我这是愚蠢或愚蠢的；那没有帮助！ ：D
嘿，我已经准备好了，但是我没有费心去编写它。无论如何，我的想法就是这个。
首先，您不需要存储所有的珠子颜色（澳大利亚拼写！），只需存储连续多少个相同颜色的珠子。因此，对于：
RRBBBWRR
您只需要存储：
2R 3B 1W 2R
需要注意的一件事是，如果末尾珠和起始珠子是相同的颜色，则必须考虑这一点，所以
RRBBBRR
存储为
4R 3B
或
3B 4R
同样的东西。请注意，这样做的原因不是节省内存或其他任何东西，而是确保彼此相邻的珠子是不同的颜色。我们通过组合相同颜色的珠子来完成此操作。
接下来是每个步骤：
-如果是红色，则加起来之后的所有内容，直到找到蓝色，然后继续添加，直到找到另一个红色
-如果它是蓝色，则除reversed
外，类似地做-如果它是白色，则下一个珠将是红色或蓝色。除了添加白色珠子的数量以外，执行上述操作
以下是一些示例。序列开始和结束处的|标记。
B | RB | R
我们找到一个R，然后是一个B，然后找到另一个R。因此，我们必须在B处停止。
B | RWRB | R
我们先找到一个R，然后再找到另一个R，但是我们还没有找到B，所以我们继续。然后我们找到一个B，然后找到另一个R。这一次，因为我们已经找到一个B，所以我们必须停止。
B | RBW | R
我们找到一个R然后是一个B，但是我们可以继续，因为下一个是a 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.
Write a program to determine the largest number of beads that can be collected from a supplied necklace.
INPUT FORMAT
Line 1: N, the number of beads Line 2: a string of N characters, each of which is r, b, or w
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
11
OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
Two necklace copies joined here
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb | wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
******|*****
rrrrrb|bbbbb <-- assignments
5xr .....#|##### 6xb
5+6 = 11 total
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屋！
