260104 讲题
CF1438F Olha and Igor
需要注意到询问的三个点是无序的。考察随便问三个点，每个点被作为答案的概率，打表发现根节点的两个儿子概率最高。因此直接乱问 420 次然后取最大次大两个点作为根的两个儿子即可。
qoj8613 Cardinality
注意到 \(k\) 个 \([0,1]\) 实数的最小值的期望是 \(\frac{1}{k+1}\)，此外最小值是好求的，因此做 \(128\) 遍答案取均值即可。
*CF1526F Median Queries
发现询问三个数 \(a,b,c(a<b<c)\)，会返回 \(\max(b-a,c-b)\)。如果我们知道了 \(1,2\) 或者 \(n-1,n\) 的位置，那么就可以把剩下的数全都问出来。考虑这一步怎么实现，我们可以用一个数对 \((x,y)\) 把所有数问一遍，得到最远和次远两个数，它们就是 \(1,2\) 和 \(n-1,n\) 中的一个。但如果 \((x,y)\) 离得太远可能会返回 \(y-x\) 而不是我们要的距离。于是我们先可以用 420 次问出足够近的两个数（\(ans\le \frac{n}{6}-eps\)），就可以满足要求。\(420\) 次是足够的。
CF1746F Kazaee
发现就算是 \(k=2\) 似乎也没有除了哈希之外更好的办法。于是考虑随机化，给每个数一个随机权值，查询时求区间和 \(sum\)，考查 \([sum\bmod k=0]\)，错误率为 \(\frac{1}{k}\)，随 \(30\) 次足矣。
CF2003F Turtle and Three Sequences
发现两两不同不好处理，但是单增可以处理，于是把 \(b\) 按相等关系重新随机赋值，然后跑三维偏序，一次复杂度为 \(O(nm\log^2n)\)。但单次正确率只有 \(\frac{1}{m!}\)，不能通过。
于是将 \(b\) 按照相等关系随机染成 \(m\) 种颜色，然后状压处理，这样单次复杂度为 \(O(n2^m\log n)\)，但正确率高达 \(\frac{m!}{m^m}\) 也就是只需要跑 \(26\) 次期望正确一次。跑 \(140\) 次即可通过。
AT_arc161_e [ARC161E] Not Dyed by Majority (Cubic Graph)
显然 2-SAT 可以做到 \(O(n)\) check。然后发现做不了了，于是猜测随机生成方案的正确率很高。尝试证明：发现如果存在一个点 \(x\)，设它的三个邻居为 \(u,v,w\)，每个邻居的另外两个邻居分别为 \(u_1,u_2,v_1,v_2,w_1,w_2\)，钦定 \(col(u_1)=col(u_2),~col(v_1)=col(v_2),~col(w_1)=col(w_2)\)，这样的图约占超过 \(\frac{1}{8}\)。此时，\(col(u)=0/1\) 的两类都会映射到相同的新图，也就是说至少有 \(\frac{1}{16}\) 的图是合法的。
实际上正确率比这个大得多，这只是一个下界。
AT_abc412_g [ABC412G] Degree Harmony
考虑转化问题，\(d_i\equiv a_i\pmod 2\) 可以看作是将度数一组一组删掉。因此将每个点拆成 \(a_i\) 个点，然后直接跑完美匹配就是对的。
为了最小化边数，我们给同一组点内部的边设置边权为 \(0\)，跨越两组点的边设置边权为 \(1\)，然后跑最小权完美匹配即可。
那么如何解决一般图最小权完美匹配呢，我们可以用线性代数知识来解决这个问题。给每条无向边 \((u,v)\) 设置一个未知元 \(x_{u,v}\)，然后考虑矩阵 \(A\)：
考虑 \(det(A)\)（一个多项式）的含义，若排列中包含奇环，那么将编号最小的奇环反过来，则相互抵消。由此只剩下偶环划分的贡献。若存在偶环划分则一定存在完美匹配。因此可以用行列式来判定完美匹配。实际实现中我们肯定不会维护多项式，所以给每个未知元随机一个很大的数即可。
据说最大匹配等于 \(\frac{rank(A)}{2}\)，神奇吧。
考虑如何处理最小权问题。引入一个新的未知元 \(y\)，并修改 \(A\) 的定义：
此时考查 \(det(A)\) 中 \(y\) 的非零最低次项的次数除以 \(2\) 就是答案。带 \(\sum a_i+1\) 组 \(y\) 进去把系数算出来即可，可以用拉插，也可以用高消。我写的高消，时间复杂度 \(O(n^3)\)。