[アルゴリズム]伯俊>#17435.関数とクエリーの合成

1962 ワード
テキストリンク
質問リンク
白駿#17435。合成とクエリー
解答方法
アルゴリズムやテクニックを使わずに問題を解決できることを想像してみてください.O(QN)の時間複雑度!時間制限の1秒を超えやすいですよね?この問題を解決するために,一部の関数結果をテーブルに予め保存する前処理プロセスを実現した.
このような前処理プロセスによって、配列内の部分をすばやく問い合わせることができるデータ構造を、疎表、Sparse Tableと呼ぶ.「一部の関数の結果をテーブルに保存」し、これらの「部分」を2^kに設定します.あらかじめナビゲートした値が小さすぎたり大きすぎたりすると、その効果は小さくなりますので、2^kに設定します.
shortCutsという名前の配列で、関数が実行した結果を18回(2^kコード#コード#
import java.util.Scanner;

public class FunctionAndQuery {
    static final int MAX_K = 19; // 2^19 > 500,000
    static final int MAX_M = 200001;
    static int[][] shortCuts = new int[MAX_K][MAX_M];
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        for (int i = 1; i <= m; i++) shortCuts[0][i] = sc.nextInt();
        for (int i = 1; i < MAX_K; i++) {
            for (int j = 1; j <= m; j++) {
                shortCuts[i][j] = shortCuts[i - 1][shortCuts[i - 1][j]];
            }
        }

        StringBuilder result = new StringBuilder();
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int n = sc.nextInt();
            int x = sc.nextInt();

            for (int bit = 0; bit < MAX_K; bit++) {
                if ((n & (1 << bit)) > 0) {
                    x = shortCuts[bit][x];
                }
            }
            result.append(x + "\n");
        }

        System.out.print(result.toString());
    }
}
Mysql同時デッドロックの原因と解決方法
CloudWatch-EC 2ログバインド