文章

//失踪人口回归系列 1. 题目 传送门=￣ω￣= 2. 题解 没想到一个月没摸过 C++居然 1A 了（C++是什么？俄文吗？）思路很简单啦，单调栈找出所有的有序对。 维护一个单调递减的栈 对于当前元素，如果栈顶元素小于（或等于）它，那么它们就是一对合法有序对，然后把栈顶元素弹出。如果栈顶比当前 阅读更多…

树上启发式合并 对于如下的一些问题，树链剖分、树上差分等常见手段就不是很好应对了： 询问树的每个子树内有多少种颜色 询问树的每个子树内出现至少 k 次的颜色有多少种 询问树上最长的路径，该路径上每个颜色的节点出现了偶数次 询问树的每个子树内某个深度的节点有多少个 询问树的每个子树内出现次数最多的颜色 阅读更多…

Knots Subtract: 给定一个绳环构成的图形，求这个绳环能否通过拓扑变换变为一个环。绳环被二维展开在一个平面内，有若干个交点，每个交点处的绳子恰好两根。交点个数不大于 $5000$。 Ideas: 一个比较简单的想法是，我们模拟人解绳子的过程。具体怎么解呢？ 1. 如果我们发现，通过平移某 阅读更多…

传送门喵 吐槽：竟然有一本教种菜的书跟这题同名 蛮巧妙的一道题。 首先一个结论，将每个菜再加一个位置 id，那么菜的高度合法的一种方案的最小交换次数=此时菜的 id 的逆序对数。 证明：初始的时候 id 数组逆序对个数的，考虑归纳法，当逆序对个数为 $k-1$的时候，我们证明有效的一次交换必定会使 阅读更多…

传送门 题意大概是选 $\{2,3,\cdots,n\}$这个集合里的两个子集使得两个自己之间的数互相互质的方案数。 首先我们来考虑 30pts 的做法。 容易发现，两个子集的数互相互质当且仅当两个子集里的质因子集合没有交集（废话 因为我们知道，当 $n\leq 30$的时候质数 阅读更多…

传送门 真的是神仙题，看了 PoPoQQQ 的题解才会做的 我们首先发现一个显然的性质，$4\times 7$的矩阵是只有可能有最多 8 个局部极小值的，否则随便鸽巢一下就能知道一定是不合法的状况。 我们考虑状压这 8 个位置是否填了数，我们发现你按表格顺序填是基本送命的，所以我们考虑从 $1$到 阅读更多…

这里是传送门 求每个点遍历一遍关键点的最小长度。 我们先假设，如果它遍历完关键点，要回到原来的点的话，那么经过的每条路径显然是都被经过两次的，因为这里不要求回到原点，并且这样的路径最小的时候生成的路径集合是唯一的，也就是说对于每个原点和所有关键点，经过它们的路径所产生的生成树是固定的，并且每条边被经 阅读更多…

考场上看到 D2T3 的时候就蒙了，觉得是什么毒瘤计数法，后来听别人说是猫锟在去年冬令营的时候讲的毒瘤算法动态 dp 板子题？然后感觉自己好亏（去年我都去不了冬令营 QAQ）于是决定学一学。 顾名思义，动态 dp，就是给你一个可以静态 dp 的题，然后带一些修改操作和询问操作来瞎搞的。一般修改的东西 阅读更多…

随着 NOIP2018 的落幕，我也要正式向陪伴我多年的 OI 说再见了。 也许是运气不佳，也许是心态问题，更可能是个人能力问题。 我也许会后悔曾经的颓废，曾经的虚度光阴，也许会痛恨无所事事的自己。 但是现在这些都不重要了。 因为，XZY 已经退役了。 从今天开始，从 2018 年 11 月 11 阅读更多…

题解 我并不觉得这次 NOIP 的题目有多好。 再说我也不是都会做。 所以写个屁的题解。 感悟 国外的大牛们出题的套路： Tom： 我想到了一个炒鸡有意思的题目呗。 Jerry：啥题目啥题目？说来听听？ Tom：就是这样，我给你一棵树，现在所有点都是白色的。你可以不停选择两个相邻且同色的点，将它们同 阅读更多…