[AGC018F] Two Trees
[AGC018F] Two Trees - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
先判一下奇偶性。考虑做一个很强的钦定，奇数都填 \(\pm1\)，偶数都填 \(0\)。对于同一棵树的一棵子树，考虑对子树内两个奇数点做匹配，要求匹配上的点一个 \(+1\) 一个 \(-1\)，这样就能在子树的根上轻易调整。两棵树的情况，观察到我们找完匹配之后，两组匹配的并是一个二分图（感觉可以感性理解），所以可以钦定出二分图的某一部点全填 \(+1\)，另一部点全填 \(-1\)。
[CF1100F] Ivan and Burgers
Ivan and Burgers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
即询问区间线性基。在普通的线性基上，多记每个基的下标，尽量保留下标更大的。插入时，如果当前位置有基但是下标比待插的小，我们 swap 这两个数和对应下标，将原来的基当作待插的数，异或上原来待插入现在成为基的数。然后继续下去。其它步骤和普通线性基一样。查询区间线性基时，就是查询 \(a[1,r]\) 的线性基中下标 \(\geq l\) 的部分。
[Jinan23L] Ticket to Ride
Ticket to Ride - Problem - QOJ.ac
首先发现是 dp：\(d_{i,j}\) 表示前 \(i\) 个数选了 \(j\) 个数了。
\[d_{i, j}=\max(d_{i-1, j-1}, d_{i-k, j-k}+val(i -k+1, i)) \]令 \(t=i-j\)。
\[d_{t, i}=\max(d_{t-1, i-1}, d_{t, i-k}+val(i-k+1, i)) \]枚举 \(t\) 去做 dp。后面的 \(d_{t, i-k}+val\) 可以使用线段树，做区间加。
可以并查集。我们需要支持：1. 前缀加；2. 全局 \(\max\)；3. 末尾加元素。观察到决策点只在前缀最大值上。并查集，将一个前缀最大值到下一个前缀最大值之前的下标全部合并。前缀加时在最后那个下标那里尝试弹出旧的前缀最大值。就行了。
但事实上，有决策单调性。队列维护决策单调性即可。但事实是，决策单调不增。
[CEOI2021] Newspapers
#3594. 「CEOI2021」报纸 - 题目 - LibreOJ (loj.ac)
充要条件是：无环，且存在一条链，使得所有点到链的距离 \(\leq 2\)。证明：前者显然，后者状压一条长度为 \(6\) 的链而中间连出去一个长度为 \(3\) 的链的情况得到。
做法：维护当前 Branko 可能在的位置，会在底层深度为奇数的点的前缀或在底层深度为偶数的点的前缀。你就不断地跟着前缀删点，然后就会变换到另一侧，再删。直到删到链顶，就删去了一半的点，再倒着做一遍就可以了。
[CEOI2023] Brought Down the Grading Server? (balance)
#4019. 「CEOI2023」Brought Down the Grading Server? - 题目 - LibreOJ (loj.ac)
\(S=2\)：每台评测机评测的两个题目连一条无向边，然后奇度的点往一个虚拟点再连一条边，欧拉回路，根据定的向安排顺序。
\(S=2^k\)：每台评测机评测的第 \(i\) 个题目与第 \(i+2^{k-1}\) 个题目连一条无向边，然后奇度的点往一个虚拟点再连一条边，欧拉回路，根据定的向安排顺序，这样划分成两个集合，每个题目在两个集合中的出现次数差不超过一，继续分治解决下去。
许庭强必刷五百题
给定平面上 \(n\) 个点，任意三点不共线，任意四点不共圆。在平面上画圆，称两个圆本质相同当且仅当它们包含的点的集合相同。问有多少个本质不同的圆。\(n\leq 500\)。
答案：\(\binom n 3+\binom n 2+\binom n 1+\binom n 0\)。
后两个分别是只包含一个点和不包含点。前两个的构造是，要么是两个点做直径，要么是选出三个角，锐角三角形画外接圆，直角和钝角三角形画的圆要求不包含直角。
从另一个角度来看，对于任意一个圆，首先稍微收缩一下，被两个点卡住，然后再缩，尝试去卡出以这两个点为直径的圆。被圆内点卡住的圆，是锐角三角形情形。被圆外点卡住的圆，是直角或钝角三角形情形。没有被卡住的圆，是两个点为直径的圆。
标签：下标,前缀,2024.8,选讲,线性,两个,题目,binom,杂题 From： https://www.cnblogs.com/caijianhong/p/18336991