残破的项链USACO问题 [英] Broken Necklace USACO Problem

问题描述

破碎项链

您有N个红色，白色或蓝色珠的项链（3'; = N＆其中; = 350）其中一些是红色，蓝色等，和其他白，无规排列。这里有两个例子为N = 29：

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.

图A中的配置可重新presented作为字符串的b以及的r，其中b重新presents蓝色珠而r重新presents一个红色的，如下：。brbrrrbbbrrrrrbrrbbrbbbbrrrrb

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.

示例

例如，对于图中的A项链，8珠可被收集，与断裂点之间任一胎圈9和胎圈10要不然之间珠24和珠25

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.

在一些项链，白色的珠子已被列入如图B以上。当收集珠，遇到了一个白珠可被视为红色或蓝色，然后涂上所需的颜色。即重新presents的字符串这种配置将包括三个符号R，B和W

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.

这是一个USACO训练问题，我遇到麻烦;我不断收到不正确的答案。 ......请不要告诉我这是愚蠢的或愚蠢的;这不是帮助！ ：D

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

推荐答案

嘿，我到这一个，但我还没有费心去code起来。总之，我的的想法的是这一点。

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

您只需要存储：

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

应当存储为

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

我们发现，则成为一个B，那么另一个R.因此，我们必须停止在B中

we find a R then a B then another R. Therefore we have to stop at the B. In

B|RWRB|R

我们找到的R，然后另一条R，但我们还没有发现A，B又那么我们继续。然后，我们找到B，然后又R.这一次，因为我们发现A，B，我们必须停止。

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

我们发现，则成为A，B，但我们可以继续，因为下一个是W，那么我们就找到另一条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

再算上W，则我们发现了一个R.因此，我们继续，直到我们找到B，然后继续，直到我们找到另一个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.

现在你所要做的就是实现它：D。当然，这并不考虑在所述的R，B和W珠的实际数量和是单珠序列的只是例子。您必须检查所有可能的序列。您还可以采取哪些包从回到开始围绕序列的照顾。

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.

最后，你可能会注意到，该算法有时是一种浪费，但N'LT; 350所以即使是O（N ^ 3）应该在1秒。也许2.无论如何，我相信这是O（N ^ 2），所以你应该能够在一秒钟内运行此程序，350倍的 的。请发表评论，如果事情是混乱的，因为我不是最好的讲解员。快乐编码。

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屋！