P9772 [HUSTFC 2023] 网格染色 题解

linyukun · 2023-10-23 23:23:03 · 题解

1. 前言

本文的分析会比较通俗，自己要多去思考，麻烦一定 仔细全部看完，有异议、不懂或认为可以优化请私信反馈呢。

2. 题目解析：

拿到这种题目，我们首先瞎猜手动画图。在模拟了 1 到 5 之后，发现蓝赢，此时基本上就可以输出了，但是我们最好再理论证明一次。

• 根据“第四条边的人得分”，我们可知画第三边是劣手，也就是不优，应尽量避免。

• 前两条边其实无所谓颜色，但是，通过模拟和感性理解，我们发现，红蓝在最佳策略，不画第三边的情况下，总会进入所有正方形都画了两边的窘境。

• 这种情况下，蓝色再与红色下“模仿棋”，也就是红色涂最外层蓝就跟上，红色涂内部蓝色就补上。这样下到最后边数肯定是二的倍数，所以红色必然画出第三边，也就是做出了不优的选择，而蓝色依然保持他的优势。

• 蓝色的得分在每一个联通的区间里最坏也会比红多一分，因为对于最后一个正方形的“封口工作”是蓝色进行。

• 当红色下了第三边，蓝色就可以封口，这样就比红色多一分。只有红色落下第三边，蓝色必然可以得分。而红色的先手成了劣势，这让他不可能扳平比分。

• 所以蓝色必胜。

3. 提示要点：

• 剖析胜负条件，看透博弈本质。
• 自信点，答案有时候就是离谱。

  4. 代码写作：

  理论存在，实践开始的瞬间就结束了。

  #include<bits/stdc++.h>
  using namespace std;
  int main(){
  cout<<"Kelin";
  return 0;
  }

5. 总结鸣谢：

不错的一道思维题，训练了推理能力，博弈的不错入门。
感谢管理大大的的审核。