IOI2020国家集训队作业

未分类

[CF504E][Think][Code] 思路简单的树上提取路径，hash，二分求lcp。O(nlogn)-O(1)求k级祖先待学。
[CF505E][Think][Code] 时光倒流贪心以避免负数。
[CF506E][Think][Code]　神 题。计数DP转有限状态自动机路径数。填数类计数问题可以先留好所有空位然后来填这样DP，不会重复。其他的marked。
[CF512D][Think][Code] 背包计数。
[CF516D][Think][Code] 想到是用双指针来搞，但是没想到是建成个小根堆再来搞，还以为是在直径上尺取。
[CF516E][Think][Code] 首先想到按gcd(n,m)分组来搞。然后这时n'和m'是互质的，只要一开始有快乐的人就一定有解，可以分别算男生女生的最大值，比如算男生时，女生的影响视为男生的影响，就成了一个多源最长路问题。细节巨多。
[CF521D][Think][Code] 简单小清新贪心题谁知我输出答案没排序WA一发。

8.19

[CF521E][Think][Code] 题意是找简单无向图的两点之间的三条不相交路径。Think错了。简单的做法是，搞一个生成树，然后用两条覆盖同一条树边的非树边来构造。
[CF526F][Think][Code] 经典的 连续段计数？？Orz。连续段判定可用max-min-len=-1，然后有max-min-len>=-1，并且全局最小值一定为-1，那么线段树维护后缀最小值和最小值个数。还要用到一个单调栈维护后缀最小值和最大值的trick。
[CF526G][Think][Code] 树论难题。首先肯定是选2*y个叶子。考虑一个询问的情况，以x为根，因为S一定包含x和所选的叶子，也就是说叶子和根(x)一定是联通的，那么可以转化为选2*y条叶子到根的链。这个用长链剖分剖出的前2*y大的长链即可。考虑到直径的两端点至少有一个在S里，那么以直径的端点为根选2*y-1条叶子到根的链，这时x可能不在S里，那么从x子树里最深的叶子往上link，直到碰到第一个在S中的点y。这时有两种选择：1)删掉y向下的链，2）删掉第2*y-2大的长链。
[CF527E][Think][Code] 水水水。

8.20

