藍橋杯——試題 演算法訓練 Sereja and Squares

解題思路：該問題與左右括弧匹配原則相類似
解題演算法：動態規劃

Java 程式碼

import java.util.Scanner;

/**
 * @Author LZP
 * @Date 2021/2/17 16:18
 * @Version 1.0
 *
 * 動態規劃
 * 
 * 試題 演算法訓練 Sereja and Squares
 * <p>
 * 資源限制
 * 時間限制：4.0s   記憶體限制：256.0MB
 * 問題描述
 * 　　Sereja在平面上畫了n個點，點i在坐標(i,0)。然後，Sereja給每個點標上了一個小寫或大寫英文字母。Sereja不喜歡字母"x"，所以他不用它標記點。Sereja認為這些點是漂亮的，當且僅當：
 * 　　·所有的點可以被分成若干對，使得每個點恰好屬於一一對之中。
 * 　　·在每對點中，橫坐標較小的會被標上小寫字母，較大的會被標上對應的大寫字母。
 * 　　·如果我們在每對點上畫一個正方形，其中已知的一對點會作為正方形的相對的頂點，它們間的線段會成為正方形的對角線，那麼在所有畫出的正方形中不會有相交或觸碰的情況。
 * 　　小Petya擦掉了一些小寫字母和所有大寫字母，現在Sereja想知道有多少種方法來還原每個點上的字母，使得還原後這些點是漂亮的。
 * 輸入格式
 * 　　第一行是一個整數n，表示點的個數。
 * 　　第二行是一個長度為n的字元串，包含小寫字母和問號"?"，是按照橫坐標遞增的順序的每個點的描述。問號表示這個點的字母被Petya擦掉了。保證輸入串不含字母"x"。
 * 輸出格式
 * 　　輸出答案對4294967296取模的值。如果沒有可行的方案，輸出0。
 * 樣例輸入
 * 4
 * a???
 * 樣例輸出
 * 50
 * 樣例輸入
 * 4
 * abc?
 * 樣例輸出
 * 0
 * 樣例輸入
 * 6
 * abc???
 * 樣例輸出
 * 1
 * <p>
 * 數據規模和約定
 * 　　20個測試點的n分別為：
 * 　　5,10,20,50,100,
 * 　　200,500,1000,2000,5000,
 * 　　10000,20000,30000,40000,50000,
 * 　　60000,70000,80000,90000,100000.
 * <p>
 * <p>
 * 遞歸實現:
 * 不過效率太低
 * 使用棧，將其當作左右括弧匹配的問題來實現，這是本題的重要解題思路
 *
 * 本題適合用C++寫，C++的效率比Java高太多了
 */
public class Main {

    private static long num = 0;

    private static long mod = 4294967296L;

    private static char[] arr = new char[100000 + 7];

    private static long[] dp = new long[100000 + 7];

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        char[] tempChar = input.next().toCharArray();
        for (int i = 0; i < tempChar.length; i++) {
            arr[i + 1] = tempChar[i];
        }

        // 沒有右括弧 ，這一步一定不能漏
        dp[0] = 1;
        long start  = System.currentTimeMillis();
        f(arr, n);
        long end  = System.currentTimeMillis();
        System.out.println(num);
        System.out.println(end - start + "ms");
    }

    static void f(char[] arr, int n) {
        if (n % 2 == 1) {
            // 奇數直接返回
            return;
        }

        // 用來記錄左括弧的個數
        int left = 0;
        int n2 = n >> 1;

        // 循環從1~n
        for (int i = 1; i <= n; i++) {
            if (arr[i] == '?') {
                // 若是問好，則可能是左括弧也可能是右括弧
                // 確定右括弧的最大上限
                int rightMax = i >> 1;
                if (i != n) {
                    /*
                        當dp到下標i時，可以確定的最多的右括弧為i/2，
                        若現在確定的是左括弧則前面i-1個格子就是確定rightMax個右括弧的結果
                        若現在確定的是右括弧，則前面i-1個格子確定的就是rightMax-1個右括弧的結果
                     */
                    // 因為只是確定了右括弧的最大上限，而不確定到底是多少，所以有很多種可能
                    // 每次後面多來一個右括弧的話，前面的可能性就越多
                    for (; rightMax >= 1; rightMax--) {
                        dp[rightMax] += dp[rightMax - 1];
                        dp[rightMax] %= mod;
                    }
                } else {
                    //i==n一定是右括弧，只要確定前n-1個格子所確定出來的n>>1-1個右括弧的結果即可
                    dp[rightMax] = dp[rightMax - 1];
                    dp[rightMax] %= mod;
                }
            } else {
                // 若不是問好，則一定是左括弧
                left++;
            }
        }

        if (left > n2) {
            // 左括弧的個數超過一半
            return;
        }

        for (int i = 0; i < n2 - left; i++) {
            dp[n2] *= 25;
            dp[n2] %= mod;
        }
        num = dp[n2] % mod;
    }
}
Tags:

VirMach 便宜 VPS