拒绝结论，直接打表

这种题目的中间结论——除非在看到题目之前就知道它——对于解题是没有意义的。只要能猜到最后的答案，就一定能以某种方式证明所有的结论。所谓的这些中间结论就变成了最终的答案的简单推论。比如本题中这个「局面的 SG 值是单个点的 SG 值的 Nim 和」就是这样的中间结论。

这样的中间结论不能成为思考的起点。

对于这种题目，思考的起点只能是打表。写一个暴力算 SG 值的代码：

CPP

constexpr int M = 4, N = 4;
auto check = [&](int val, int mai, int maj) -> bool {
    auto dfs = [&](auto&& dfs, int i, int j) -> void {
        if (!((val >> (i * N + j)) & 1)) return;
        val ^= 1 << (i * N + j);
        if (i) dfs(dfs, i - 1, j);
        if (i + 1 < M) dfs(dfs, i + 1, j);
        if (j) dfs(dfs, i, j - 1);
        if (j + 1 < N) dfs(dfs, i, j + 1);
    };
    dfs(dfs, mai, maj);
    return val == 0;
};
int idx = 0;
std::vector<int> state;
std::vector<int> nim(1 << (M * N));
for (int cr = 0; cr < (1 << (M * N)); ++cr) {
    std::vector<int> nxt;
    for (int pr = 0; pr < cr; ++pr) {
        int diff = cr ^ pr;
        int mai = 0, maj = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if ((diff >> (i * N + j)) & 1) {
                    mai = std::max(mai, i);
                    maj = std::max(maj, j);
                }
            }
        }
        if (((diff >> (mai * N + maj)) & 1) && check(diff, mai, maj)) {
            nxt.emplace_back(nim[pr]);
        }
    }
    std::sort(nxt.begin(), nxt.end());
    nxt.erase(std::unique(nxt.begin(), nxt.end()), nxt.end());
    for (; nim[cr] < (int)nxt.size() && nim[cr] == nxt[nim[cr]]; ++nim[cr]);
}

多尝试几组

M

和

N

，找找规律。（这一步要尽可能地压榨一下电脑性能，测一测例如

1\times 16

2\times 8

3\times 5

4\times 4

这种足够大的值，和例如

2\times 2

2\times 3

3\times 3

这种足够小的值，避免不完全归纳。）

首先，第一个发现是，SG 值过于混乱，没有明显的规律。（如果你这一步就猜出了前文所述的中间结论，那你可以直接跳过本文。）

但是，这种题目，没有明显的独立子游戏的结构，SG 值没用。只需要考察必败状态就行。所以，输出所有必败状态。

然后，就可以发现，必败状态的数量一定是

2

的幂次，且前几组必败状态呈现出明显的互相组合的特征。两个状态的组合，就是它们的异或值，其中，

H=0,T=1

。

于是，猜测所有

2^k

种必败状态都是

k

种必败状态的异或组合。那么，自然想到，只打印第

2^0,2^1,2^2,\cdots

种必败状态，看看这些 基本状态 长啥样。（这时候就体现按顺序打表的好处了。）（这一步需要通过打表验证猜测的正确性。）

这一步可以惊喜地发现，这些基本状态都只有两个

T

。

比如，

2\times 2

的必败状态是：

PLAINTEXT

0
HHH
HHH
=0

1
THT
HHH
=0

2
HTH
THH
=0

3
TTT
THH
=0

其中，第一个和第二个状态是基本状态，第三个是它们的组合。

对于更复杂的情形，可以打印出所有的只有两个

T

的状态，细品。将只有两个

T

的状态称为 简单状态。很容易想到，如果两个简单状态有一个公共的

T

，那么它们组合可以得到第三个简单状态。这是啥？这是传递性！传递性意味着啥？意味着出现在同一个简单状态的两个

T

的位置是等价的。也就是说，可以根据是否出现在同一个简单状态中，将所有位置分为若干类。

最后需要判断是否是必败状态，只要统计 每个等价类中的位置的个数是否为偶数 就可以了。

利用这些简单状态打个表，看一下位置的等价类具体长啥样。很容易发现，除了第

0

列和第

0

行，其余所有的位置，都是按照对角线划分等价类的。而边上的两排，新的等价类出现在

0,1,3,7,15,\dots

处。而且，对角线上的等价类和边上的等价类是可以对应上的。

由此，总结出计算等价类标号的方法为：

\begin{cases} \operatorname{lowbit}(x + y - 1), & \text{if }xy = 0,\\ x + y, &\text{otherwise}. \end{cases}

直接计算即可。

代码就很简单：

CPP

int main() {
    auto calc = [&](int x, int y) {
        return (!x || !y) ? __builtin_ctz(x + y + 1) : x + y;
    };
    int t;
    std::cin >> t;
    for (; t; --t) {
        int n, m;
        std::cin >> n >> m;
        std::bitset<200> st;
        for (int i = 0; i < n; ++i) {
            std::string s;
            std::cin >> s;
            for (int j = 0; j < m; ++j) {
                if (s[j] == 'T') {
                    st.flip(calc(i, j));
                }
            }
        }
        std::cout << (st.any() ? "-_-" : "=_=") << '\n';
    }
    return 0;
}

当然，这样分析的结果就是别的题解中算出的 SG 函数值的对数。

所有别的题解提到的中间结论和本文猜出来的中间结论都可以在归纳地证明了最后得到的 SG 函数值或等价类函数之后，再漫不经心地证明。

但是，如果事先不知道这些中间结论，那么，其实它们也不是啥必需品。这就是本文想说明的核心观点。

拒绝结论，直接打表

文章操作

相关推荐

评论

拒绝结论，直接打表