ABC217
A
签到
B
签到
C
签到
D
有一根长度为\(L\)的木棍，有以下两个操作：
\(1.\)在\(x_i\)处断开
\(2.\)回答包含\(x_i\)处的木棍的长度
解：
\(set\)二分
E
给定一个空序列，有以下三种操作：
\(1.\)在末尾添加一个字符\(x\)
\(2.\)输出首字符并删除
\(3.\)将序列升序排序
解：
用\(queue\)维护序列，升序排序时将序列中的所有字符都加入小根堆
输出时优先输出小根堆内堆顶，堆为空时输出队首
F
一列\(2n(n\leq 200)\)个人，有\(m\)对友好关系，每次选择相邻的两个友好的人删掉，求删掉所有人的方案数
解：
一眼区间\(dp\)
但是计算方案数的区间\(dp\)需要特殊的统计方法保证不重不漏
要不重复就要利用当前枚举到区间的特征
枚举\(k\in[l+1,r]\)，表示最后一步是由\(l,k\)配对而成
\(f[l][r]=\sum_{k=l+1}^r f[l+1][k-1]*f[k+1][r]*\dbinom{\frac{r-l+1}{2}}{\frac{k-l+1}{2}}\)
G
将\(1\sim n(n\leq 5000)\)分配到\(k(k=1,2,…,n)\)个非空集合里，\(id\)号模\(m\)同余的人不能在一个集合里，有多少种分组方式？
解：
考虑没有限制时，答案为第二类斯特林数\(S_2[n][k]\)
第二类斯特林数的递推式
其中第一部分表示第\(i\)个数字自成一组，不需要考虑限制
第二个部分表示第\(i\)个数字加入到现有的组中，只要去掉不能加入的组
设\(sum[i]\)为\(1\sim i-1\)中模\(m\)与\(i\)同余的数的个数
H
小人开始时在数轴上的原点，每个时刻可以选择向左移动一步或向右移动一步
有\(n(2e5)\)次操作，每次在\(t_i\)时刻\(x_i\)处出现出现一把向左或向右发射的水枪，对小人造成\(|x_i-pos|\)的伤害，如果在水枪背侧则不受伤害
求受到的最少伤害
解：
https://www.cnblogs.com/ak-dream/p/AK_DREAM127.html
这篇写得好
定义一个\(dp\)状态：\(dp_{t,x}\)表示\(t\)时刻在\(x\)处受到的最少伤害，\(F_{t,x}\)表示\(t\)时刻在\(x\)处受到的伤害
有转移方程
然后我们需要敏锐地观察力和经验发现，对于固定的\(t_i\)，\((x,dp_{t,x})\)构成了一个下凸函数
那么可以发现对于凸壳左半侧，\(dp_{t_i,x}=dp_{t_{i-1},x+\Delta t}\)
对于右半侧\(dp_{t_i,x}=dp_{t_{i+1},x-\Delta t}\)
等于将左半侧凸壳向右移动\(\Delta t\)，右半侧凸壳向左移动\(\Delta t\)
第二部分\(F(t,x)\)，以向左发射为例，对于小于\(x_i\)的部分是一个斜率为\(-1\)的一次函数，对于大于\(x_i\)的部分是贡献为\(0\)的常函数
现在介绍维护凸壳，每次只会对凸壳某一部分的斜率改变一个单位，且相邻两部分之间斜率相差\(1\)，因为只要维护凸壳的断点在哪里
将左侧和右侧分开维护，并手动统计斜率为\(0\)的部分的答案
后面细节看上面博客