校内模拟赛 coin

题意：

　　n*m的棋盘，每个格子可能是反着的硬币，正着的硬币，没有硬币，每次可以选未选择的一行或者未选择的一列，将这一行/列的硬币取反。如果没有可选的或者硬币已经全部正面，那么游戏结束。

　　最后一次操作的选手获得一分，如果最终棋盘上的硬币全是正面，那么双方都获得两分，问先手最多的多少分。

分析：

　　双方的最优策略一定是尽量使硬币全是正面，然后在考虑最后一次操作。

　　如果局面不可能使硬币全是正面，那么输出(n+m)&1。考虑如何判断。

　　如果（i,j）硬币，如果是正面，那么i->j连一条权值为0的边，否则连一条权值为1的。从一个点开始染色，使整张图满足边权等于两个点权的异或值。边权为0表示两个点要么同时选，要么同时不选，为1表示两个点只能选一个。

　　如果可以使硬币全是正面，然后对于一个联通块，可能是两种方式涂色，即确定一个点的颜色后，整个联通块也确定了。记录两个方式涂色后1的个数。

　　一共有三种可能，两种方式1的个数都是偶数，都是奇数，一个是偶数一个是奇数。那么偶偶与奇奇的没法改变，只有偶奇的根据第一个人选的这个联通块的颜色来确定。

　　那么讨论一下即可。

　　或者求sg值后异或起来。

代码

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#include<bitset>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int col[N], e[N][N], n, m, c1, c2;

vector<int> T[N];

char s[N][N];

bool dfs(int u) {

    col[u] ? c1 ++ : c2 ++;

    for (int i = ; i < T[u].size(); ++i) {

        int v = T[u][i];

        if (col[v] == -) {

            col[v] = col[u] ^ e[u][v];

            if (dfs(v)) return ;

        }

        else {

            if (col[v] != col[u] ^ e[u][v]) return ;

        }

    }

    return ;

}

void solve() {

    n = read(), m = read();

    for (int i = ; i <= n; ++i) scanf("%s", s[i] + );

    for (int i = ; i <= ; ++i) T[i].clear();

    memset(col, -, sizeof(col)); memset(e, , sizeof(e));

    for (int i = ; i <= n; ++i)

        for (int j = ; j <= m; ++j) {

            if (s[i][j] == 'e') continue;

            T[i].push_back(j + n); T[j + n].push_back(i);

            if (s[i][j] == 'o') e[i][j + n] = e[j + n][i] = ;

            else if (s[i][j] == 'x') e[i][j + n] = e[j + n][i] = ;

        }

    int ans1 = , ans2 = ;

    for (int i = ; i <= n + m; ++i) {

        if (col[i] == -) {

            col[i] = ;

            c1 = , c2 = ;

            if (dfs(i)) { cout << ((n + m) & ) << "\n"; return ; }

            c1 %= , c2 %= ;

            if (c1 && c2) ans1 ++;

            else if (c1 ^ c2) ans2 ++;

        }

    }

    ans1 %= , ans2 %= ;

    if (ans1 | ans2) puts("");

    else puts("");

    for (int i = ; i <= n + m; ++i) T[i].clear();

}

int main() {

    for (int T = read(); T --; solve());

    return ;

}

巴特西

校内模拟赛 coin

最新文章

热门文章