Luogu 3631 [APIO 2011] 方格染色

• • • • • 傳送門
        • 思路
        • 參考代碼
        • 細節

傳送門

思路

  很不錯的一道題，用到的東西不深，但是要想到确實需要一定思維。

  一開始我想的是動态規劃，發現如果要設狀态需要知道一個格子左邊，上邊和左上邊三個格子的狀态。然後發現轉移時還要枚舉右上角是什麼，有點麻煩，但是應該可做。

  思考題目時，如果題目不是一眼題，即使沒有部分分，也應該從兩個方面去想：

1. 資料規模較小的情況（如果題目的正解是多項式算法，那麼最好往多項式算法去想，這時就不要糾結于指數級算法了）

2. 特殊情況，比如較少限制條件的情況

  但是我忘記了考慮特殊情況，于是就涼了。

  考慮一下，如果沒有人來塗色，答案将會是多少。考慮逐層構造，發現，當構造完第一行時（第一行本身沒有限制），第二行隻需要知道第一個列是什麼，就能唯一确定第二行。推廣一下，便能發現：隻要确定了第一行和第一列，那麼就能得到唯一的構造方法。這跟普及組的熄燈問題是類似的。

  現在我們把塗了的顔色加進來，看看會有哪些影響。影響無非就是原來的某個方案不符合已經塗色的内容。如果我們能夠通過已經塗色的倒推出還沒有塗色的，那麼問題也差不多解決了。

  下面就需要一些思維高度了。我們将題意轉換一下，将顔色抽象為 0 0 和 11，則一個 2×2 2 × 2 的方陣裡要麼出現了 3 3 個 00，要麼出現了 3 3 個 11。這等價于是說這個 2×2 2 × 2 的方陣異或和為 1 1 。

  對于 (x,y)(x,y>1)(x,y)(x,y>1)，我們将左上角為 (1,1)∼(x−1,y−1) ( 1 , 1 ) ∼ ( x − 1 , y − 1 ) 的所有 2×2 2 × 2 的方陣中的四個元素都選擇一遍（要重複選擇，因為異或的性質，選偶數次等價于沒有選），那麼這些元素的異或和顯然與 (x−1)×(y−1) ( x − 1 ) × ( y − 1 ) 有關（因為每個方陣的四個數的異或和為 1 1 ，共有 (x−1)×(y−1)(x−1)×(y−1) 個方陣）。若上式為奇數，則異或和為 1 1 ，否則為 00。又因為異或的性質，可以發現，這麼選等價于隻選擇了 (1,1),(x,1),(1,y),(x,y) ( 1 , 1 ) , ( x , 1 ) , ( 1 , y ) , ( x , y ) 這四個方格。換句話說，我們知道了這四個數的異或和！

  我們枚舉 (1,1) ( 1 , 1 ) 是 0 0 還是 11，就能得到兩個數的異或和，這可以用帶關系的并查集或者帶反集合的并查集解決。如果出現了非法的情況，說明無解。最終的答案取決于兩種顔色都能選的集合的個數。細節留給你們，我将會在參考代碼後給出。

參考代碼

醜

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int mod = int(1e9);
const int maxn = int(1e6) + 5;
int n, m, k;
int x[maxn];
int y[maxn];
int c[maxn];

struct DS
{
    int parent[maxn * 4];
    int color[maxn * 4];
    void clear(int size)
    {
        for (int i = 1; i <= size; i++)
            parent[i] = i;
        for (int i = 1; i <= size; i++)
            color[i] = -1;
    }
    int find(int x)
    {
        return x == parent[x] ? x : (x = find(parent[x]));
    }
    bool unite(int x, int y)
    {
        if (~color[find(x)] && ~color[find(y)] && color[find(x)] != color[find(y)])
            return false;
        color[find(x)] = std::max(color[find(x)], color[find(y)]);
        parent[find(y)] = find(x);
        return true;
    }
    bool judge(int x, int y)
    {
        return find(x) == find(y);
    }
} ds;

LL power(LL x, int y)
{
    LL ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}

