倍增 + 并查集
VJspr4I - 萌萌哒 给定 NNN 和 QQQ 个限制 Li1,Ri1,Li2,Ri2L_{i 1},R_{i 1},L_{i 2},R_{i 2}Li1,Ri1,Li2,Ri2，问满足如下条件的字符串 S=(S1S2S3⋯Sn)S = (S_1S_2S_3 \cdots S_n)S=(S1S2S3⋯Sn) 数量：①1⩽S1⩽9,0⩽Si⩽91 \leqslant S_{1} \leqslant 9, 0 \leqslant S_{i} \leqslant 91⩽S1⩽9,0⩽Si⩽9；②子串 S[Li1,Ri1]S[L_{i 1},R_{i 1}]S[Li1,Ri1] 与 S[Li2,Ri2]S[L_{i 2},R_{i 2}]S[Li2,Ri2] 完全相同。N,Q⩽105N, Q \leqslant 10^{5}N,Q⩽105。 若字符串的两位置相同 Si=SjS_{i}=S_{j}Si=Sj 则给 i,ji,ji,j 连边，设连边后连通块个数为 xxx，那么答案为 9⋅10x−19\cdot 10^{x-1}9⋅10x−1。 ...
倍增
经典倍增方法： 初始状态 {F(x,1)=π(x)G(x,1)=W(x,π(x))\begin{cases} F(x, 1) = \pi(x) \\ G(x, 1) = W(x, \pi(x)) \end{cases} {F(x,1)=π(x)G(x,1)=W(x,π(x)) 转移 {F(x,2k)=F(F(x,2k−1),2k−1)G(x,2k)=G(x,2k−1)+G(F(x,2k−1),2k−1)\begin{cases} F(x, 2^k) = F(F(x, 2^{k-1}), 2^{k-1}) \\ G(x, 2^k) = G(x, 2^{k-1}) + G(F(x, 2^{k-1}), 2^{k-1}) \end{cases} {F(x,2k)=F(F(x,2k−1),2k−1)G(x,2k)=G(x,2k−1)+G(F(x,2k−1),2k−1) 12345678for (int bit = 1; bit < D; bit++) { for (int x = 0; x < n; x++) { if...
优雅的复数旋转 & 坐标变换方法
【XCPC/ 计算几何】优雅的复数旋转 & 坐标变换方法 给定二维平面的区域是一条以原点为端点的射线和所有距离射线 \leqslant d 的点的集合。射线的初始方向向量给定，会以每个单位时间 1 弧度的顺序旋转。给定一个 n 个顶点的凸多边形，保证凸多边形目标距离原点 >d。求区间在时间 [0,t] 中区域与凸多边形有交的时间区间长度。 法向量：n=(A,B)\boldsymbol{n} = (A, B)n=(A,B) 方向向量：u=(−B,A)\boldsymbol{u}=(-B, A)u=(−B,A) 单位方向向量：u0=(−B,A)∣∣n∣∣\boldsymbol{u}_{0} = \frac{(-B, A)}{||\boldsymbol{n}||}u0=∣∣n∣∣(−B,A) 平行分量（投影）t=P⋅ut = \boldsymbol{P} \cdot \boldsymbol{u}t=P⋅u 垂直分量（距离）d=∣P⋅n+C∣∣∣n∣∣d = \frac{|\boldsymbol{P} \cdot \boldsymbol{n} +...
CuteCube Garden - Testing Round
https://codeforces.com/gym/690768 CuteCube Garden - Testing Round 1 题解 A. Common Tangents 初中几何结论 首先两个圆有无穷多条切线当且仅当两圆完全重合，即 (x1,y1,r1)=(x2,y2,r2)(x_1,y_1,r_1)=(x_2,y_2,r_2)(x1,y1,r1)=(x2,y2,r2) 。 记两圆圆心距 d=(x2−x1)2+(y2−y1)2d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}d=(x2−x1)2+(y2−y1)2，有下面的结论： d≤∣r1−r2∣d \le \left| r_1 - r_2 \right|d≤∣r1−r2∣，内含，000条公切线。 d=∣r1−r2∣d = \left| r_1 - r_2 \right|d=∣r1−r2∣，内切，111条公切线。 ∣r1−r2∣≤d≤r1+r2\left| r_1 - r_2 \right| \le d \le r_1 +...
01Trie
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121struct Node { std::array<Node*, 2> next{}; int icnt = 0;};void insert(Node*& p, int val, int bit = 30) { if (!p) { p = new Node(); } p->icnt++; if (bit == -1) return; ...
01 串
二分转化为 01 串 如果某个问题满足： 如果序列只有 0\mathtt{0}0 和 1\mathtt{1}1，问题是易解决的 答案依赖于序列中的数的大小关系 单次询问 可以考虑二分答案（或计算答案的中间变量）为 xxx，将序列中 ⩾x\geqslant x⩾x 的数置为 111，否则将 <x<x<x 的数置为 000（或 −1-1−1，按需），将序列转化为 01\mathtt{01}01 串。 【求中位数】x=an+12′x = a'_{\frac{n+1}{2}}x=a2n+1′，其中将 aaa 数组排序后为 a′a'a′。⩾x\geqslant x⩾x 的个数比 <x< x<x 的个数 恰好 要多，因此可以通过二分出一个最大的满足上述整数得到中位数。值得注意的是，如果中位数定义为 an+12a_{\frac{n+1}{2}}a2n+1，将 ⩾x\geqslant x⩾x 的数置为 111，定义为 an2a_{\frac{n}{2}}a2n，将 >x> x>x...
二分
https://codeforces.com/problemset/problem/1999/G1 https://codeforces.com/gym/106161/problem/C 这个，网络赛的 hall，还有上次 cf 的 f
网络流
1×21\times21×2 骨牌的最大覆盖数
Trie
CMG 最喜欢的字典树题——主机场「新懐質問」 * 本题名称来自「新しい、でも懐かしい質問」（新的，但是令人怀念的问题），因为有人说命题人的题目都很有年代感…… 给定 N,KN, KN,K 和一个字符串集合 S=(S1,S2,…,SN)S = (S_{1}, S_{2}, \dots, S_{N})S=(S1,S2,…,SN)，任选 KKK 元子集 T⊂ST\subset ST⊂S，最小化 maxa,b∈T,a≠bLCP(a,b)\max\limits_{a,b\in T,a \neq b}^{}\operatorname{LCP}(a,b)a,b∈T,a=bmaxLCP(a,b)。2⩽K⩽N⩽1062\leqslant K \leqslant N \leqslant 10^62⩽K⩽N⩽106 且 ∑∣Si∣⩽106\sum |S_i| \leqslant 10^6∑∣Si∣⩽106。（2023GDCPC E. New but Nostalgic...