题解：P14256 平局（draw）

验题人题解。

以下讨论都在模

3

意义下进行。

约定石头为

2

，剪刀为

1

，布为

0

，即

x

击败

(x-1)

。

两个观察：

如果出现两个相同的手势，则可以直接消去一个。
如果出现形如 $x,x-1,x$ 的情况，则可以替换成一个 $x$ 。

证明考虑如果要让中间的 $x-1$ 对答案有贡献，则左右两边的 $x$ 必须损失一个，答案不会变大。

把这两种情况全部消去，剩下的数必定形如：

\underbrace{\dots,x-2,x-1}_a,x,\underbrace{x-1,x-2,\dots}_b

考虑在

x

前面有

a

项，

x

后面有

b

项，则答案为

\left \lfloor \frac a3 \right \rfloor + \left \lfloor \frac b3 \right \rfloor + \left [ a\equiv b\equiv 2 \pmod{3} \right ]

，容易手模出来。

现在我们再观察前面的两种情况，如果我们已经知道前

i

个人的

a,b

值，考虑下一个人：

相当于直接消去，对 $a,b$ 无影响。
让 $b\gets b-1$ 。

于是我们就可以直接 dp 了。设当前考虑到

i

，第

i

个人的选择出

x

，当前的

a

和

b

。考虑下一个人出

x'

：

$x=x'$ ：发生上面第一种情况， $a'=a,b'=b$ ；
$x+1=x'$ ：如果 $b=0$ ，则不会发生上面的第二种情况， $a'=a+1,b'=b$ ；否则 $a'=a,b'=b-1$ 。
$x-1=x'$ ： $a'=a,b'=b+1$ 。

每当发生消去时，答案要额外

+1

，记录方案数和当前的答案，即可做到

O(n^3)

。注意到

a

不降，于是只用记录

a \bmod 3

即可，时间复杂度

O(n^2)

。

代码

CPP

constexpr int N = 3005;
char s[N];
Mint f[N][3][N][3], g[N][3][N][3];
vi possible[N];

// signed main() {
int main() {
  // freopen("draw3.in", "r", stdin);
  // freopen(".out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  cin >> reinterpret_cast<char (&)[N]>(s[1]);
  for (int i = 1; i <= n; i++) s[i] -= '0';
  for (int i = 1; i <= n; i++) {
    for (auto j : {0, 1, 2})
      if (s[i] >> j & 1) possible[i].pb(j);
  }
  for (auto x : possible[1]) g[1][0][0][x] = 1;
  for (int i = 1; i < n; i++) {
    for (auto x : possible[i]) {
      for (int upl = 0; upl < 3; upl++) {
        for (int downl = 0; downl < i; downl++) {
          auto &F = f[i][upl][downl][x], &G = g[i][upl][downl][x];
          if (F != 0 || G != 0) {
            for (auto nx : possible[i + 1]) {
              if (x == nx) {
                g[i + 1][upl][downl][nx] += G;
                f[i + 1][upl][downl][nx] += F + G;
              } else if ((x + 1) % 3 == nx) {
                if (downl == 0) {
                  g[i + 1][(upl + 1) % 3][downl][nx] += G;
                  f[i + 1][(upl + 1) % 3][downl][nx] += F + G * (upl == 2);
                } else {
                  g[i + 1][upl][downl - 1][nx] += G;
                  f[i + 1][upl][downl - 1][nx] += F + G;
                }
              } else {
                g[i + 1][upl][downl + 1][nx] += G;
                f[i + 1][upl][downl + 1][nx] += F;
              }
            }
          }
        }
      }
    }
  }
  Mint ans = 0;
  for (auto x : possible[n]) {
    for (int upl = 0; upl < 3; upl++) {
      for (int downl = 0; downl < n; downl++) {
        auto &F = f[n][upl][downl][x], &G = g[n][upl][downl][x];
        ans += F + G * (downl / 3 + (upl == 2 && downl % 3 == 2));
      }
    }
  }
  cout << ans << endl;

  return 0;
}

题解：P14256 平局（draw）

文章操作

相关推荐

评论

题解：P14256 平局（draw）