专栏文章

P12456 Sol || 别样的差分大战

CCarroT1212菜萝卜
P14256题解参与者 5已保存评论 5

文章操作

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

当前评论
5 条
当前快照
1 份
快照标识符
@minkml8m
此快照首次捕获于
2025/12/02 03:57
3 个月前
此快照最后确认于
2025/12/02 03:57
3 个月前
查看原文
选手题解。
题意
  • 有 nn 个人在石头剪刀布，每个人只会出固定的手势。你每次可以让相邻两个人石头剪刀布决斗，输的人被删除，如果平局就随便删除一个。求过程中的最多平局数。
现在你知道每个人分别是否可能出石头、剪刀、布，请对所有可能的出手方案求以上问题的答案之和。n≤3000n\le 3000。
（先说最终做法，场上的一些尝试和观察会在文后补充）
以下内容用 0 表示石头，1 表示剪刀，2 表示布。
看上去是 DP 套 DP 状物。我们需要对内层问题找到一个非常强的做法，强到几乎和最优化没有任何关系。这样才能做。
把每个人的决策看成 012 序列 a[1,n]a_{[1,n]}。那就形如如果两个相邻决斗的 x,yx,y 满足 (x+1) mod 3=y(x+1)\bmod 3=y，那么 xx 会击败 yy。
胡思乱想后可以感受到一个结论：
  • 如果某一时刻序列里有相邻的相同元素，那么最优情况下可以选择立刻让他们决斗得到平局，直到所有相邻元素都不同。
简单证明
如果有两个相邻的相同元素 x,yx,y，你没有选择第一时间让 x,yx,y 决斗得到平局。那么假设下一次是 xx 和另外一个元素 zz 决斗，如果 xx 输了，那你显然不如干脆让 xx 跟 yy 打个平局。如果 xx 赢了，那你先把 x,yx,y 决斗了合并起来再去跟那个元素打，也一样能赢。
另外发现，上面这个同余的击败条件比较适合做差分。对这个 012 序列差分得到 b[1,n−1]b_{[1,n-1]}。在同余意义下可以看成 bb 只有 −1,0,+1-1,0,+1。
考虑一次决斗对 bb 造成的影响，显然只会影响到 bib_i 的相邻三个元素 x,y,zx,y,z。
具体的讨论
  • 根据结论我们先把 bb 里的 00 删除，不考虑带 00 的情况。
  • 如果这次决斗左边获胜，那么 y=1y=1。
    • xx 不会变。
    • 如果 zz 为 11，那么 y,zy,z 会合并为 −1-1。
    • 如果 zz 为 −1-1，那么 y,zy,z 会合并为 00，可直接删去。
  • 如果这次决斗右边获胜，那么 y=−1y=-1。
    • 如果 xx 为 11，那么 x,yx,y 会合并为 00，可直接删去。
    • 如果 xx 为 −1-1，那么 x,yx,y 会合并为 11。
    • zz 不会变。
  • xx 不存在或者 zz 不存在的情况（决斗的两个人在边上）是不重要的。
综上，bb 上有效的操作只有：
  • 删去初始就存在的 00，答案 +1+1；
  • 删去相邻的 +1,−1+1,-1，答案 +1+1；
  • 将两个相邻 +1+1 变为一个 −1-1；
  • 将两个相邻 −1-1 变为一个 +1+1。
这就比较类似一个括号匹配状物了，尝试用栈处理。考虑如下做法：
  • 维护一个栈。遍历初始的 bib_i。
  • 若 bi=0b_i=0，答案 +1+1。
  • 否则如果 bi=1b_i=1 或栈为空，直接将 bib_i 放入栈。
  • 否则 bi=−1b_i=-1：
    • 若栈顶为 11，则让它们匹配，弹栈，答案 +1+1；
    • 否则栈顶为 −1-1。因为匹配要求 −1-1 在右侧，那么堆在左侧的 −1-1 肯定是不优的，不如直接把栈顶和这个新 −1-1 合成一个 +1+1。
  • 整个过程结束后，如果栈内还有 11，则可以每三个 11 合成一对匹配（两个 +1+1 变 −1-1）。
这样做就可以得到最优答案。可以说是全方位的肉眼可见的优秀，看着就很有前途。
此算法的代码CPP
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;
}
它最厉害的地方在于，整个过程中我们只关心栈内有多少个 11 以及栈底是不是 −1-1（显然 −1-1 不会超过一个且一定在栈底），所以容易设状态套上外层 DP。
具体来说，dpi,j,0/1,0/1/2dp_{i,j,0/1,0/1/2} 表示做了 a[1,i]a_{[1,i]}，栈内有 jj 个 11，栈底是不是 −1-1，aia_i 是多少，这种情况下有多少种手势方案，以及这些方案的当前平局数之和。做类似的转移即可。
大常数 O(n2)O(n^2)，足以通过。
正解代码CPP
#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;
}
场上其它的一些碎碎思路
内层问题一个比较容易想到的 DP 是 dpl,r,0/1/2dp_{l,r,0/1/2} 表示 [l,r][l,r] 内决出了一个胜者，他出的是石头/剪刀/布时，这一部分的最大平局数。容易 O(n3)O(n^3) 转移。
但是这个玩意作为内层 DP 根本没法往外套，因为这是个最优化，想对于一个方案求出正确结果就需要几乎所有的 DP 信息，这也太烂了！
观察：
  • 这个问题很难像一些括号序列问题那样处理，原因主要在于，石头剪刀布是个循环相克的过程，我们对相同手势的匹配如何分层完全没有任何头绪。
  • 做法应该跟 33 有比较大的关系，不然这题完全可以不止石头剪刀布，还能再塞什么甜甜圈独角兽之类的东西进来。
    • 其实我主要还是顺着这个想到差分的。
建议尝试：AGC022E

评论

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

正在加载评论...