c++ - 如何解决我们必须向前和向后迭代的 Broken Necklace Problem

Question

This problem has been asked here but that's not what I am looking for.

大家好!我正在解决断链问题，这是一个 USACO 问题。这是问题所在:

你有一条由 N 个红色、白色或蓝色珠子组成的项链(3<=N<=350)，其中一些是红色的，一些是蓝色的，还有一些是白色的，随机排列。以下是 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

图片中标记了下文中第一和第二考虑的珠子。

图 A 中的配置可以表示为一串 b 和 r，其中 b 代表蓝色珠子，r 代表红色珠子，如下所示:brbrrrbbbrrrrrrrbbbbbbrrrrb。

假设您要在某个点打断项链，将其平放，然后从一端收集相同颜色的珠子，直到找到不同颜色的珠子，然后在另一端做同样的事情(这可能与之前收集的珠子颜色不同。

确定应该打破项链的点，以便收集最多数量的珠子。

例子:例如图A的项链，可以收集到8颗珠子，断裂点要么在9号珠和10号珠之间，要么在24号珠和25号珠之间。

在一些项链中，如上图 B 所示，包含白色珠子。收集珠子时，遇到的白色珠子可能会被处理为红色或蓝色，然后涂上所需的颜色。表示此配置的字符串可以包含 r、b 和 w 三个符号中的任何一个。

编写一个程序来确定可以从提供的项链中收集到的最大数量的珠子。

实际上，我尝试使用 C++ 来解决问题。但是，我似乎在案例 3 中得到了一个错误的答案，即

77 rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr

我的代码输出 72 但答案是 74。我什至看不出答案是 74(难道我们必须减去 5 b block 才能得到 77-5=72)我们如何得到 74？我的代码怎么错了，我遗漏了哪些案例？我似乎无法调试此代码...

任何帮助将不胜感激。谢谢。

#include <bits/stdc++.h>
using namespace std;

int main(){
//For faster I/O
ios::sync_with_stdio(0);
cin.tie(0);
//read and write files
freopen("beads.in", "r", stdin);
freopen("beads.out", "w", stdout);
//get as input all the bead colors
int N; cin >> N;
char beads[N]; for(int i=0;i<N;i++) cin >> beads[i];

//the max amount of stuff we can get
int maxCount = INT_MIN;
//some helper variables we'll need later
int currCount = 0; int counter1 = 0; int counter2 = 0; char currColor = 'w';

for(int i=0;i<N;i++){
    //set counter1 and counter2 both to 0
    counter1 = 0; counter2 = 0;
    //the iterator
    int j;

    //First loop - forwards
    //---------------------
    j = i;
    currColor = beads[i];
    while(beads[j]==currColor || beads[j]=='w'){
        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];
        if(j==N-1) j=0;
        else j++;
        counter1++;
        if(counter1 > N) break;
    }

    //Second loop - backwards
    //-----------------------
    j = (i>0) ? i-1 : N-1;
    currColor = (i>0) ? beads[i-1] : beads[N-1];
    while(beads[j]==currColor || beads[j]=='w'){
        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];
        if(j==0) j=N-1;
        else j--;
        counter2++;
        if(counter2 > N) break;
    }

    //get the current count and get max value
    currCount = counter1 + counter2;
    maxCount = max(currCount,maxCount);
}

if(maxCount > N) cout << N;
else cout << maxCount;

cout << "\n";

return 0;
}

Answer 1

对于您的代码，我稍微修正了一下。但不能保证它适用于所有情况。 74 是正确答案的原因是因为您可以将颜色从“r 变为 b”或“b 变为 r”。因此，例如，使用“rrrrbbb”，您可以捕获所有 7 个珠子。现在当它出现“w”时，它可能是“r”或“b”。因此，有了这个字符串。

rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr

您可以捕获 b 和它后面或前面的 w，但不能捕获 r。如果你捕获第一个 b 那么你也不能捕获第二个 b。因此，无论哪种方式抓取，您都将剩下 1r、1w 和 1b。

为什么你的代码不起作用，你不允许颜色从 r 变为 b 一次。我修复了你的前向代码，测试了你的代码，但我没有测试你的后向代码。它适用于下面的字符串，但谁知道所有其他字符串。

有了这个，我给你一个剧透代码。对于我的代码，它通过了提交，但我仍在努力提高它的效率，所以我可能会在将来修改它。

