计蒜客 ACM训练联盟周赛第一场 Christina式方格取数思维

助手Christina发明了一种方格取数的新玩法：在n*m的方格棋盘里，每个格子里写一个数。两个人轮流给格子染色，直到所有格子都染了色。在所有格子染色完后，计算双方的分数。对于任意两个相邻（即有公共边）的格子，如果它们都被同一个人染色，那么这个人将得到这两个格子中的数的异或的分数。所有的分数加和计算。

现在，Christina用这个游戏来挑战你，想让你一败涂地，因此她总是采用最优策略使得她的分数尽可能地比你多。为了不输得太惨，你需要知道自己最多比助手多多少分数，或最少比助手少多少分数——也就是你的得分减去助手的得分最大是多少。（先后手由输入给定）

输入

第一行一个正整数T，表示数据组数。

对于每组数据，输入第一行为三个整数n,m,f。其中f为0或1，当f=0,你是先手，当f=1,你是后手。

接着输入n行，每行m个非负整数，表示格子里的数。

输入保证2<=n,m<=400。格子里的数均为不超过int范围的非负整数。

此题有多组数据，数据组数T<=10。

输出

对于每一组数据，输出一行一个整数：你的得分减去助手的得分的最大值。

SOURCE：codeforces

输出时每行末尾的多余空格，不影响答案正确性

样例输入

样例输出

题目来源

ACM训练联盟周赛

分析：这题目的关键是怎么选择下一步。

题目求分数的过程中，如果有相邻的分数则两分数需异或，所以每个点的分数并不是最后可以用来算总分的分数。

他们的实际分数应该是这个点的分数和相邻所有点分数的异或和

然后我们根据所有的异或和相隔着一人取一个分数就可以得到每个人所能得到的最大分数

因为实际运算的结果中并不能取到结果点的所有相邻点，只能取到一半，所以在计算结果时还要再除以二

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 4*1e2 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll mapn[maxn][maxn], a[maxn*maxn];
ll dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
bool cmp( ll x, ll y ) {
    return x > y;
}
int main() {
    ll t;
    cin >> t;
    while( t -- ) {
        ll n, m, f;
        memset( a, 0, sizeof(a) );
        cin >> n >> m >> f;
        for( ll i = 0; i < n; i ++ ) {
            for( ll j = 0; j < m; j ++ ) {
                cin >> mapn[i][j];
            }
        }
        ll cnt = 0;
        for( ll i = 0; i < n; i ++ ) {
            for( ll j = 0; j < m; j ++ ) {
                a[cnt] = 0;
                for( ll k = 0; k < 4; k ++ ) {
                    ll x = i + dx[k];
                    ll y = j + dy[k];
                    if( x >= 0 && x < n && y >= 0 && y < m ) {
                        a[cnt] += (mapn[i][j]^mapn[x][y]);
                    }
                }
                cnt ++;
                //cout << a[cnt-1] << " ";
            }
            //cout << endl;
        }
        sort( a, a + cnt, cmp );
        ll sum1 = 0, sum2 = 0;
        for( ll i = 0; i < cnt; i ++ ) {
            if( i&1 ) {
                sum2 += a[i];
            } else {
                sum1 += a[i];
            }
        }
        //因为要取到相邻的所有点的时候才能得到结果，然而在我们实际的运算
        //结果中只取到了这些结果点的一半相邻点，所以要除以二
        if( !f ) {
            cout << ( sum1 - sum2 ) / 2 << endl;
        } else {
            cout << ( sum2 - sum1 ) / 2 << endl;
        }
    }
    return 0;
}

彼时当年少，莫负好时光。