题解 | 信息学奥赛一本通 取石子
取石子
https://ac.nowcoder.com/acm/contest/983/F
思路
不知道为什么好多大佬写的都是玄学的.
这里介绍从某位神仙博客看来的神奇推理.
过滤石子数为0的堆,我们把石子数为1的堆(以下称为单数堆)的个数记为,大于1的堆(以下称为复数堆)石子数总和+堆数-1记为
.
先手存在必胜策略当且仅当满足以下条件:
- 若
,需要满足
和
至少有一个是奇数.
- 若
,需要满足
.
下面我们来证明这个结论.
先证明的情况.
很明显最后时为必败态.
不管怎样你都有办法使复数堆不被直接取完(也就是最后都合并成一堆).
如果是都是奇数,你可以把一个单数堆与一个复数堆合并,这样子
都减一,变成必败态.
如果是奇数,
是偶数,你直接合并两个复数堆或者从复数堆取一个石子或者合并两个单数堆(当
时就得这么干),变成必败态.
如果是偶数,
是奇数,直接取一个奇数堆即可,变成必败态.
若果都是偶数,不管怎么取,都会变成必胜态.
如果,如果
,直接取一个单数堆,如果
,合并两个单数堆.
至此证明完成.
复杂度是.
代码
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
flg ? x = -x : x;
}
clock_t t_bg, t_ed;
int T, N, x, s, c;
signed main(){
t_bg = clock();
read(T);
while( T-- ){
read(N), s = c = 0;
fp( i, 1, N ){
read(x);
if ( x == 1 ) ++c;
else if ( x > 1 ) s += x + 1;
} if ( s ) --s;
if ( s > 2 ) printf( (s&1)||(c&1) ? "YES\n" : "NO\n" );
else printf( c % 3 ? "YES\n" : "NO\n" );
}
t_ed = clock();
fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
return 0;
} 