尽管如此，对于我的代码。将字符串的结尾想象成一个门户。一个你踏入门户。你会出现在一开始。尽管如此，如果你穿过第一个入口，然后到达你开始的地方，入口就消失了。因此，这意味着您完成了。

另外，请记住，您可以向后搜索得到的东西，也可以在远距传送设备的帮助下向前搜索。

更新:

虽然传送代码看起来很酷，但它并不是最高效的代码。我想出了第二种解决方案来解决这个问题。那就是把珠子压缩成 block ，然后把珠子 block 加在一起。在那种方法中，我将珠子分为两种类型“r”和“b”。对于 'w' 珠子，如果它们在一个 block 之前，它们的计数将不会添加到该 block ，但我们会跟踪它们的计数。但是，如果他们在一个 block 之后，他们将被添加到一个 block 中。对于像 rwr 或 bbwwbb 这样的 'w' 珠子，它们成为该 block 的计数，或者简单地我们将它们分别转换为 r 或 b。最后我们只需要计算每个相邻的珠子 block 的数量。因此，保存嵌套循环。那是剧透代码2。剧透2也通过了提交。它看起来像 C 代码，但剧透 2 可以作为 C 或 CPP 代码提交。

你的代码有一些固定的:

#include <bits/stdc++.h>
using namespace std;

int main(){
//For faster I/O
ios::sync_with_stdio(0);
cin.tie(0);
//read and write files
freopen("beads.in", "r", stdin);
freopen("beads.out", "w", stdout);
//get as input all the bead colors
int N; cin >> N;

char beads[N]; for(int i=0;i<N;i++) cin >> beads[i];

//the max amount of stuff we can get
int maxCount = INT_MIN;
//some helper variables we'll need later
int currCount = 0; int counter1 = 0; int counter2 = 0; char currColor = 'w';

for(int i=0;i<N;i++){
    //set counter1 and counter2 both to 0
    counter1 = 0; counter2 = 0;
    //the iterator
    int j; 
    bool changeOne = 0;

    //First loop - forwards
    //---------------------
    j = i;
    currColor = beads[i];
    while(1){
        // The color allow to change one 
        // For example
        // rrrrbbbb is perfectly 8 beads you can get. 
        // Nonetheless bbbrrrrbr you can only get the first 3b and 4 r to make the longesth.
        // Now when it come to w, it can be either. Thus with this string below.
        // rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrw
        // you can get either one b with the w behind it or one b with the w before it.
        if ( beads[j] != currColor ){
           if ( beads[j] != 'w' && changeOne ) break;

           // if we start with 'w'
           // and the color haven't change
           // we better change it
           if ( currColor == 'w' ) 
             currColor = beads[j];
           else 
             changeOne = true;
        }

        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];

        if(j==N-1) j=0;
        else j++;

        counter1++;
        if(counter1 == N) break;
    }

    //Second loop - backwards
    //-----------------------
    j = (i>0) ? i-1 : N-1;
    currColor = (i>0) ? beads[i-1] : beads[N-1];
    while(beads[j]==currColor || beads[j]=='w'){
        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];
        if(j==0) j=N-1;
        else j--;
        counter2++;
        if(counter2 == N) break;
    }

    //get the current count and get max value
    currCount = counter1 + counter2;
    maxCount = max(currCount,maxCount);
}

if(maxCount > N) cout << N;
else cout << maxCount;

cout << "\n";

return 0;
}

剧透代码:

#include <fstream>

using namespace std;

int main () {
    ifstream fin("beads.in");
    ofstream fout("beads.out");

    int totalBeads, len, thisCount, j;
    int maxL = 0,
        changeOne = 0;

    // Read into char array instead of 
    // string for faster performance    
    char beads[350], thisChar, lookFor;

    fin >> len; 
    fin >> beads;

    // lastIndex is made so that this 
    // doesn't have to be computed for every loop.
    const int lastIndex = len - 1;

    for (int i = 0; i < len; i++ ){
      thisCount = 1;
      lookFor = beads[i];
      j = i + 1;
      while(1) {
        // If we reach the end 
        // we start again at the beginning.
        if ( j > lastIndex ) j = 0;
        // If we reach where we use to be
        // we are done for this nested loop
        if ( j == i ) goto makeLength;

        thisChar = beads[j];

        if ( thisChar != lookFor ){
          if ( lookFor == 'w' ){
            lookFor = thisChar;
          } else if ( thisChar != 'w' ){
            lookFor = thisChar;
            // If bead already change between
            // r and b one we are done.
            if ( changeOne == 1 ){
              makeLength:
              if ( thisCount > maxL ) maxL = thisCount;
              changeOne = 0;
              break;
            }
            // We are allow one change.
            changeOne++;
          }
        }
        thisCount++; 
        j++;
      }
    }

    fout << maxL << endl;

    return 0;
}

