VOI 2011 COLOREC - Hình chữ nhật bốn màu

Overview

VOI 2011 COLOREC - Hình chữ nhật bốn màu

Đề bài: https://vnoi.info/problems/COLOREC/
Keywords: bit, dp
Ngôn ngữ: C++

solution.md

Với bài này ta gán mỗi màu cho một bit từ 0 đến 3, sau đó có thể quy hoạch động để đếm như sau:

Cố định 2 dòng i và j, ta đếm số hình chữ nhật 4 màu có cạnh nằm trên dòng i và j như sau:

Gọi F(c) là số cặp đỉnh có màu là c (c là tổng màu của 2 đỉnh đó) thì số hình chữ nhật 4 màu nhận được từ 2 đỉnh đó là F(15 - c).

Từ đó ta có thể dùng 3 vòng for để tính như trong code.

main.cpp

Open in Github • Download

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector< vector<int> > a(401, vector<int>(401, 0));
    while (n--) {
        int u, v, c; cin >> u >> v >> c;
        a[u + 200][v + 200] = 1 << (c - 1);
    }
#define rep(i, a, b) for (int i=a; i<=b; i++)
#define LL long long
    LL res = 0;
    rep(i, 0, 400) rep(j, 0, i) {
        vector<LL> f(16, 0);
        rep(k, 0, 400) if (a[i][k] && a[j][k] && a[i][k] != a[j][k]) {
            int c = a[i][k] | a[j][k];
            res += f[15 - c];
            f[c]++;
        }
    }
    cout << res;
    return 0;
}