java - ACM 竞赛中的斐波那契数列

Question

我正在尝试找出如何解决 ACM ICPC final 之一的问题(从 2012 年开始，所以我猜是最近的)。它称为 Fibonacci Words，描述为 here在问题 D 下。

我认为我非常接近，因为除了最后一个以外的所有测试用例都给出了正确答案。但最后，我得到 6440026026380244497，它处于正确的数量级，但仍有很大差距——因为数量级很大。 :)

这是我的 Java 代码，有很多注释(太多了，你觉得？可以重构吗？):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class FibonacciWords {

public static StringBuilder[] updateChars(StringBuilder lastOneBack, StringBuilder firstTwoBack, StringBuilder lastTwoBack, StringBuilder firstThreeBack) {
    int pattLen = lastOneBack.length();
    StringBuilder[] newChars = new StringBuilder[2];
    newChars[0] = new StringBuilder(pattLen); // will become the new lastOneBack!
    newChars[1] = new StringBuilder(pattLen); // will become the new firstTwoBack!

    if(lastOneBack.charAt(0) == 'E') { // lastOneBack not full yet
        int shiftCharsBy = 0; // holds amount to shift lastOneBack by
        for(int i = 0; i < pattLen; i++) {
            if(firstTwoBack.charAt(i) != 'E') {
                shiftCharsBy++; // need to move whatever is at beginning of firstTwoBack to end of lastOneBack
            } else {
                break; // when first 'E' is reached in firstTwoBack, the rest are 'E' also
            }
        }

        for(int i = 0; i < pattLen-shiftCharsBy; i++) {
            newChars[0].append(lastOneBack.charAt(i+shiftCharsBy)); // shift lastOneBack by shiftCharsBy characters
        }
        for(int i = 0; i < shiftCharsBy; i++) {
            newChars[0].append(firstTwoBack.charAt(i)); // fill remainder of new lastOneBack with what's in firstTwoBack
        }
    } else { // lastOneBack already full
        newChars[0] = lastTwoBack; // make lastOneBack lastTwoBack (following pattern)
    }

    if(firstTwoBack.charAt(pattLen-1) == 'E') { // firstTwoBack not full yet
        if(lastOneBack.charAt(0) == 'E') {
            for(int i = 1; i < pattLen; i++) {
                if(lastOneBack.charAt(i) != 'E') {
                    newChars[1].append(lastOneBack.substring(i)); // move last characters of lastOneBack to front of new firstTwoBack
                    break;
                }
            }
            int charsAdded = newChars[1].length();
            for(int i = 0; i < pattLen-charsAdded; i++) {
                newChars[1].append('E'); // fill whatever might remain with 'E'
            }
        } else {
            //newChars[1] = lastOneBack;
            for(int i = 0; i < pattLen; i++) {
                if(firstTwoBack.charAt(i) != 'E') {
                    newChars[1].append(firstTwoBack.charAt(i));
                } else {
                    break;
                }
            }
            int charsAdded = newChars[1].length();
            // now take from firstThreeBack--which also isn't full if firstTwoBack isn't--until pattLen is reached
            for(int i = 0; i < pattLen-charsAdded; i++) {
                newChars[1].append(firstThreeBack.charAt(i));
            }
        }
    } else {
        newChars[1] = firstTwoBack; // firstTwoBack doesn't change when already full
    }

    return newChars;
}

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    String pattern = br.readLine();

    long numPattTwoPrior = 0; // number of times pattern occurred in F(n-2)
    if(pattern.equals("0")) {
        numPattTwoPrior++; // since n starts at 2 below, increment this if pattern is F(0), or "0"
    }

    long numPattOnePrior = 0; // number of times pattern occurred in F(n-1)
    if(pattern.equals("1")) {
        numPattOnePrior++; // since n starts at 2 below, increment this if pattern is F(1), or "1"
    }

    int pattLen = pattern.length();
    StringBuilder lastCharsInOnePrior = new StringBuilder(pattLen); // keeps track of last pattLen characters in F(n-1)
    for(int i = 0; i < pattLen; i++) {
        lastCharsInOnePrior.append('E'); // 'E' stands for empty
    }
    lastCharsInOnePrior.setCharAt(pattLen-1, '1'); // since F(1) = "1"

    StringBuilder firstCharsInTwoPrior = new StringBuilder(pattLen);
    for(int i = 0; i < pattLen; i++) {
        firstCharsInTwoPrior.append('E');
    }
    firstCharsInTwoPrior.setCharAt(0, '0'); // since F(0) = "0"

    StringBuilder lastCharsInTwoPrior = null; // last characters always the same as 2 back, so keep track of this
    StringBuilder firstCharsInThreePrior = null; // used for special case in updateChars
    // number of times pattern occurs in F(n)
    long numPattCurr = (n == 0) ? numPattTwoPrior : (n == 1) ? numPattOnePrior : 0;

    for(int i = 2; i <= n; i++) { // finding F(n) up to the n given by the input
        numPattCurr = numPattTwoPrior + numPattOnePrior; // at least this many times in F(n)

        // adding to above all patterns found as part of concatenating F(n-1) and F(n-2), but not either on its own
        middle:
        for(int j = 1; j < pattLen; j++) { // starting at pos. 1 b/c [0, pattLen) is all F(n-1)
            if(lastCharsInOnePrior.charAt(j) == 'E') {
                continue;
            }

            StringBuilder compareWith = new StringBuilder(pattLen); // to compare with pattern
            for(int k = 0; k < pattLen; k++) {
                if(j + k >= pattLen) { // reached end of characters in F(n-1), start checking F(n-2)
                    int posInFirstChars = (j + k) % pattLen;
                    if(firstCharsInTwoPrior.charAt(posInFirstChars) == 'E') {
                        break middle; // none of the remaining overlap between F(n-1) and F(n-2) is as long as pattern, so can stop here
                    } else {
                        compareWith.append(firstCharsInTwoPrior.charAt(posInFirstChars));
                    }
                } else {
                    compareWith.append(lastCharsInOnePrior.charAt(j + k));
                }
            }

            if(pattern.equals(compareWith.toString())) {
                numPattCurr++; // this overlap matched pattern
            }
        }

        // changing characters of F(n-1) and F(n-2), as needed, for next iteration
        StringBuilder[] updatedChars = updateChars(lastCharsInOnePrior, firstCharsInTwoPrior, lastCharsInTwoPrior, firstCharsInThreePrior);
        lastCharsInTwoPrior = lastCharsInOnePrior;
        firstCharsInThreePrior = firstCharsInTwoPrior;
        lastCharsInOnePrior = updatedChars[0];
        firstCharsInTwoPrior = updatedChars[1];

        // changing number of times pattern found for F(n-1) and F(n-2) for next iteration
        numPattTwoPrior = numPattOnePrior;
        numPattOnePrior = numPattCurr;
    }
    System.out.println(numPattCurr);
    System.exit(0);
}
}

我想我只留下了一行注释代码，当它是 else block 中唯一的一行时，它在所有测试用例中给出了完全相同的答案——尽管我用它替换的更正确。

关于我遗漏了什么或我可能如何调试最后一个测试用例的任何建议？或者因为您正在准备比赛或只是致力于学习算法而有兴趣与某人讨论？请告诉我。

Answer 1

C++ solution与 verification (online judge)