退役III次后做题记录(扯淡)

时间:2021-04-10 22:12:53

退役III次后做题记录(扯淡)


CF607E Cross Sum

计算几何屎题

直接二分一下,算出每条线的位置然后算

注意相对位置这个不能先搞出坐标,直接算角度就行了,不然会卡精度/px

flag:计几题都不写了

CF611G New Year and Cake

真香

双指针扫可行的区间然后维护。

一个三角形的面积可以用\(|AB+BC+CA|\)算,其中\(A,B,C\)是向量\(OA,OB,OC\),\(O\)在三角形外

然后推出的式子可以很好地化简然后维护(为啥我写这么慢啊

CF504E

巨大常数卡过去了 舒服

二分+哈希,然后哈希可以\(O(巨大常数)\)算,要长链剖分算一个\(x\)的\(k\)级祖先

https://codeforc.es/contest/504/submission/63411989

CF506C

二分,然后倒着做,变成一开始有\(n\)个高度为\(mid\)的,每个时刻开始高度全部减\(a_i\),然后选择\(k\)个高度加\(p\)。

考虑限制是啥,正着做的时候一开始是\(h_i\),中间会出现一些\(<0\)的时候很不爽,一开始先给\(h_i\)加上一个数就很爽了,条件就是高度始终\(\ge 0\),倒着做的话另一个条件就是最后的高度满足\(\ge h_i\)

对每个东西维护:如果不再操作,最后的值\(fi\)。如果有\(fi<0\),肯定先做\(fi<0\),有多个先做更早会\(<0\)的

否则随便做一个\(fi_i<h_i\)的,然后可以check了

CF704B

对连通块dp。

AGC028C

答案一定是所有\(A,B\)中选\(n\)个,先拿出所有的升序排序,然后拿出最小的\(n\)个,看是否能取到,如果不能再分情况讨论

(懒得写了

CF521D

求个\(\ln\)后三操作就是加,1,2操作是凸的,可以用一个堆维护

CF536D

每个点到\(s,t\)最短距离后转化为一个坐标,在坐标轴上面dp,前缀和优化

CF547D

这提姆不就是704d吗= =

CF571D

先对每个询问求出最后一次清空的时间就可以忽略清空操作了

搞出重构树,直接在上面操作

CF576D

bitset优化01矩乘

毒瘤= =zbl

CF582D

这题先咕了

CF587D

屎题

抠出每种颜色,显然只能是很多链或者环,分情况讨论亿下,长度为奇数的链还要二分 2sat

CF643D

搞一堆set大模拟,修改点时只用修改父亲

CF521E

加边加到图不是仙人掌时可以找到端点,然后输出方案

CF576E

线段树分治 可以操作到叶子节点之后再放之后的操作

CF582E

设\(f_{i,j}\)表示树上点i,对于所有变量取值的答案压到\(j\),方案数

转移用fwt

CF585E

直接莫反,不算\(1\)的话每对集合和数会算\(-1\)次

CF538H

显然图是个二分图,染色之后同一个连通块同一个颜色缩成一个区间

然后问题就是有很多对区间,取两个位置\(p1,p2\)对于每一对区间正好分别在一个区间内

然后直接枚举左端点,对一对区间可行的右端点还是个区间,线段树维护即可

CF575I

鸽子好神仙啊

先要维护三个东西:

以一个点为右上角的矩形

以一个点向左下的直线和向下的直线围成的图形(直角三角形)

以一个点向右下的直线和向下的直线围成的图形(直角三角形)

然后4个操作都可以用这三个东西容斥出来

CF626G

设\(t\)表示题面中\(l\),\(s\)表示你的方案中每个箱子放的数量。有限制\(\sum s\leq T\)

那么你最终收益期望是\(\sum p_i-\sum \frac{t_ip_i}{t_i+s_i}\)

那么要最小化后面的东西,也就是最大化\(\frac{t_ip_i}{t_i+s_i}\)

一组询问可以用堆维护,然后修改一个\(t_i\)并不会影响其他选取方案的相对顺序

可以证明,给一个\(t_i\)修改\(1\)过后的\(s\)最多只会有一处增加和一处减少

先看给\(t_i\)加1,那么选这个箱子整体会变差,所以策略是可能会拿走一个给别的箱子

如果拿走两个是不可能的,因为原来选了这个箱子收益是\(\frac{t_ip_i}{t_i+s_i}\),后来变成了\(\frac{(t_i+1)p_i}{t_i+s_i+1}\),\(s_i\)减去\(1\)后变成\(\frac{(t_i+1)p_i}{t_i+s_i}\),严格大于原来的收益,既然原来的选了这个肯定不会被换掉

给\(t_i\)减1类似,策略是如果超了先减1然后选这个箱子会变好,可能会从另一个箱子拿一个过来,不过类似上面可证明不会拿两个过来

然后用一个堆维护“插入箱子”和“从箱子拿出”的最大值就行了