题解 | 信息学奥赛一本通 取石子游戏

思路

首先,函数什么的不怎么管用.(亏我想了好久)
这题做法十分神奇.
设表示在区间[l,r]的石子左边添加一堆L[i][j]的石子会导致先手必败,如果没有该种策略值为0.与此同理.
易证决策不可能吧同时存在多个.
预处理边界.因为相同的两堆会导致这样的情况:先手在一堆取多少,后手就在后一堆取多少,先手明显必败.
然后中间的决策可以推过去.设

1. 
   这样是一个必败态,不管在左边放怎样的石子堆先手都可以取完这一堆引来必败态,所以.
2. 
   .先手在某一边取多少(未取完),后手就在另一边取多少如果先手把一边取完了,后手面临的情况可以看做的石子在左边或右边放一堆石子,且不为或.前面说过,必败的放石子方案是唯一的,因此这个局面是必胜的.
3. 
   .然后执行以下几个策略.
   若先手取左边,并且,我们维持状态即可(也就是先手取多少,就在另一堆取多少).
   若先手取左边,并且,我们把右边那堆取光,然后先手就面临必败态了.
   若先手取左边,并且(未取光),我们把右边那堆也取到相同数目的石子,这样局面就相当于且先后手各取完一轮时,先手必输.
   若先手取左边且取光,右边很明显不会为,是必胜态.
   若先手取右边,并且未取光,我们把直接把左边取成与右边相同即可,这样就相当于且先后手各取完一轮的状态.
   若先手取右边且取光,我们把左边取到,然后就是必败态了.
4. 
   分析同上..
5. 
   .分析也是类似的.如果还是,维持状态.
   如果,就变成状态2.
   否则会变成状态3或4,对应地变成先手取剩的石子+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;
const int MAXN = 1e3 + 5;
int T, N, a[MAXN];
int L[MAXN][MAXN], R[MAXN][MAXN];

signed main(){
    t_bg = clock();
    read(T);
    while( T-- ){
        read(N);
        fp( i, 1, N ) read(a[i]), L[i][i] = R[i][i] = a[i];
        fp( len, 2, N ) fp( i, 1, N - len + 1 ){
            int j = i + len - 1, l, r, x;
            l = L[i][j - 1], r = R[i][j - 1], x = a[j];
            if ( x == r ) L[i][j] = 0;
            else if ( ( x < l && x < r ) || ( x > l && x > r ) ) L[i][j] = x;
            else if ( l <= x && x < r ) L[i][j] = x + 1;
            else L[i][j] = x - 1;
            l = L[i + 1][j], r = R[i + 1][j], x = a[i];
            if ( l == x ) R[i][j] = 0;
            else if ( ( x < l && x < r ) || ( x > l && x > r ) ) R[i][j] = x;
            else if ( r <= x && x < l ) R[i][j] = x + 1;
            else R[i][j] = x - 1;
        } printf( a[1] == L[2][N] ? "0\n" : "1\n" );
    }
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}