题解：P14256 平局（draw）

Petit_Souris · 2025-10-19 17:07:46 · 题解

::::info[中文题解]

第一步显然需要考虑对于给定的序列，计算最大平局问题的答案。

对于相邻的两个人的胜负关系，用 <, =, > 表示。

首先可以观察到对于序列中初始的所有 =，都可以立即合并，获得 1 的贡献，因为如果不合并这两个人后续合并至多因此多得到 1 的贡献，不优于原方案。

现在考虑一次操作对胜负序列的影响，显然会影响到相邻的两个符号。

考虑不同情况的合并：

容易发现我们只有两种得到 = 的方式：

• 将 >< 合并成 =；

• 将 >>> 合并成 ><，再合并成 =。

因此可以从左往右扫描，维护一个栈。

如果当前扫描到的元素是：

• - 若栈为空，直接加入栈中； - 若栈顶为 $>$，显然直接合成 $=$ 最优，因为 $<$ 和后面的东西不能直接合成 $=$。给答案 $+1$ 并删除。 - 若栈顶为 $<$，这个 $<$ 同理后面就没用了，不如直接 $<<$ 合成 $>$。

因此我们的栈一定形如 >>\dots >> 或 <>>\dots >>。

那么就很容易 dp 了：设 f_{i, j, 0/1, 0/1/2} 表示前 i 个人，目前栈中有 j 个 >，栈底是否有 <，上一个人出的是剪刀石头布中的哪一个，方案数以及贡献总和。转移枚举 3 种下个人的情况分类讨论。

最后剩下的 j 个 > 可以合成 \lfloor\frac{j}{3}\rfloor 个 =。

时间复杂度 \mathcal O(n ^ 2)，空间复杂度 \mathcal O(n)（滚动数组）。

::::

::::info[English Editorial]

The first step is to consider a given sequence, and calculate the maximum possible number of ties.

For every adjacent pairs, we use notations <, =, > to represent their relationship.

First of all, we can observe that all = can be directly removed, and contribute 1 to the final answer. The proof is simple: at most 1 potential contribution to the final answer can be obtained if we use this = to build other =, while we already lose 1 contribution when breaking it. So it can't be better than the original solution.

Now we can move on to the case without =. An operation will affect two consecutive relationships:

Thus, the only 2 ways to get a = is:

• Merging >< into a =;

• Merging >>> into ><, then into a =.

We can process the sequence from left to right, store the current data in a stack. Do some casework on the current element:

• If it is a =, remove it directly and add 1 to the answer;

• If it is a >, push it into the stack;

• If it is a <:

  • If the stack is empty, push it into the stack;

  • If the top of stack is >, we can merge them into a =, since two or more elements are needed for an extra = with this <, which is worse.

  • If the top of stack is <, since if we continue using the current <, the top of the stack is wasted. Thus we'd better merge them into a >.

It is obvious that the stack will look like >>\dots >> or <>>\dots >> eventually.

We can calculate the contribution using dynamic programming: f_{i, j, 0/1, 0/1/2} means that we are currently handling the i-th person, with j > in the stack, 0 or 1 < at the bottom of the stack, and the last person is rock / paper / scissors. We can enumerate three different states for transition.

The number of ways reaching this state, and the total contribution of a given state should be recorded at the same time.

Finally, the > can be merged three by three into =, contributing \lfloor\frac{j}{3}\rfloor to the final answer.

Time complexity: \mathcal O(n ^ 2).

Memory complexity: \mathcal O(n), since f_{i} only depends on f_{i - 1}.

::::

::::success[参考实现 / Implementation]

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 3e3 + 9, Mod = 1e9 + 7;
ll n, a[N];
char str[N];
struct Dat {
    ll f, g;
} dp[2][N][2][3];
bool cur;
bool Med;
int main() {
    // freopen("draw.in", "r", stdin);
    // freopen("draw.out", "w", stdout);
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read(), scanf("%s", str + 1);
    rep(i, 1, n) a[i] = str[i] - '0';
    rep(i, 0, 2) {
        if((a[1] >> i) & 1) dp[cur][0][0][i] = {1, 0};
    }
    rep(i, 1, n - 1) {
        rep(j, 0, i + 2) {
            rep(k, 0, 1) {
                rep(l, 0, 2) dp[cur ^ 1][j][k][l] = {0, 0};
            }
        }
        rep(j, 0, i) {
            rep(k, 0, 1) {
                rep(l, 0, 2) {
                    ll F = dp[cur][j][k][l].f, G = dp[cur][j][k][l].g;
                    if(!F && !G) continue;
                    rep(o, 0, 2) {
                        if(!((a[i + 1] >> o) & 1)) continue;
                        ll d = (l - o + 3) % 3;
                        if(d == 0) {
                            dp[cur ^ 1][j][k][o].f = (dp[cur ^ 1][j][k][o].f + F) % Mod;
                            dp[cur ^ 1][j][k][o].g = (dp[cur ^ 1][j][k][o].g + F + G) % Mod; 
                        }
                        else if(d == 1) {
                            dp[cur ^ 1][j + 1][k][o].f = (dp[cur ^ 1][j + 1][k][o].f + F) % Mod;
                            dp[cur ^ 1][j + 1][k][o].g = (dp[cur ^ 1][j + 1][k][o].g + G) % Mod; 
                        }
                        else {
                            if(j) {
                                dp[cur ^ 1][j - 1][k][o].f = (dp[cur ^ 1][j - 1][k][o].f + F) % Mod;
                                dp[cur ^ 1][j - 1][k][o].g = (dp[cur ^ 1][j - 1][k][o].g + F + G) % Mod; 
                            }
                            else if(k) {
                                dp[cur ^ 1][1][0][o].f = (dp[cur ^ 1][1][0][o].f + F) % Mod;
                                dp[cur ^ 1][1][0][o].g = (dp[cur ^ 1][1][0][o].g + G) % Mod; 
                            }
                            else {
                                dp[cur ^ 1][0][1][o].f = (dp[cur ^ 1][0][1][o].f + F) % Mod;
                                dp[cur ^ 1][0][1][o].g = (dp[cur ^ 1][0][1][o].g + G) % Mod; 
                            }
                        }
                    }
                }
            }
        }
        cur ^= 1;
    }
    ll ans = 0;
    rep(i, 0, n) {
        rep(j, 0, 1) {
            rep(k, 0, 2) {
                ans = (ans + dp[cur][i][j][k].g) % Mod;
                ans = (ans + dp[cur][i][j][k].f * (i / 3)) % Mod;
            }
        }
    }
    write(ans), putchar('\n');
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

::::