Baka's Blog

[WC2014]紫荆花之恋 题目要求$r_i + r_j \geq dis_{i,j}$的点对有多少，那么考虑枚举路径上一个点把路径分开，就是求$r_i -dis_i \geq r_j + dis_j$的点对数量。那么在这个点上维护平衡树，就可以二分查找了。去重，考虑在儿子节点上挂一个平衡树，维护的

[NOI2012]骑行川藏 首先要知道偏导数，就是一个很多变量的函数求关于一个变量的导数，把其他变量看作常数。记为$\frac{\delta f}{\delta x}$ 有一个拉格朗日乘数法。给定$f(x_1,x_2,…,x_k)$，并且要求满足$g(x_1,x_2,…,x_k)=c$，求$f$的极

[CTSC2010]性能优化 首先题目要求的是$AB^C$，乘法为循环卷积。众所周知DFT有循环卷积的性质，只需要快速求出DFT就行了。 题目里提到了$n+1$为质数，且$n$的质因子$\in \lbrace 2,3,5,7 \rbrace$。那么求出$n+1$的一个原根，考虑NTT。 在常用的NT

[WC2014]时空穿梭 如果推式子足够熟练的话，可以一路推出来的。但是我推着推着就迷惑了。。 首先要找的是直线。那么确定直线最好的办法是确定两个端点。考虑枚举两个点，坐标分别为$(a_1,a_2…),(b_1,b_2,…)$，那么必须有$\exists i, a_i < b_i$。确定两个点之后，

[HNOI2019]白兔之舞 这个套路那个套路 叠加起来就是毒瘤题 各种奇怪东西加在一起的题。 考虑钦定走了$m$步的方案数。令$f_m$为连着走了$m$步的方案： $$\sum_{i=0}^L \binom{i-1}{L-1} f_m = \binom{L}{m} f_m $$ 显然$f$k可以矩

[Makoto Soejima Contest 1, Japanese Grand Prix, by rng_58][CF100958I] Substring Pairs 上面的来源有长长的一串，是因为在陈老师WC课件里见过这个题，来源很迷，全粘贴上了… 考虑一下给定$T$怎么求有多少个$S$，令$

一般图最大匹配 比较摸，不是很有学带花树的动力，网上冲浪冲到了随机算法： 首先如果给定的图没有环，直接做类似二分图匹配的匈牙利肯定是对的。如果图中的环都是偶数，增广一下也不会有问题。（二分图就是偶环） 但是如果图中有奇环，可以发现绕环增广会挂掉。。 举个例子，一个大小为$3$的环，选了其中一条边。把

【UER #8】雪灾与外卖 模拟费用流板子题。 首先可以建立一个简单费用流模型。把点按坐标排序后，不难发现，最终匹配方案不交叉。 那么可以考虑将两类点排序，对费用流的过程进行模拟。模拟的难点在于退流。 考虑一个$x$点。先把它向左边没用匹配的$y$中最优秀的匹配。它的贡献是$x_i+v_j$，其中$

关于为什么用WSL：曾经是用Manjaro的，但是某次下载东西，硬盘不够了，就把Linux删了…实际上对于OI来说，WSL已经够用了，可以同时享受到Linux写代码，和Windows的易用。 安装 其实安装没什么问题…直接装Ubuntu就好…换个国内源什么的 zsh 装好zsh和ohmyz

CF888G Xor-MST 求奇怪边权的MST，考虑Boruvka。 考虑第一次Boruvka的过程。每个点选最小边，合并。把所有点放在Trie上，则体现为叶子处的点合并。 合并叶子后，Trie产生了新的叶子，进行下一次Boruvka即可。 考虑Trie上一个点，可以计算合并它左右儿子的贡献。只需