PTC 2015/12_1 C: Warehouse

題目

比賽時，記憶體並沒有限制，題目放上 etutor 後，記憶體有 64MB 的限制，造成 next 陣列開不出來（etutor 竟然把 MLE 回報成 TLE…）。現在有新增第二筆測資，N <= 500，這樣就能在 64MB 的限制下解出該筆測資。

分析

使用類似 LCA 倍增法的原理建出下列陣列，再搭配快速冪。

int next[i][x, y] = 從 x, y 出發，2^i 秒後到哪裡。

利用

next[i][x, y] = next[i-1][ next[i-1][x, y] ]

可在 O(max_log_k * max_n * max_n) 建出數列。

之後每次詢問 O(lg(k))。

AC Code

#include <cstdio>
using namespace std;

const int MAX_N = 500;
const int MAX_LOG_K = 27; // ceil(lg(10^8))

int N, K;
int data[MAX_N * MAX_N];
int next[MAX_LOG_K][MAX_N * MAX_N]; // next[i][x, y] = next 2^i move from x, y

int encode(int x, int y) {
    return y * N + x;
}

void init() {
    const int dx[8] = {+1, +1, 0, -1, -1, -1, 0, +1};
    const int dy[8] = {0, -1, -1, -1, 0, +1, +1, +1};

    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            int idx = encode(x, y);
            if (data[idx] == -1) next[0][idx] = -1;
            else {
                int new_x = x + dx[data[idx] - 1];
                int new_y = y + dy[data[idx] - 1];
                if (new_x < 0 || new_x >= N ||
                    new_y < 0 || new_y >= N ||
                    data[encode(new_x, new_y)] == -1)
                    next[0][idx] = idx;
                else
                    next[0][idx] = encode(new_x, new_y);
            }
        }
    }

    for (int i = 1; i < MAX_LOG_K; i++) {
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                int idx = encode(x, y);
                if (next[i-1][idx] == -1) next[i][idx] = -1;
                else next[i][idx] = next[i-1][next[i-1][idx]];
            }
        }
    }
}

int query(int x, int y, int k) {
    int result = encode(x, y);
    int base = 0;

    while (k != 0) {
        if (k & 1)
            result = next[base][result];
        base++;
        k >>= 1;
    }

    return result;
}

int main() {
    int Q;
    while (scanf("%d %d", &N, &Q) != EOF) {
        for (int y = 0; y < N; y++) {
            char input[MAX_N + 1];
            scanf("%s", input);
            for (int x = 0; x < N; x++) {
                if (input[x] == 'x')
                    data[encode(x, y)] = -1;
                else
                    data[encode(x, y)] = input[x] - '0';
            }
        }

        init();

        while (Q--) {
            int x, y, k;
            scanf("%d %d %d", &x, &y, &k);

            int result = query(x, y, k);
            printf("%d %d\n", result % N, result / N);
        }
    }

    return 0;
}

amoshyc/ptc_2015_12_1_c.md

PTC 2015/12_1 C: Warehouse

題目

分析

AC Code