美国时间8/12
P2851
思考一下不难发现John的最小交付硬币数相当于多重背包,店主的找零相当于完全背包,那么先把这几个求出来,但是John多付一些钱去找零的方案可以更优,最后统计结果是取付钱的最少硬币数+找零的最小硬币数的最小值。背包上界值用余数的鸽巢原理证一下的求出 244002440024400。(但是由于数据太水10100的上界甚至也过去了)
Code
美国时间8/16
P1117
贴主是看题解才会100分的,所以讲的不明不白。
先考虑 O(n2)O(n^2)O(n2) 做法,由于题面允许 A=BA=BA=B 所以相当于两个 AAAAAA 串拼接在一起,所以先求出以每个点为结尾和开头的 AAAAAA 串数量,可获得95pts。
考虑遍历 AAA 的长度,每 ∣A∣\lvert A \rvert∣A∣ 个字符放一个标记点,不难发现每个 AAAAAA 串中必然有且仅有2个相邻标记点,因此遍历相邻标记点。
每个 AAAAAA 串中的 AAA 由2个部分组成:从相邻标记点往后的 LCSLCSLCS 和 相邻标记点往前的 LCPLCPLCP,只有当 LCP+LCS≥∣A∣+1LCP+LCS \geq \lvert A \rvert+1LCP+LCS≥∣A∣+1 时才能构成 AAAAAA 串。然后用差分记录答案。
这里求 LCSLCSLCS 和 LCPLCPLCP 可以直接用后缀数组,但是由于我太弱了不会,所以选择用多一只 logloglog 的二分哈希,代码细节不少。
Code
美国时间8/17
P13323
本质上是一个最长公共子序列,将每一个段作为整体求最长公共子序列,但是需要把前面的段内别的可以匹配的放进来。
Code
P14347
在最优状态下有几个重要结论:区间覆盖操作不相交,区间翻转操作不相交,先区间覆盖再区间翻转一定不劣,具体证明看题解,这里就不写了。
然后定义 dpi,0,0dp_{i,0,0}dpi,0,0 表示为当前第 iii 位,这一位不覆盖,不翻转;dpi,0,1dp_{i,0,1}dpi,0,1 表示为当前第 iii 位,这一位不覆盖,翻转;dpi,1,0dp_{i,1,0}dpi,1,0 表示为当前第 iii 位,这一位覆盖为0,不翻转;dpi,1,1dp_{i,1,1}dpi,1,1 表示为当前第 iii 位,这一位覆盖为0,翻转;dpi,2,0dp_{i,2,0}dpi,2,0 表示为当前第 iii 位,这一位覆盖为1,不翻转;dpi,2,1dp_{i,2,1}dpi,2,1 表示为当前第 iii 位,这一位覆盖为1,翻转。
转移时如果第二维或第三维不为 000 且与 dpi−1dp_{i-1}dpi−1 的这一维状态不同则需要在前一位基础上加一,具体实现见代码。
Code
美国时间8/18
P3488
这道题首先用hall定理转化一下问题,转化后为:在任意区间(设为 [l,r][l,r][l,r])内脚的总数鞋必须全部小于等于 k×(r−l+d+1)k \times (r-l+d+1)k×(r−l+d+1) 才能全部匹配,那么将式子转化一下成为求脚的数量减去鞋子的数量的最大子段和再减去 k×dk \times dk×d ,判断其正负性,线段树维护即可。
Code。
美国时间8/21
P2146
树剖模板改一下就行了。
Code
美国时间8/22
P2114
从高位往低位贪心,如果这一位设为0不劣或上界不足设1则设为0,否则设为1。
Code
P8572
根号分治题。
如果 n≤kn \leq kn≤k 预处理所有 l,r{l,r}l,r 的答案。
否则用前缀和按照题意模拟即可。
Code
P4556
线段树合并模板题。
Code
美国时间8/24
P9000
设 aia_iai 表示第 iii 个人的位置,fif_ifi 为 aia_iai 的相对最终位置,因为题目相当于求最小的最大值,所以左移可以相对地变为右移,则最终答案等于 max((fi−ai)−(fj−aj))\max ((f_i-a_i)-(f_j-a_j))max((fi −ai )−(fj −aj )),由于 f1−a1f_1-a_1f1 −a1 恒为0,所以相当于求 max(fi−ai)\max(f_i-a_i)max(fi −ai )。
则 fi=maxj≤i(fj+(i−j)d)f_i=\max\limits_{j \le i} (f_j+(i-j)d)fi =j≤imax (fj +(i−j)d),代入答案式得 maxj≤i((fj−jd)−(fi−id))\max\limits_{j\le i}((f_j-jd)-(f_i-id))j≤imax ((fj −jd)−(fi −id)),线段树维护即可。
Code
中国时间8/25
P5854
笛卡尔树模板。
Code
中国时间8/26
P1377
注意到最终的树按插入顺序来看是小根堆,按权值来看是二叉搜索树,而笛卡尔树的性质是按权值来看是小根堆,按插入顺序来看是二叉搜索树。因此把插入顺序和权值交换一下就好了(其实数据范围也提示了这一点)。
Code
P3793
太好了是随机数据,说明建出来的二叉搜索树是平衡的。因此建出笛卡尔树,找到查询区间内节点的LCA的权值即可,具体实现的话,如果当前节点在区间左端点外则走右儿子,在区间右端点外则走左儿子,直到其落到区间内输出即可。
时间复杂度O(nlogn)O(n logn)O(nlogn),虽不是神秘类四毛子算法的线性复杂度但是常数极小,因此能过。
Code
中国时间8/27
P3586
查询先把每个数大于 sss 的部分砍掉,若 ∑i=1nai≥c×s\sum_{i=1}^{n} a_i\geq c\times s∑i=1n ai ≥c×s 即输出 TAK。实现用值域树状数组即可。
Code
中国时间8/28
喜报:一天没看我做的19道紫降了3道,做的速度赶不上降的速度那咋办/yi。
P2597
看到DAG和食物链一眼拓扑。先建立一个超级源点作为每一个单独的DAG中生产者的共同食物,这样图中只剩一个生产者。先反向连边(食物→\to→猎物),不难发现任何一个点 uuu 总能找到另外恰好一个离它最近的点 vvv,使得一旦 vvv 灭绝,uuu 也一定灭绝。然后将 vvv 当作 uuu 的父亲建树(称其为灭绝树),最终个点 uuu 的答案就是 uuu 的子树大小。
具体实现时在拓扑排序的过程中通过灭绝树上 uuu 的猎物的LCA更新节点在灭绝树上的父亲,因为根据拓扑序,更新转移时 uuu 的猎物一定已经出现在了灭绝树上(拓扑序的性质),别忘了将节点入队时更新ST表。
Code
上课,讲反悔贪心,题比较多,等会加上