当前位置: 首页 > news >正文

2024 CCPC Final F

F. Witnessing the Miracle / 见证奇迹

动态规划。

打表发现当一个被拿走的磁铁集合确定之后,未被拿走的磁铁的方向和距离可以由它左边被拿走的磁铁数量确定,因此,拿走磁铁的先后顺序不影响最终局面的状态,即从 \(S\) 中拿走不同集合的磁铁所对应的状态也是不同的。

考虑从左往右 \(dp\),设 \(dp_{i,j}\) 表示为 \(S\) 中确定了前 \(i\) 个和 \(T\) 中前 \(j\) 个位置的方案数。

由于磁铁可以往左往右溢出,此时溢出的位置也是合法的,可以将 \(T\) 前后扩 \(n\)\(0\)

因为可以从右边拿走磁铁使得左边的磁铁左移 \(k\) 位,所以初始化时需初始 \(dp_{0,n-k}\)\(1\),最终答案也是同理,最右边的可以被右移 \(k\) 位,则答案为 \(dp_{n,2n+k}\)\(s_{i-1}\) 保留 \(0/1\) 时有转移:

\[dp[i][j] = dp[i][j] + dp[i-1][j-1]\quad \text{ if } s_{i-1} \ne x \land t_{j-1}\ne x,x\in\{0,1\} \]

\(s_{i-1}\)\(1\) 但不保留时,有转移:

\[dp[i][j] = dp[i][j] + dp[i-1][j-3]\quad \text{ if } t_{j-1}=t_{j-2}=t_{j-3}=0 \]

代码中 Z 类型为取模类。

点击查看代码
using Z = ModInt<MOD[0]>;void solve() {int n, k;std::cin >> n >> k;std::string s, t;std::cin >> s >> t;t = std::string(n, '0') + t + std::string(n, '0');const int lim = 3 * n;std::vector<Z> dp(lim + 1);dp[n - k] = 1;for(int i = 0; i < n; i += 1) {std::vector<Z> ndp(lim + 1);for(int j = 1; j < lim; j += 1) {if(t[j - 1] != '1' && s[i] != '1') {ndp[j] += dp[j - 1];}if(s[i] != '0') {if(t[j - 1] != '0') {ndp[j] += dp[j - 1];}if(j >= 3 && t[j - 1] != '1' && t[j - 2] != '1' && t[j - 3] != '1') {ndp[j] += dp[j - 3];}}}dp = std::move(ndp);}std::cout << dp[2 * n + k] << "\n";}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=33257

相关文章:

  • vue
  • Windows关闭端口占用
  • 洛谷 P12865
  • ubuntu清理内存缓存
  • ubuntu常用技巧
  • 10.17 CSP-S模拟33 改题记录
  • 包装类(基本数据类型对应的引用数据类型)
  • luogu P7915 [CSP-S 2021] 回文
  • USACO 绿-蓝 思维题小记
  • Day16-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\classlei
  • 一个实用的短视频脚本创作指令分享
  • 字典树 Trie 乱讲
  • redis和mysql之间的数据一致性
  • ubuntu允许root登录桌面系统
  • 24. 两两交换链表中的节点
  • AI协科学家:技术革命还是安全噩梦?
  • 一个决定
  • 10月17日
  • npm镜像配置
  • 一些特性
  • ubuntu安装mysql
  • 计算机视觉技术与应用深度解析
  • AGC 板刷记录1
  • 2025.10.17总结
  • 记Windows 11环境Rust下载安装配置流程
  • K8s学习笔记(九) job与cronjob - 教程
  • [HZOI]CSP-S模拟33
  • [PaperReading] VLM2Vec-V2: Advancing Multimodal Embedding for Videos, Images, and Visual Documents
  • ShandongCCPC2024
  • 标悬浮展开多级菜单