Solution -「多校联训」取石子游戏

\(\mathcal{Description}\)

??Link.

??有 \(n\) 堆石子,第 \(i\) 堆有 \(x_i\) 个,Alice 每次只能从这堆中拿走 \(a_i\) 个石子,Bob 每次只能从这堆中拿走 \(b_i\) 个石子,不能操作者负。对于 \(i=1,2,\dots,n\),求只考虑 \([1,i]\) 的石子堆时,双方博弈的结果(有 Alice 必胜、Bob 必胜、先手必胜、后手必胜四种结果)。

??\(n\le10^5\)

\(\mathcal{Solution}\)

??我不会博弈啊……

??在这种非对称博弈问题中,一般不去研究 SG 函数,而是考虑“Alice 能比 Bob 多操作多少次”一类的问题。我们来逐步分析本题:

??结论:双方可以通过轮流操作同一堆石子,直至不存在这样石子堆,来达到最优策略。如果一方需要单独操作某一堆,另一方必然可以缠着(?)她,所以这个结论比较自然。

??所以只用考虑 \(r_i=x_i\bmod (a_i+b_i)\) 的取值

  • \(r_i<\min\{a_i,b_i\}\):双方无法操作,忽略;
  • \(\min\{a_i,b_i\}<r_i<\max\{a_i,b_i\}\):只有一方能操作,计入“能多操作几次”的贡献;
  • \(\max\{a_i,b_i\}\le r_i\):双方都能操作,但一方操作后另一方不能操作。

??先将所有第三类的操作记给 Alice,那么 Bob 选择一个 \(r_i\) 会使得 Alice 与 Bob 的操作次数差减少 \(\lfloor\frac{a_i}{r_i}\rfloor+\lfloor\frac{b_i}{r_i}\rfloor\),可见双方都会从大到小选择这一值,线段树维护选择结果即可。复杂度 \(\mathcal O(n\log n)\)

\(\mathcal{Code}\)

/*~Rainybunny~*/

#include <cstdio>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

typedef long long LL;

const int MAXN = 1e5;
int n, x[MAXN + 5], a[MAXN + 5], b[MAXN + 5];

struct SegmentTree {
    static const int MAXND = 4e6;
    int node, ch[MAXND][2], cnt[MAXND];
    LL sum[MAXND][2];

    inline void pushup( const int u ) {
        cnt[u] = cnt[ch[u][0]] + cnt[ch[u][1]];
        sum[u][0] = sum[ch[u][1]][0] + sum[ch[u][0]][cnt[ch[u][1]] & 1];
        sum[u][1] = sum[ch[u][1]][1] + sum[ch[u][0]][!( cnt[ch[u][1]] & 1 )];
    }

    inline void update( int& u, const int l, const int r, const int x ) {
        if ( !u ) u = ++node;
        if ( l == r ) {
            ++cnt[u];
            sum[u][0] = ( cnt[u] + 1ll >> 1 ) * l;
            sum[u][1] = 1ll * ( cnt[u] >> 1 ) * l;
            return ;
        }
        int mid = l + r >> 1;
        if ( x <= mid ) update( ch[u][0], l, mid, x );
        else update( ch[u][1], mid + 1, r, x );
        pushup( u );
    }
} sgt;

int main() {
    freopen( "C.in", "r", stdin );
    freopen( "C.out", "w", stdout );

    scanf( "%d", &n );
    rep ( i, 1, n ) scanf( "%d %d %d", &x[i], &a[i], &b[i] );
    
    LL dif = 0; int rt = 0;
    rep ( i, 1, n ) {
        int r = x[i] % ( a[i] + b[i] );
        if ( r >= a[i] && r >= b[i] ) {
            dif += r / a[i], sgt.update( rt, 1, 2e9, r / a[i] + r / b[i] );
        } else if ( r >= a[i] || r >= b[i] ) {
            dif += ( r >= a[i] ? 1 : -1 ) * ( r / a[i] + r / b[i] );
        }

        bool aw = dif - sgt.sum[rt][1] > 0, bw = dif - sgt.sum[rt][0] < 0;
        if ( !aw && !bw ) puts( "Second" );
        else if ( !aw ) puts( "Bob" );
        else if ( !bw ) puts( "Alice" );
        else puts( "First" );
    }
    return 0;
}

Solution -「多校联训」取石子游戏

上一篇:[原]零基础学习SDL开发之在Android使用SDL2.0显示BMP叠加图


下一篇:输入子系统分析