题解 CF1396B 【Stoned Game】

又抢到了截止到2021年1月13日16点41分一道题的[最优解](https://www.luogu.com.cn/record/list?pid=CF1396B&orderBy=1&status=&page=1)，发篇题解纪念下。基础博弈论题目。 ## 题目大意 有 $n$ 堆石子，每堆分别有 $a_i$ 个石子。 两者轮流取其中一个石子。但不能取上次对手取过的那一堆。特殊的，第一次取可以取任何一堆的石子。 当前先手取完要取的石子之后使对手无路可走时，先手获胜。 ## 大体思路 1. 首先进行特判： 记 $sum=\sum\limits_{i=1}^n a_i$，则若有一堆石子比剩余所有石子都多，即 $\max\limits_{i=1}^n\{a_i\}>sum-\max\limits_{i=1}^n\{a_i\}$，则先手只需一直取这堆石子必胜。 2. 若不存在上述情况： 显然，最终必然仅存在一堆石子，参考 @[SSerxhs](https://www.luogu.com.cn/user/29826) 的证明方法： >考虑最终状态必定只有一堆石子，现证明双方都可以通过设定操作策略为取走目前可取的石子最多的那堆做到最后一堆石子被拿干净。 >假设不被拿干净，必定是出现了最多石子的那堆石子数目大于其他之和的状态（例如最终状态），逆推回去可以发现每两次取石子就有一个人取了这堆，逆推至初始状态与“否则”矛盾，不成立。 可得结论：当 $\max\limits_{i=1}^n\{a_i\}\le sum-\max\limits_{i=1}^n\{a_i\}$，所有石子均被取完。因此只需判断 $sum$ 的奇偶性，若为奇数则先手取胜，否则后手取胜。 ## 完整代码 ```cpp #include<bits/stdc++.h> using namespace std; #define rep(ii,aa,bb) for(re int ii=aa;ii<=bb;ii++) #define Rep(ii,aa,bb) for(re int ii=aa;ii>=bb;ii--) typedef long long ll; typedef unsigned long long ull; const int maxn=105; namespace IO_ReadWrite{ #define re register #define gg getchar() template <typename T> inline void read(T &x){ x=0;re T f=1;re char c=gg; while(c>57||c<48){if(c=='-') f=-1;c=gg;} while(c>=48&&c<=57){x=(x<<1)+(x<<3)+(c^48);c=gg;} x*=f;return; } inline void ReadChar(char &c){ c=gg; while(!isalpha(c)) c=gg; } template <typename T> inline void write(T x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar('0'+x%10); } template <typename T> inline void writeln(T x){write(x);putchar('\n');} } using namespace IO_ReadWrite;//习惯卡常 int a[maxn],n,T; int main(){ read(T); while(T++){//好多组数据 int sum=0;//记录Σa[i] read(n);rep(i,1,n) read(a[i]),sum+=a[i];//输入 sort(a+1,a+n+1,greater<int>());//从大到小排序 if(a[1]>sum-a[1]) puts("T");//特判 else if(sum&1) puts("T"); else puts("HL");//判断奇偶 } return 0;//完美 } ```