3 条题解
-
2
- 1
信息
- ID
- 798
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 14
- 已通过
- 4
- 上传者
考虑先把所有 *
替成 (
,然后这样还不满足前缀非负的肯定不对。
再把 *
替换成 )
,这样还不满足后缀非负的也不对。
考虑为什么满足这两个就对了。首先肯定将一段前缀 *
替成 (
,后缀替成 )
,由于满足两个条件,最终必然有前后缀和非负。再考虑能否满足总和为 0
。由于可以有空串,在【*
替成 (
】的情况下依次将后缀 *
改成 )
,最后奇偶性问题用一个空串解决。
所以问题变成了求 (x,y) 个数使得 ry≤x≤y≤lx。随便扫描线。倒序枚举 y 即可。
注册一个 CZOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。