ABC484G 题解
2026-11-15 19:41:31
发布于:广东
19阅读
0回复
0点赞
场上只切了 4 题怎么办/ll要不要退役/ll
Difficulty:4.8(蓝题下位)/ Easy+
Tag:DP 套 DP(?
首先考虑爆搜。但这是指数级,太不牛了。
考虑用状态代替被搜索的串,使得最后有一种简单的方法判定状态。
显然我们可以记录当前前缀可以被表示为哪些 之类和最后 的前 位字符拼接。状态太多了!注意到只有最后的那个前缀字符才是真正被用到的,其它都可以抛弃。这样可能的状态数量就只有 了,但是显然一个字符串可以用若干个这种状态表示,所以用 个二进制状态记录每一种状态是否存在,转移时最后判断状态中是否存在一个完整的 或一个完整的 即可。
然后我们发现可以把相同长度相同状态压成一种一起转移,显然是对的。
预处理每一种状态下一位接 会变为哪些状态。然后接个 DP 即可做到 ,可以通过。
代码中使用了滚动数组减小空间。
#include <bits/stdc++.h>
#include <assert.h>
namespace cjdst{
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
void init(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
}
const ll N = 2000, M = 16, mod = 998244353;
std::string s, a, b;
ll dp[2][(1 << M) + 5];
int next[(1 << M + 5)][2];
int curid;
int n, x, y;
inline char match(char x, char y){
return (x == '?' || y == '?' || x == y);
}
void solve(){
std::cin >> s >> a >> b;
n = s.size(), x = a.size(), y = b.size();
s = " " + s;
for(int i = 0; i < x + y; i++){
for(int j = 0; j <= 1; j++){
if(i == x - 1){
if(match(j + '0', a[0])) next[1 << i][j] |= 1;
if(match(j + '0', b[0])) next[1 << i][j] |= (1 << x);
}else if(i == x + y - 1){
if(match(j + '0', a[0])) next[1 << i][j] |= 1;
}else{
if(i < x && match(j + '0', a[i + 1])) next[1 << i][j] |= (1 << i + 1);
else if(i >= x && match(j + '0', b[i - x + 1])) next[1 << i][j] |= (1 << i + 1);
}
}
}
for(int i = 1; i < (1 << (x + y)); i++){
for(int j = 0; j <= 1; j++){
if(i & (i - 1)) next[i][j] = next[i & (i - 1)][j] | next[i & (-i)][j];
}
}
dp[0][(1 << x - 1) | (1 << x + y - 1)] = 1;
for(int i = 1; i <= n; i++){
curid ^= 1;
memset(dp[curid], 0, sizeof(dp[curid]));
for(int j = 0; j < (1 << (x + y)); j++){
if(match(s[i], '0')) dp[curid][next[j][0]] += dp[curid ^ 1][j];
if(match(s[i], '1')) dp[curid][next[j][1]] += dp[curid ^ 1][j];
}
for(int j = 0; j < (1 << (x + y)); j++){
dp[curid][j] %= mod;
}
}
ll ans = 0;
for(int i = 0; i < (1 << (x + y)); i++){
if((~i >> (x - 1) & 1) && (~i >> (x + y - 1) & 1)) continue;
ans = (ans + dp[curid][i]) % mod;
}
std::cout << ans << '\n';
}
}
int main(){
cjdst::init();
int T = 1;
// std::cin >> T;
for(int _ = 1; _ <= T; _++){
cjdst::solve();
}
std::cout.flush();
return 0;
}
全部评论 2
md场切ABCG叫啥
2天前 来自 上海
0你们都会dp就我不会
2天前 来自 浙江
0








有帮助,赞一个