P12456 Sol || 别样的差分大战

CarroT1212 · 2025-10-18 19:51:26 · 题解

选手题解。

:::info[题意]

• 有 n 个人在石头剪刀布，每个人只会出固定的手势。你每次可以让相邻两个人石头剪刀布决斗，输的人被删除，如果平局就随便删除一个。求过程中的最多平局数。

现在你知道每个人分别是否可能出石头、剪刀、布，请对所有可能的出手方案求以上问题的答案之和。n\le 3000。 :::

（先说最终做法，场上的一些尝试和观察会在文后补充）

以下内容用 0 表示石头，1 表示剪刀，2 表示布。

看上去是 DP 套 DP 状物。我们需要对内层问题找到一个非常强的做法，强到几乎和最优化没有任何关系。这样才能做。

把每个人的决策看成 012 序列 a_{[1,n]}。那就形如如果两个相邻决斗的 x,y 满足 (x+1)\bmod 3=y，那么 x 会击败 y。

胡思乱想后可以感受到一个结论：

• 如果某一时刻序列里有相邻的相同元素，那么最优情况下可以选择立刻让他们决斗得到平局，直到所有相邻元素都不同。

:::info[简单证明] 如果有两个相邻的相同元素 x,y，你没有选择第一时间让 x,y 决斗得到平局。那么假设下一次是 x 和另外一个元素 z 决斗，如果 x 输了，那你显然不如干脆让 x 跟 y 打个平局。如果 x 赢了，那你先把 x,y 决斗了合并起来再去跟那个元素打，也一样能赢。 :::

另外发现，上面这个同余的击败条件比较适合做差分。对这个 012 序列差分得到 b_{[1,n-1]}。在同余意义下可以看成 b 只有 -1,0,+1。

考虑一次决斗对 b 造成的影响，显然只会影响到 b_i 的相邻三个元素 x,y,z。

:::info[具体的讨论]

• 根据结论我们先把 b 里的 0 删除，不考虑带 0 的情况。
• 如果这次决斗左边获胜，那么 y=1。
  • 如果 z 为 1，那么 y,z 会合并为 -1。
  • 如果 z 为 -1，那么 y,z 会合并为 0，可直接删去。
• 如果这次决斗右边获胜，那么 y=-1。
  • 如果 x 为 1，那么 x,y 会合并为 0，可直接删去。
  • 如果 x 为 -1，那么 x,y 会合并为 1。
• :::

综上，b 上有效的操作只有：

• 删去初始就存在的 0，答案 +1；
• 删去相邻的 +1,-1，答案 +1；
• 将两个相邻 +1 变为一个 -1；
• 将两个相邻 -1 变为一个 +1。

这就比较类似一个括号匹配状物了，尝试用栈处理。考虑如下做法：

• 维护一个栈。遍历初始的 b_i。
• 若 b_i=0，答案 +1。
• 否则如果 b_i=1 或栈为空，直接将 b_i 放入栈。
• 否则 b_i=-1：
  • 若栈顶为 1，则让它们匹配，弹栈，答案 +1；
  • 否则栈顶为 -1。因为匹配要求 -1 在右侧，那么堆在左侧的 -1 肯定是不优的，不如直接把栈顶和这个新 -1 合成一个 +1。
• 整个过程结束后，如果栈内还有 1，则可以每三个 1 合成一对匹配（两个 +1 变 -1）。

这样做就可以得到最优答案。可以说是全方位的肉眼可见的优秀，看着就很有前途。

:::success[此算法的代码]

ll get(ll x,ll y) { return (y-x+4)%3-1; }
void solve() {
    for (ll i=1;i<n;i++) b[i]=get(a[i],a[i+1]);
    stack<ll> st; ll res=0;
    for (ll i=1;i<n;i++) {
        if (b[i]==0) res++;
        else if (!st.size()) st.push(b[i]);
        else if (b[i]==1) st.push(1);
        else {
            if (st.top()==1) st.pop(),res++;
            else st.pop(),st.push(1);
        }
    }
    ll cnt=0; while (st.size()&&st.top()==1) cnt++,st.pop();
    res+=cnt/3;
}

:::

它最厉害的地方在于，整个过程中我们只关心栈内有多少个 1 以及栈底是不是 -1（显然 -1 不会超过一个且一定在栈底），所以容易设状态套上外层 DP。

具体来说，dp_{i,j,0/1,0/1/2} 表示做了 a_{[1,i]}，栈内有 j 个 1，栈底是不是 -1，a_i 是多少，这种情况下有多少种手势方案，以及这些方案的当前平局数之和。做类似的转移即可。

大常数 O(n^2)，足以通过。

:::success[正解代码]

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9,N=3007,P=1e9+7;
const ll J=1e18;
int n,s[N],a[N],b[N],ans;
char str[N];
pii dp[N][N][2][3];
int get(int x,int y) { return (y-x+4)%3-1; }
void add(pii &x,pii y) { (x.fi+=y.fi)%=P,(x.se+=y.se)%=P; }
void mian() {
    scanf("%d%s",&n,str+1);
    for (int i=1;i<=n;i++) {
        s[i]=str[i]-'0';
        int x=s[i]&1,y=s[i]>>1&1;
        s[i]=s[i]&4|x<<1|y;
    }
    for (int d=0;d<3;d++) if (s[1]>>d&1) dp[1][0][0][d]={1,0};
    for (int i=2;i<=n;i++) for (int j=0;j<i-1;j++) for (int x=0;x<2;x++) for (int y=0;y<3;y++) {
        for (int d=0;d<3;d++) if (s[i]>>d&1) {
            pii w=dp[i-1][j][x][y]; int b=get(y,d);
            if (b==0) add(dp[i][j][x][d],{w.fi,(w.se+w.fi)%P});
            else if (!j&&!x) {
                if (b==1) add(dp[i][1][0][d],w);
                else add(dp[i][0][1][d],w);
            }
            else if (b==1) add(dp[i][j+1][x][d],w);
            else {
                if (j) add(dp[i][j-1][x][d],{w.fi,(w.se+w.fi)%P});
                else add(dp[i][1][0][d],w);
            }
        }
    }
    for (int j=0;j<n;j++) for (int x=0;x<2;x++) for (int y=0;y<3;y++) {
        pii w=dp[n][j][x][y];
        (ans+=(w.se+1ll*w.fi*(j/3)%P)%P)%=P;
    }
    cout<<ans;
}
bool ORY; int main() {
//  freopen("draw6.in","r",stdin);
//  freopen("draw.out","w",stdout);
//  while (1)
//  int t; for (scanf("%d",&t);t--;)
    mian();
    cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
    return 0;
}

:::

:::warning[场上其它的一些碎碎思路]

内层问题一个比较容易想到的 DP 是 dp_{l,r,0/1/2} 表示 [l,r] 内决出了一个胜者，他出的是石头/剪刀/布时，这一部分的最大平局数。容易 O(n^3) 转移。

但是这个玩意作为内层 DP 根本没法往外套，因为这是个最优化，想对于一个方案求出正确结果就需要几乎所有的 DP 信息，这也太烂了！

观察：

• 这个问题很难像一些括号序列问题那样处理，原因主要在于，石头剪刀布是个循环相克的过程，我们对相同手势的匹配如何分层完全没有任何头绪。
• 做法应该跟 3 有比较大的关系，不然这题完全可以不止石头剪刀布，还能再塞什么甜甜圈独角兽之类的东西进来。
  • 其实我主要还是顺着这个想到差分的。

:::

建议尝试：AGC022E