剧透 2( block 压缩):

#include <stdio.h>

typedef struct beadBlock{
    int preW;
    int count;
    char type;
} beadBlock;

int main () {
    FILE *fin  = fopen ("beads.in", "r");
    FILE *fout = fopen ("beads.out", "w");

    int len;
    int maxL = 0,
        thisCount = 0,
        wCount = 0,
        pos = 0,
        blockLen = 0;

    // For this algorithm we compress the beads to blocks of beads.
    // At worst there is the same amount of block as bead. 
    // For example, rbrbrbrb.

    // We never need to keep track of the white beads that are
    // behind a block. This, method, included their count into the 
    // a block count.
    beadBlock blocks[351]; 
    char beads[351], thisChar, lookFor;

    fscanf(fin, "%d", &len);
    fscanf(fin, "%s", beads);

    // Discard all white beads at the beginning of the string.
    while ( beads[pos] == 'w' ){
        pos++;
        wCount++;
    }

    // If pos == len, it is all w
    // lookFor's value can be of anything
    // because it won't be used.
    if ( pos != len ) lookFor = beads[pos];
    blocks[blockLen].preW = wCount;
    for ( ; pos < len; pos++ ){
        thisChar = beads[pos];

        // If it is w we just increase 
        // the white count.
        if ( thisChar == 'w' ) {
            wCount++;
        } else {

          if ( thisChar != lookFor ){
            blocks[blockLen].count = thisCount;
            blocks[blockLen].type = lookFor;
            blockLen++;

            // Preparing the wCount for next block.
            blocks[blockLen].preW = wCount;
            thisCount = 0;
            lookFor = thisChar;
          }
          // For anything that is not a 'w', we turn wCount to zero.
          wCount = 0;
        }

        thisCount++;
    }

    blocks[blockLen].count = thisCount;
    blocks[blockLen].type = lookFor;
    blockLen++;

    if ( blockLen < 3 ){
        // If there are less than 3 block, it is easy.
        // If there is just www, the w count will be added
        // by doing block[0].preW.
        maxL = blocks[0].preW;
        maxL += blocks[0].count;
        if (blockLen == 2) maxL += blocks[1].count;
    } else {
        int lastBlock = blockLen - 1;
        // If there were more than 3 blocks,
        // we calculate the count of the border blocks first
        // and use the length of the higher count.

        // If block[0] and block[last] are the same type
        // we need to add an additional block.
        if ( blocks[0].type == blocks[lastBlock].type){
          int maxL2;
          // block[last] + block[0] + block[1]
          // block[last] + block[last - 1] + block[0]
          maxL = blocks[lastBlock].count;
          // When calculating a block, any white
          // succeeding a block will be inclusive in the count of
          // that block but not the white beads proceeding it.
          // Thus, when adding two block together that are next
          // to each other we do not need to add the
          // posW value to the count. However, we have to add preW
          // to the value of the block that does not
          // have any other block on the left of it.
          maxL += blocks[lastBlock].preW;
          maxL += blocks[0].preW;
          maxL += blocks[0].count;
          maxL += blocks[1].count;

          maxL2 = blocks[lastBlock - 1].preW;
          maxL2 += blocks[lastBlock - 1].count;
          maxL2 += blocks[lastBlock].count;
          maxL2 += blocks[0].preW;
          maxL2 += blocks[0].count;
          if ( maxL2 > maxL) maxL = maxL2;
        } else {
          // If last block and first block are not the same type,
          // just add block[last] to block[0]
          maxL = blocks[lastBlock].preW;
          maxL += blocks[lastBlock].count;
          maxL += blocks[0].preW;
          maxL += blocks[0].count;
        }
        // Then we loop.to calculate the length of all
        // blocks that are next to each other.
        for ( int i = 0; i < lastBlock; i++ ){
           // Reusing this count.
           thisCount = blocks[i].preW;
           thisCount += blocks[i].count;
           thisCount += blocks[i+1].count;
           if ( thisCount > maxL ) maxL = thisCount;
        }
    }

    fprintf(fout, "%d\n", maxL );

    return 0;
}