Educational Codeforces Round 94 题解
2024-09-05 12:20:26
我竟然比到了全场的 rk 14,incredible!
A
大水题,直接输出 \(n\) 遍 \(s_n\) 即可。
B
分类讨论题,放在 B 题可能难度有点大了。
直接暴力枚举你拿了多少个宝剑,然后贪心地计算出你随从最多可以带多少把武器。
把它们加起来取一个 \(\max\) 就行了
C
简单构造,如果 \(s_i=0\) 那么就把 \(w_{i-x}\) 和 \(w_{i+x}\) 上填 \(0\)。其余位置上都填 \(1\)。
然后回过头来过来 check 一遍,如果不合法就输出 \(-1\),否则
D
暴力跑一遍前缀和 \(s_{i,j}\) 表示 \([1,i]\) 有多少个 \(a_k=j\)。
然后枚举 \(j,k\) 乘法原理计算出 \(i,l\) 的个数
E
同 CF448C,我抄我自己。
考虑清空一个区间 \([l,r]\)。那么显然只有两种方法:
- 不断横着清空,直到序列中有数为 \(0\)。
- 竖着清空 \(r-l+1\) 次。
分治递归即可。
F
sb 题啊~~为什么我考场上没 rush 出来?
显然可以预处理出所有 x-prime 的字符串——最多 \(2399\) 个。
然后对原串建 AC 自动机。
考虑 \(dp_{i,j}\) 表示在前 \(i\) 位中,现在到达了 AC 自动机上的节点 \(j\),最少删去的字符数。
考虑转移,分两种情况:
- 删除第 \(i+1\) 个字符,那么肯定还停留在原先的节点上。\(dp_{i,j}+1 \to dp_{i+1,j}\)
- 保留第 \(i+1\) 个字符,那么 \(j\) 就会变为 \(j\) 的第 \(s[i+1]-'0'\) 个儿子。\(dp_{i,j} \to dp_{i+1,son[j][s[i+1]-'0'}\),当然,此种情况必须满足一个条件,那就是 \(son[j][s[i+1]-'0'\) 不是任何一个 x-prime 的字符串的结尾。
G
https://www.luogu.com.cn/blog/et2006/solution-cf1400g
最新文章
- UITableViewController和XML解析还有地图的简单结合
- 开始学习Dojo
- Facebook的Hack语言三大看点
- c中的基本运算
- python 网络编程(一)---基础
- gdb调试高级用法
- python的sorted相关
- Display number of replies in disscussion board
- MongoDB基础教程系列--第一篇 进入MongoDB世界
- xcode修改代码目录结构出现clang:error:nosuchfileordirectory解决方法
- Java学习笔记之——Manth类和String类
- IE内核浏览器的404页面问题和IE自动缓存引发的问题
- _ZNote_Qt_Tips_添加动态链接库
- 仿迅雷播放器教程 -- C++ 100款开源界面库 (10)
- (转+整理)Nandflash存储
- linux用户管理 用户和用户组信息
- input.php
- (原)linux下caffe模型转tensorflow模型
- idou老师教你学Istio:如何用 Istio 实现速率限制
- 第四章 Spring.Net 如何管理您的类___统一资源访问接口