CF1132
降智严重......
已经不会cf 2k难度的题了......
于是三题滚粗......
这是lk新号第一场debuff吗......
技不如人就是技不如人,找什么借口......
A
显然((,))
个数必须一样。
显然)(
需要在((,))
中间。
所以如果)(
存在((
不存在就不可以。
B
把\(a\)从大到小排序,\(s=\sum a_i\),第\(i\)个套餐答案显然就是\(s-a_{b_i}\)
C
枚举不请的两个人,然后两个区间中只被刷一次的段和两个区间交中只被刷两次的段不会被刷到。
上面是我赛时A掉的题
过C的时候比赛刚开始14分钟,之后就再没得分了((((
D
这题卡2个log的常 !差评!
二分答案,然后每秒贪心选择剩余可用时间最少的给它充1分钟
如果用优先队列,就是2个log。
注意不用充电的电脑不用扔进优先队列。
不考虑这个,写优先队列的就会像我一样被卡tle
当然由于结束时间\(\le 200000\),只要把每个关机时间开个桶就可以一个log了。
E
\(L=\mathrm{lcm}(1..8)=840\)
显然1..8中每个数i 由多个i凑成的L本质上一样,只需要先统计每个i不凑成L的部分。
dp[i][j]
表示1..i
中每个数k不用来凑L的部分的和为j,最多能凑出多少个L。
F
这题是2000难度可我场上不会....
设f[l,r]
表示[l:r]
区间消掉最少次数。
考虑第l
个字符是怎么消掉的:
- 如果是单独消的,
f[l,r]=1+f[l+1,r]
。 - 否则,选择一个
[l+1,r]
区间里面满足s[i]=s[l]
的i
,然后先把[l+1,i-1]
区间删掉,然后[i,r]
区间删除的时候,把l
和i
一起删除f[l,r]=min(f[l+1][i],f[i+1][r])。
G
设nxt[i]为最小的j满足i<j,c[i]<c[j]
。若不存在则为n+1
则nxt构成了一棵以n+1
为根的树。
显然每个点为p[1]
的最长长度就是它到根节点路径上可选点数(由于可选位置是连续的所以没问题)
为了方便维护可以用线段树+dfs序。
然后就是区间加求全局最大值。