昨天的周赛题目没来的及打,今天在图书馆调了一下午,很显然在75分钟内这题必挂。
我最开始定义了一堆没用的状态和转移,浪费了好几张草稿纸。但在定义状态和转移的过程中我把每个状态都精确的分了出来,以及最开始的填充和特判状态,就显得代码很长,像循环展开一样。
题意
给定一个字符串样的地图,字符串中只有 $ 1,2,*,?,0$ 五种字符,可在字符为 $?$ 的字符中填充 $0,1, 2,*$ 这 $4$ 类字符,求所有不同的合法数量的地图(字符串)。
限制条件
若第 $i$ 位置字符的左右两边,有(或可填充) $j$ 个雷($*$),那么该 $i$ 位置就填充 $j$ 。
题面数据 $1\leq n\leq10^6$ ,那么必然不能直接模拟某个位置填充什么的所有情况,不进行状态转移,这样复杂度会,额就是会很费手感觉至少得 $O(n^4)$ 。
分析
由于题目给了一个字符串,可以发现第 $i$ 个位置的方案数总可以由第 $i-1$ 个位置的方案数推导出来,显然考虑 $dp$ 。关于状态如何定义和转移,这个开始思考了很久。
首先会想到在 $i$ 位置填充数字 $j$ (数字 $3$ 可以代表雷)的方案数,其实这样定义大概率也是可以的,就是会比较麻烦,因为需要考虑是否有雷,根据是否有雷状态转移会很麻烦,那么倒不如单独把是否有雷拎出来,定义一个三维 $dp$ 。
对于 $dp$ 问题,定义状态往往是最难的,状态的定义是否正确合理则决定了做法是否正确和简洁
——一个我忘了哪个大佬说的
那么此时状态定义就很清楚了,$dp_{i,j,k}$ 分别表示在第 $i$ 位置填充数字 $k$ 的方案数, $j$ 判断上一个位置是否有雷,$k$ 代表填充的数字。
考虑状态转移
对于填充的数字 $0,1,2,3$
- 0
状态只能由 $*1?$ 和 $00?$ 这两种状态转移过来。
dp[i][0][0] = dp[i - 1][1][1] + dp[i - 1][0][0];
- 1
状态可以由 $*?,*1?,0?$ 三种大的状态来转移。
前面含雷的也单独分出来两种,包括含雷的前面是否有雷的两种状态。
前面不含雷只能由前面是 $0$ 或者是 $1$ 且 $1$ 的前面必须有雷,因为我们此时填充的不含雷,若 $1$ 左右两边均不含雷是不合法的。
dp[i][1][1] = dp[i - 1][1][3] + dp[i - 1][0][3];
dp[i][0][1] = dp[i - 1][0][0] + dp[i - 1][1][1];
- 2
状态可以由 $*?$ 这一种大的情况得到。
前面含雷的也单独分出来两种,包括含雷的前面是否有雷的两种状态。
dp[i][1][2] = dp[i - 1][1][3] + dp[i - 1][0][3];
- 3(即 $*$ 雷)
状态可以由 $*?,01?,11?,*2?$ 这三种大情况得到。
$01?,11?$ 这两种情况都是 $dp_{i-1,0,1}$ 这一种情况。
同样前面含雷分两种小情况,再加上一个 $2$ 的情况即可。
dp[i][1][3] = dp[i - 1][1][3] + dp[i - 1][0][3];
dp[i][0][3] = dp[i - 1][0][1] + dp[i - 1][1][2];
即状态转移已经处理好了,接下来把条件初始化一下即可。
直接放代码吧,处理和状态转移的很像。
if (s[0] == '?')
dp[0][0][1] = dp[0][0][0] = dp[0][0][3] = dp[0][1][3] = 1;
else if (s[0] == '2')
{
cout << 0;
return 0;
}
else if (s[0] == 1)
dp[0][0][1] = 1;
else if (s[0] == '*')
dp[0][0][3] = dp[0][1][3] = 1;
else if (s[0] == '0')
dp[0][0][0] = 1;
坑点:对于第一次 $?$ 在填充数字的时候转移,对于含雷的情况要单独特判为 $1$。
if (i == 1)
for (int j = 1; j <= 3; j++)
dp[t][1][j] = 1;
题面说有不合法的情况,对于我们特判不合法只需要特判第一个字符即可,至于字符串内部不合法的情况会在转移的时候变成 $0$ 。无需考虑。
答案统计,必然是统计最后一个位置,需要考虑当填充的数字数 $2$ 或最后一个位置前面没有雷却填充了数字 $1$ 。
复杂度 $O(n+T)$ $T$ 是一个巨大的常数,取决于 $?$ 的数量。
最后发现,由于状态只跟 $i-1$ 有关,可以用滚动数组,降低空间复杂度。(虽然也会增加一点时间复杂度)
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
const int mod = 1e9 + 7;
char s[N];
int dp[2][2][4];
int n, m, ans, t;
void init()
{
for (int j = 0; j <= 1; j++)
for (int k = 0; k <= 3; k++)
dp[t ^ 1][j][k] = 0;
}
int main()
{
cin >> s;
int n = strlen(s);
if (n == 1)
{
if (s[0] == '?')
{
cout << 2;
return 0;
}
else if (s[0] == '*' || s[0] == '0')
{
cout << 1;
return 0;
}
else
{
cout << 0;
return 0;
}
}
if (s[0] == '?')
dp[0][0][1] = dp[0][0][0] = dp[0][0][3] = dp[0][1][3] = 1;
else if (s[0] == '2')
{
cout << 0;
return 0;
}
else if (s[0] == 1)
dp[0][0][1] = 1;
else if (s[0] == '*')
dp[0][0][3] = dp[0][1][3] = 1;
else if (s[0] == '0')
dp[0][0][0] = 1;
for (int i = 1; i < n; i++)
{
t ^= 1;
if (s[i] == '?')
{
for (int j = 1; j <= 3; j++)
dp[t][1][j] = dp[t ^ 1][1][3] + dp[t ^ 1][0][3], dp[t][1][j] %= mod;
if (i == 1)
for (int j = 1; j <= 3; j++)
dp[t][1][j] = 1;
dp[t][0][3] = dp[t ^ 1][0][1] + dp[t ^ 1][1][2];
dp[t][0][3] %= mod;
dp[t][0][0] = dp[t ^ 1][1][1] + dp[t ^ 1][0][0];
dp[t][0][0] %= mod;
dp[t][0][1] = dp[t ^ 1][0][0] + dp[t ^ 1][1][1];
dp[t][0][1] %= mod;
init();
}
else if (s[i] == '*')
{
dp[t][1][3] = dp[t ^ 1][1][3] + dp[t ^ 1][0][3];
dp[t][1][3] %= mod;
dp[t][0][3] = dp[t ^ 1][0][1] + dp[t ^ 1][1][2];
dp[t][0][3] %= mod;
init();
}
else if (s[i] == '1')
{
dp[t][1][1] = dp[t ^ 1][1][3] + dp[t ^ 1][0][3];
dp[t][1][1] %= mod;
dp[t][0][1] = dp[t ^ 1][0][0] + dp[t ^ 1][1][1];
dp[t][0][1] %= mod;
init();
}
else if (s[i] == '2')
{
dp[t][1][2] = dp[t ^ 1][1][3] + dp[t ^ 1][0][3];
dp[t][1][2] %= mod;
init();
}
else
{
dp[t][0][0] = dp[t ^ 1][1][1] + dp[t ^ 1][0][0];
dp[t][0][0] %= mod;
init();
}
}
int sum = 0;
for (int j = 0; j <= 1; j++)
for (int k = 0; k <= 3; k++)
{
if (k == 2 || (k == 1 && j == 0))
continue;
sum += dp[t][j][k];
sum %= mod;
}
cout << sum;
return 0;
}
状态转移是依次往右移动的 $s_n$ 这个数组也可以优化为字符,空间复杂度可以继续降低。
难度上来了
滚动转移每次在转移的时候初始化一下下一次的转状态就可以啦