题解：P14256 平局（draw）

中文题解

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

对于相邻的两个人的胜负关系，用

<, =, >

表示。

首先可以观察到对于序列中初始的所有

=

，都可以立即合并，获得

1

的贡献，因为如果不合并这两个人后续合并至多因此多得到

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)

（滚动数组）。

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:

$<<$ can be merged into a $>$ ;
$<>$ can be merged into a $<$ or a $>$ ;
$><$ can be merged into a $=$ ;
$>>$ can be merged into a $<$ ;

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 >>

<>>\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

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}

参考实现 / Implementation

CPP

#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;
}

题解：P14256 平局（draw）

文章操作

相关推荐

评论

题解：P14256 平局（draw）