Baka's Blog

其实学这个并不能帮我改变NOI要打铁这件事 从19年集训队论文里抄了一下。省略证明，记一些不严谨，仅仅是能用级别的结论。 杨表的插入 比如插入行，扫每一行，找到比它大的最小值，交换一下继续下一行。注意到杨表的单调性，可以二分。b找不到就丢这一行后面 杨表与LIS 杨表第一行的长度就是LIS。

人比较菜，找的题也垃圾，轻点喷 [GYM102114A] Always Online 题意：仙人掌，求最大流异或和。 考虑环，那么注意到如果选环，环上最小的边一定会被割，直接把它割开，边权加在其它边上。之后按边权合并即可 [CF1240F] Football 题意：给一张图，选一些边，为每条边分

丁香之路 假装已经知道了要走哪些边，可以发现答案就确定了。那么问题就是确定走哪些边。首先输入的肯定要走，并且还要再加一些，使得可以形成欧拉路。 欧拉路不好处理，就从T到S连一条边变成欧拉回路。欧拉回路需要满足两个条件：度数是偶数，联通。 从小往大扫，如果两个点的度数都是奇数，就让它们连一条边。之后图

退役前挣扎一下 说起来高一寒假就学过一次这玩意，学一次忘一次 其实就是求$x^2 \equiv a \pmod p$。 有不少算法的样子，比较常用的应该是Cipolla算法，可以求解模奇素数的二次剩余。 首先冷静一下：考虑原根，那么就是要求$2x’ \equiv a’ \pmod \varphi$。

来自一个前缀和写错选手的良心馈赠 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

丢链接跑路 例题：CF906E 把串交叉成新串，原串的反转对应新串的回文，套个板子上去

[清华集训2017]榕树之心 “榕树还是当年的榕树，你却不是当年的你了” 先只算根，发现就是要把子树配对，使得根不会动。那么从下往上考虑，因为在比较深的树里如果能匹配很多对，上面需要更多的时候就可以随便减少一些给上面用。那么尽量在深的地方匹配是优秀的。 考虑把子树分成若干堆，考虑用最大的一堆和其

[NOI Online#3]优秀子序列 首先易知$i \And j=0$等价于$i j = i +j$。于是就是子集卷积。$O(3^n)$卷一下就行了。注意特判$0$。考场代码不知道为什么60分 考虑使用形式幂级数。冷静分析一下：首先一个数不能选两次，因此随便选$k$次，除以$k!$，就得到了$k$

大质数取模有很多奇妙的姿势，其中比较菜的一个就是裸exLucas（然而我还是不会）。 exLucas适用于模数分解后不大的情况。 大概姿势是这样的：模数$P$分解为$p_1^{a_1} p_2^{a_2}…$，分别求解后用CRT合并。 那么求解$\binom{n+m}{n}$，只需要求解形如$n!

[HNOI/AHOI2018]转盘 冷静分析一下：在原地呆一会再走比中间呆着优秀。倍长，钦定从$x$开始走，等待时间$s=\max_{i=x}^{i+n-1} \lbrace A_i - i + x \rbrace$。再冷静一下发现直接求到$2n$也是没问题的。 之后就是一个神秘转化了：反过来考虑$