专栏文章

题解：CF2140E1 Prime Gaming (Easy Version)

SSUNCHAOYI废物生成器
CF2140E1题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miny6rf4
此快照首次捕获于
2025/12/02 10:17
3 个月前
此快照最后确认于
2025/12/02 10:17
3 个月前
查看原文

E1

首先 m=1m = 1 的时候只有一种全为 11 的情况，答案为 11。
接下来只需考虑 m=2m = 2 的情况。由于 n≤20n \le 20，考虑状压。
先钦定从左往右数第 ii 堆石头的信息存在长度为 nn 二进制从高位往低位数的第 ii 位上。由于 ci=1/2c_i = 1/2，我们设二进制某一位为 0/10/1 表示石头的数量为 1/21/2。
设 dpi,S,0/1dp_{i,S,0/1} 表示有 ii 堆石子，状态为 SS 且当前 Alice 为先手/后手的时候最终的那一堆石头的数量是否能为 22。则有转移方程：
{dpi,S,0=⋁S′∈F(S)dpi−1,S′,1dpi,S,1=⋀S′∈F(S)dpi−1,S′,0\begin{cases} dp_{i,S,0} = \bigvee_{S' \in \mathcal{F}(S)} dp_{i-1,S',1}\\ dp_{i,S,1} = \bigwedge_{S' \in \mathcal{F}(S)} dp_{i-1,S',0} \end{cases}
其中 F(S)\mathcal{F}(S) 表示 SS 中的某一位去掉以后的状态，这个可以进行预处理。
设 nxtS,inxt_{S,i} 表示状态为 SS 去掉第 ii 堆石头时形成的状态。但需要注意，这个状态 SS 在二进制下的长度一直是 nn，因此即使没有该位置的信息，直接置为 00 即可。由于是从高位往低位存储信息的，因此是形如 xxxxoyy→xxxxyy\texttt{xxxxoyy} \to \texttt{xxxxyy} 的合并。显然可以分为两个部分合并，写成如下式子（注意 ii 下标是 0-base 的）：
nxts,i=(⌊S2n−i⌋⋅2n−i)+(2⋅(S mod 2n−i−1))nxt_{s,i} = \left( \left\lfloor \frac{S}{2^{n-i}} \right\rfloor \cdot 2^{n-i} \right) + \left( 2 \cdot \left( S \bmod 2^{n-i-1} \right) \right)
也就是等价于如下表达式：
CPP
nxt[S][i] = ((S >> (n - i)) << (n - i)) | ((S & ((1 << (n - i - 1)) - 1)) << 1);
最后的答案为 2n+∑S=02n−1dpn,S,02^n + \sum \limits_{S = 0}^{2^n - 1} dp_{n,S,0}。
代码如下：
CPP
void solve ()
{
    int n = read (),m = read (),k = read (),ans = 0;
    vector <int> fl (n);
    for (int i = 1;i <= k;++i) fl[read () - 1] = 1;
    if (m == 1) {puts ("1");return;}
    vector <vector <int>> dp (1 << n,vector <int> (2,0)),ndp (1 << n,vector <int> (2,0)),nxt (1 << n,vector <int> (n + 1));
    for (int S = 0;S < (1 << n);++S)
        for (int i = 0;i < n;++i) nxt[S][i] = ((S >> (n - i)) << (n - i)) | ((S & ((1 << (n - i - 1)) - 1)) << 1);
    dp[0][0] = dp[0][1] = 0;dp[1 << (n - 1)][0] = dp[1 << (n - 1)][1] = 1;
    for (int i = 2;i <= n;++i)
    {
        for (int S = 0;S < (1 << i);++S)
        {
            ndp[S << (n - i)][0] = 0,ndp[S << (n - i)][1] = 1;
            for (int j = 0;j < i;++j) 
                if (fl[j]) ndp[S << (n - i)][0] |= dp[nxt[S << (n - i)][j]][1],ndp[S << (n - i)][1] &= dp[nxt[S << (n - i)][j]][0];
        }
        for (int S = 0;S < (1 << i);++S) dp[S << (n - i)][0] = ndp[S << (n - i)][0],dp[S << (n - i)][1] = ndp[S << (n - i)][1];
    }
    for (int S = 0;S < (1 << n);++S) ans += dp[S][0];
    printf ("%d\n",ans + (1 << n));
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...