let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2011 PARIGAME - Trò chơi chẵn lẻ

solution.md

Bài này có thể giải bằng quy hoạch động.

Đặt \(F(i, j) = true\) nếu người đi trước có thể thắng với bảng giới hạn từ ô \((1, 1)\) tới \((i, j)\). Ta có:

  • Nếu ở \((i, j)\) ta có thể xoá cột (tức là tổng các số từ dòng 1 đến dòng i trên cột j là số chẵn), thì khi xoá cột, \(F(i, j) = not F(i, j-1)\)
  • Tương tự, khi xoá hàng thì \(F(i, j) = not F(i-1, j)\)

Ban đầu \(F(i, j) = false\), ta chọn kết quả tốt hơn trong 2 cách ở trên.

Ngoài ra, để phức tạp hoá vấn đề (và tăng tốc độ chương trình), ta có thể dùng tổng xor để thay cho tổng trong đề bài. Ngoài ra, mảng F cũng chỉ cần 2 dòng n cột là đủ để tính.

clearer.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> array(int n) {
    return vector<vector<int>>(n+1, vector<int>(n+1, 0));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        auto f = array(n), c = array(n), d = array(n);
#define rep(i,a,b) for(int i=a; i<=b; i++)
        rep(i, 1, n) rep(j, 1, n) {
            int x; cin >> x;
            d[i][j] = d[i][j-1] + x;
            c[i][j] = c[i-1][j] + x;
            if (~d[i][j] & 1) f[i][j] |= ~f[i-1][j];
            if (~c[i][j] & 1) f[i][j] |= ~f[i][j-1];
        }
        cout << (f[n][n]? "YES\n":"NO\n");
    }
}
main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> array(int n) {
    return vector<vector<int>>(2, vector<int>(n+1, 0));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        auto f = array(n), c = array(n), d = array(n);
#define rep(i,a,b) for(int i=a; i<=b; i++)
        rep(i, 1, n) rep(j, 1, n) {
            int x; cin >> x;
            d[i&1][j] = d[i&1][j-1] ^ x;
            c[i&1][j] = c[~i&1][j] ^ x;
            f[i&1][j] = 0;
            if (~d[i&1][j] & 1) f[i&1][j] |= ~f[~i&1][j];
            if (~c[i&1][j] & 1) f[i&1][j] |= ~f[i&1][j-1];
        }
        cout << (f[n&1][n]? "YES\n":"NO\n");
    }
}
Comments