[CF536D][Think][Code] 我觉得可以称作最大最小博弈。值得注意的是通过矩阵处理了二维限制。
[CF538G][Think][Code] 坐标轴变换。首先(x,y)->(x+y,y-x)，上下左右就成了(1,1),(1,-1),(-1,-1),(-1,1)，然后(x,y)->((x+t)/2,(y+t)/2)，上下左右就成了(1,0),(0,1),(0,0),(1,1)。这时可以所谓的横纵坐标分别考虑，其实意思是可以自由地操纵一维坐标而不用担心对另一维的影响。
[CF538H][Think][Code] 先考虑没有T和t的限制，是否存在一个最优的(n1,n2）,发现n1=min{ri},n2=max(li}，且n1只能变小，n2只能变大。然后二分图染色完了。
[CF547D][Think][Code] 横纵坐标连边，转化为给边定向使得每个点出入度之差不超过1。偶点即出入度相等，奇点可以link一下虚点，因为奇点个数一定是偶数，所以所有点度数都成偶数了，这样跑个欧拉回路定向即可。
[CF547E][Think][Code] 字符串套路题。
[CF549E][Think][Code]
[CF553E][Think][Code] 好题。首先看到带最优化决策的期望，肯定是DP没错了。然后我想这是个一般图怎么转移啊，唉sb，一维没法转移再加一维时间就好了，并且注意到有个明显的边界条件就是时间大于t时最优决策直接是到n点的最短路加x。列出朴素转移，套路地分治fft优化。

8.21（假）

[CF555E][Think][Code] 我已经连这种简单图论题都做不出了吗。无向图的边双一定可以按某种方案定向为有向图边双使得它里面两两可达，显然这是最优方案。

8.22（LGR-O75）

[CF559E][Think][Code] DP妙题。设计时只考虑新加的贡献。
[CF559E][Think][Code] 很有指导意义。首先，发现它跟普通的树的中心一样具有单峰性，但是不能一条边一条边地走，于是可以点分治，走使答案最小的子树。设当前分治中心为x，把答案看成一个函数f(z)，z可以认为是最小路径长度，重点是从x走向y后，对于x的每棵子树中的路径来说，z的变化值是相同的（因此可以看成一个函数）。对这个函数求导就OK了。
[CF566E][Think][Code] 需要灵感的构造题。考虑能否直接判断两点之间有无边，发现对于两个非叶节点x,y，存在边(x,y)充要条件是存在两个集合交集恰好为{x,y}。 bitset是可以1000^3/w的。
[CF568C][Think][Code] 2-sat如果只是判定的话可以边填边判。
[CF568E][Think][Code] LIS有种dp方法是设f[i]为长度为i的LIS的最小末数字，然后在f上二分来转移。
[CF571D][Think][Code] 在线并查集好想。值得注意的是离线先像kruscal重构树一样把树建出来，再做子树加，子树赋值。

8.23

[CF571E][Think][Code] 码农数论Marked。
[CF573E][Think][Code] 维护n个一次函数的最大值，支持k和b区间加。分块，一个块内统一k和b的标记。因为块内k一定单增，所以块内可以用单调队列维护个上凸包，这样query时就可以从左到右扫。区间修改打标记，单点修改暴力重构。然后维护凸包时斜率不存在时要特判啊！！！
[CF575A][Think][Code] 矩乘套路题。
[CF575E][Think][Code]
[CF575I][Think][Code] 发现这类支持某个奇怪的平面图形加跟查询的题的套路了。关键是找到x,y满足的不等式，根据这个来维护。
[CF576D][Think][Code] awsl。想到要枚举最大解锁的边，然后呢？然后找可能的起点bfs啊！真蠢。

8.24

[CF576E][Think][Code] 动态维护是否存在二分图？并查集。并查集维护二分图有两种方式，一种是带权，看路径长奇偶性，一种是扩域。在时间轴上线段树分治。发现一个操作可能不执行？没关系，先假装它执行，判断后再看1）不管2）延长上一个执行。
[CF578E][Think][Code] 小清新贪心？朴素的贪心策略不行，于是加个小改动就AC了？
[CF578F][Think][Code] 涉及到对偶图，Marked。

8.25

[CF582D][Think][Code] 毒瘤DP题。洛谷上写了题解。
[CF582E][Think][Code] 建中序表达式树，树形DP，状压每个变量值的函数值，fwt优化。
[CF585E][Think][Code] 一眼秒？容斥系数一定要敢想，这个不行取个负试试。

8.26

[CF585F][Think][Code] AC自动机+数位DP。启发我们可以把自动机的节点加入DP状态，以获取一些关于字符串匹配的信息。还有AC自动机如果是链虚点写法的话别忘了根节点的空儿子要连向自己。
[CF587D][Think][Code] 2-sat。前缀建图优化。
[CF587F][Think][Code] CF547E把询问swap了一下？还是水水水。不过注意在树状数组上查询时要用dfn序啊。
怎么可能啊。要根号分治。
[CF590E][Think][Code] AC自动机上处理出字串关系，然后构造最大反链。注意不用跳fail跳到底，只要跳到最近的结束点就行了，细节略坑。
[CF594E][Think][Code]

8.27

[CF603E][Think][Code] 这种题没结论不可做的。要发现一个很强的判定性定理：节点个数为偶数的联通块一定有解。然后发现答案单减，用cdq分治或者LCT动态加边，删除最大边解决。
[CF605E][Think][Code] 像这种带最优决策的期望题，看起来似乎后效性所以只能高消但又碍于min-max，实际上往往隐藏着不具后效性的性质或决策方式，需要找出它，然后DP或贪心。然后，尽量不要用double型变量读入数据，非常慢。
[CF626G][Think][Code] 我真是越来越蠢了呢。发现每个奖池的derta是减函数，于是想到用堆每次取最大的，修改的话也可以贪心地取使答案变化最大的，然后猜结论发现每次最多修改1张。为浮点数写比较函数时应该这样写：如果差值小于eps视为相等，按编号排 。

8.28

[CF611G][Think][Code] 双指针。
[CF611H][Think][Code] 不会证的结论+网络流。

8.29

[CF613E][Think][Code] hash+DP。需要注意的是为了保证上下摇摆时转移无后效性，可以设两个状态，一个是上一步从同一列来的，一个是上一步从不同列来的。
[CF627F][Think][Code] 构造题越来越玄学了。

「2020集训队作业Part1」rush完毕。
未完成任务：
学习O(nlogn)-O(1)求k级祖先 [✔]
CF506E
CF549E
CF575E
CF578F
CF594E

[CF627E][Think][Code] 枚举上下边界，固定右边界算左边点的贡献。
[CF639E][Think][Code] 简单贪心。话说好久没做连扰动法都没一眼看出来。

8.30（假）

[CF639F][Think][Code] 建虚树然后强跑tarjan。4k代码。

8.31

[CF666D][Think][Code]
[CF666E][Think][Code] 调了1h+之后我只想说一句话，注意SAM的tips！！！
[CF671D][Think][Code] 整体DP。线性规划的对偶问题marked。
[CF671E][Think][Code]
[CF643D][Think][Code] 模拟题。维护所有儿子除去自己贡献的答案的set的trick。
[CF643F][Think][Code] 做法没怎么看懂。。不过求组合数时如果不好求逆元可以分子分母除gcd。

9.1

[CF643G][Think][Code] 区间赋值，区间查询比例大于p%的数（p>=20)。像这种「比例大于p%的数」有个「摩尔投票」的经典做法，就是维护100/p个数的HP，每次加入一个数，如果与这100/p个数相等就HP加加，否则这些数HP都减1。正确性可以这样考虑，最坏情况下每次减的100/p个数都是最终答案，但这时推推不等式会发现仍能保证它们能留到最后。另一种做法是值域分快，因为区间推平使得均摊只需要修改O(n)个数值的前缀和数组。
[CF679E][Think][Code] 值得注意的线段树维护方式。复杂度（不包括操作2）可以这样想。我们知道所有数字变坏的总次数是O(nlogn)的，但是如果暴力加的话，一次是O(n)的，但如果拿到线段树上来做，只有当前节点中包含会变坏的点时才递归下去，一次均摊就是O(logn)的。相当于我们提前预知了哪里会变坏并且在线段树上就只朝那边走，这样一个会变坏的点最多让我们走线段树的树高O(logn）步。注意标记之间的相互作用。
[CF685C][Think][Code] 解不等式组。要注意奇偶性。
[CF696F][Think][Code] 垃圾计算几何，调得我十分暴躁。
[CF698D][Think][Code] 考虑一个方案，i可以为j清理障碍，则link(i,j)那么会形成一个DAG。这个DAG可以有多个拓扑序（因为优先级相同的点的顺序可以是任意的），枚举全排列（拓扑序）就可以唯一还原出一种方案。

9.2

[CF700E][Think][Code] sam的parent树上dp。
[CF704B][Think][Code] 贪心全靠蒙。发现一个点的贡献只与它与左右点的关系有关，然后我就不会dp了。排序啊！从小到大加入啊！每次合并两条链！这种题DP好像有个套路，jiu'shi
[CF704C][Think][Code] 题意杀。点边转化。表达式为点，变量为边，dp。
[CF704D][Think][Code] 上下界网络流。
[CF704E][Think][Code] 首先树剖，考虑一条链。我开始是推公式，看能不能找到一个判别式，但这种问题其实应该首先画图，以时间为 $x$ 轴，深度为 $y$ 轴，一个事件就是一条线段，用铅直的扫描线来扫，每次加入或删除事件时用相邻事件的交点更新答案，扫到大于最优答案时就退出。因为退出后才出现交点，所以可以用 set 维护而不至于内部乱序。
[CF708D][Think][Code] 要利用上下界网络流的武器（雾）！ 别乱搞负圈。

9.3

[CF708E][Think][Code] 推式子优化DP。我连状态设计都没想到。开始想的是以「前i层」为阶段，但是这样不能做。其实各层之间是独立的，且第i层能不能接上只与第i-1层有关。
[AGC020D][Think][Code] 蓝题，但是真的很难的构造题。
[AGC020E][Think][Code] 用mapdp还行。
[AGC020F][Think][Code] 发现一个「反常识」的事实，随机选择两个实数相等的概率为 $0$ !这个题竟然可以把小数部分离散化然后枚举小数部分的大小。。。

由于种种原因其实是洛谷不支持交AT了暂停刷2020集训队作业，将开新坑。

[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]
[][Think][Code]