void run()
{
    n = readIn();
    m = readIn();
    k = readIn();
    bool bset[2] = {};
    for (int i = 1; i <= k; i++)
    {
        x[i] = readIn();
        y[i] = readIn();
        c[i] = readIn();
        if (x[i] == 1 && y[i] == 1)
            bset[c[i]] = true;
    }
    for (int i = 1; i <= k; i++)
    {
        x[i]--;
        y[i]--;
    }

    int ans = 0;
    int delta = n + m - 2;
#define THIS(x) (x)
#define ANTI(x) ((x) + delta)
    if (!bset[0])
    {
        bool bOk = true;
        ds.clear(delta << 1);
        for (int i = 1; i <= k; i++)
        {
            if (!x[i] && !y[i])
                continue;
            else if (!x[i])
            {
                if (~ds.color[ds.find(THIS(y[i]))] &&
                    ds.find(THIS(y[i])) != c[i])
                {
                    bOk = false;
                    break;
                }
                ds.color[ds.find(THIS(y[i]))] = c[i];
                ds.color[ds.find(ANTI(y[i]))] = !c[i];
            }
            else if (!y[i])
            {
                if (~ds.color[ds.find(THIS(m - 1 + x[i]))] &&
                    ds.find(THIS(m - 1 + x[i])) != c[i])
                {
                    bOk = false;
                    break;
                }
                ds.color[ds.find(THIS(m - 1 + x[i]))] = c[i];
                ds.color[ds.find(ANTI(m - 1 + x[i]))] = !c[i];
            }
            else
            {
                if ((x[i] & 1) && (y[i] & 1))
                {
                    if (!ds.unite(THIS(m - 1 + x[i]), ANTI(y[i])) ||
                        !ds.unite(ANTI(m - 1 + x[i]), THIS(y[i])) ||
                        ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
                        ds.judge(THIS(y[i]), ANTI(y[i])))
                    {
                        bOk = false;
                        break;
                    }
                }
                else
                {
                    if (!ds.unite(THIS(m - 1 + x[i]), THIS(y[i])) ||
                        !ds.unite(ANTI(m - 1 + x[i]), ANTI(y[i])) ||
                        ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
                        ds.judge(THIS(y[i]), ANTI(y[i])))
                    {
                        bOk = false;
                        break;
                    }
                }
            }
        }
        if (bOk)
        {
            int ex = 0;
            for (int i = 1; i <= (delta << 1); i++)
            {
                if (ds.parent[i] != i) continue;
                if (!~ds.color[i])
                    ex++;
            }
            ex >>= 1;
            ans = (ans + power(2, ex)) % mod;
        }
    }
    if (!bset[1]) // copy and modify a !
    {
        bool bOk = true;
        ds.clear(delta << 1);
        for (int i = 1; i <= k; i++)
        {
            if (!x[i] && !y[i])
                continue;
            else if (!x[i])
            {
                if (~ds.color[ds.find(THIS(y[i]))] &&
                    ds.find(THIS(y[i])) != c[i])
                {
                    bOk = false;
                    break;
                }
                ds.color[ds.find(THIS(y[i]))] = c[i];
                ds.color[ds.find(ANTI(y[i]))] = !c[i];
            }
            else if (!y[i])
            {
                if (~ds.color[ds.find(THIS(m - 1 + x[i]))] &&
                    ds.find(THIS(m - 1 + x[i])) != c[i])
                {
                    bOk = false;
                    break;
                }
                ds.color[ds.find(THIS(m - 1 + x[i]))] = c[i];
                ds.color[ds.find(ANTI(m - 1 + x[i]))] = !c[i];
            }
            else
            {
                if (!((x[i] & 1) && (y[i] & 1)))
                {
                    if (!ds.unite(THIS(m - 1 + x[i]), ANTI(y[i])) ||
                        !ds.unite(ANTI(m - 1 + x[i]), THIS(y[i])) ||
                        ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
                        ds.judge(THIS(y[i]), ANTI(y[i])))
                    {
                        bOk = false;
                        break;
                    }
                }
                else
                {
                    if (!ds.unite(THIS(m - 1 + x[i]), THIS(y[i])) ||
                        !ds.unite(ANTI(m - 1 + x[i]), ANTI(y[i])) ||
                        ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
                        ds.judge(THIS(y[i]), ANTI(y[i])))
                    {
                        bOk = false;
                        break;
                    }
                }
            }
        }
        if (bOk)
        {
            int ex = 0;
            for (int i = 1; i <= (delta << 1); i++)
            {
                if (ds.parent[i] != i) continue;
                if (!~ds.color[i])
                    ex++;
            }
            ex >>= 1;
            ans = (ans + power(2, ex)) % mod;
        }
    }
    printOut(ans);
}

int main()
{
    run();
    return 0;
}           

細節

  （這取決于具體實作）首先看有沒有對 (1,1) ( 1 , 1 ) 染色，如果有，則隻有一種情況，否則 (1,1) ( 1 , 1 ) 的顔色有兩種情況。

  對于所有對第一行或者對第一列（除了 (1,1) ( 1 , 1 ) ）的染色，我們将所在被染位置所在集合進行标記，标記為染成了什麼顔色，相應的它的反集合也要進行标記。如果它已經被标記了并且顔色不同，說明方案不合法。

  進行并查集的合并操作時，我們同樣先檢查這兩個集合是否已經被染色。若已經被染色了，且染的顔色不同，說明不合法，否則将新的集合也染上相應顔色。

  最後，我們看并查集中有多少個集合沒有被打上染色标記。設該值為 x x ，顯然，由于反集合與原集合有對稱性，忽視反集合後應該有 x2x2 個集合沒有被打上染色标記。那麼在這種情況下的答案為 2x 2 x 。最終答案為（至多）兩種情況的答案之和。