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

10.14 NOIP 模拟赛 T1. HappyLovelyEveryday!

思路

不难发现等价于划分序列, 对序列内部做异或和, 求本质不同的最终序列的数量

考虑去重, 子序列计数去重用的是钦定尽量往前匹配
本题中, 对于任意一种最终序列, 我们可以限制每个划分块都必须是最小的, 也就是攒够要的赶紧跑路
也就是若要 \(1\), 就找到后面第一个 \(1\) 划分, 若要 \(0\), 就找直接一个 \(0\) 或者连续两个 \(1\)
然后最后找任意结尾, 加上最后一段算方案数

#include <bits/stdc++.h>
#define int long long
const int MAXN = 2e6 + 20;
const int MOD = 998244353;int add(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }int a[MAXN];
int f[MAXN];
int nxt1[MAXN];
std::unordered_set<long long> vis;
signed main() {// freopen("a.in", "r", stdin);// freopen("a.out", "w", stdout);int _; scanf("%lld", &_);while (_--) {std::string astr; std::cin >> astr;int n = astr.size();bool sp = true;for (int i = 1; i <= n; i++) a[i] = astr[i - 1] - '0', sp &= (a[i] == 1);a[n + 1] = 1; a[n + 2] = 1;/*找每个位置后第一个 1*/for (int i = n + 2; i >= 1; i--) {if (a[i]) nxt1[i] = i;else nxt1[i] = nxt1[i + 1];}/*dp*/f[0] = 1;for (int i = 1; i <= n; i++) f[i] = 0;for (int i = 0; i <= n; i++) {if (a[i + 1]) {if (i + 1 <= n) f[i + 1] = add(f[i + 1], f[i]);}else {if (nxt1[i + 1] <= n) f[nxt1[i + 1]] = add(f[nxt1[i + 1]], f[i]);}if (!a[i + 1]) {if (i + 1 <= n) f[i + 1] = add(f[i + 1], f[i]);}else {if (nxt1[nxt1[i + 1] + 1] <= n) f[nxt1[nxt1[i + 1] + 1]] = add(f[nxt1[nxt1[i + 1] + 1]], f[i]);}}int ans = 0;for (int i = 0; i <= n - 1; i++) {ans = add(ans, f[i]);}printf("%lld\n", ans);}return 0;
}

总结

最小构造用于去重还是很牛的

http://www.hskmm.com/?act=detail&tid=31177

相关文章:

  • CSP-J 2025 入门级模拟赛 Day6 复盘 B. 罐の水表
  • 10.14每日总结
  • 四边形不等式
  • 20251014 杂题
  • 二叉树的遍历
  • SQL在智能自动化业务场景中的应用 - Irving11
  • 拼接字符串要求字典序最小
  • 高级语言作业第一次随笔
  • C#实现开机自启动应用多种方式
  • 日志|二叉树|110平衡二叉树|111二叉树的最大深度|199二叉树的右视图
  • Chrome在Speedometer 3.1创下历史最高分,为用户节省数百万小时
  • 西电CTF平台——Moectf 2025 WriteUP
  • [笔记]并查集进阶(带权、扩展域、带删除)
  • 20251013 模拟赛 总结
  • 什么是反应式编程 - 详解
  • SDL3和其附属的编译记录
  • Qwen多模态系列模型笔记—Qwen2-VL
  • WPF 调用 ChangeWindowMessageFilterEx 修改指定窗口 (UIPI) 消息筛选器的用户界面特权隔离
  • 实验1 现代C++基础课程
  • 牙科诊所借力AI营销4个月创收13万
  • 10月14日日记
  • P4653 [CEOI 2017] Sure Bet
  • 20251014
  • PHP虚拟主机测试页面
  • 歌词本。 - Slayer
  • 10月14日
  • 使用 Docker 快速搭建 MinIO 文件存储服务
  • 2025.10.14 正睿二十连测
  • singleton_pattern
  • ai出题