Fanyi's Blog

原题链接 有一趟列车有 \(M+1\) 个车站，从 \(0\) 到 \(M\) 编号。有 \(N\) 种商品，第 \(i\) 种只在编号 \([l_i,r_i]\) 的车站出售。一辆列车有一个预设好的系数 \(d\)，从 \(0\) 出发，只会在 \(d\) 的倍数车站停车。对于 \(d\) 从 \(1\) 到 \(M\) 的列车，求最多能买到多少种商品。 \(1\le N \le 3\times 10^5;1\le M\le 10^5;1\le l_i\le r_i\le M\)。 我们考虑对于每个 \(d\)，如果区间 \([l_i,r_i]\) 有 \(r_i-l_i+1\ge d\)，那么显然它一定会被覆盖，我们直接统计答案。 我们考虑 \(r_i-l_i+1<d\) 的情况，显然它只会被覆盖一次，所以我们只要求这些区间与这些点的交点个数即可。 于是我们由长度从小到大枚举区间，放入…

原题链接 题意大概就是给你一个排列 \(p\)，你每次可以找到 \(p\) 中相邻两个数并将其移至另一个初始为空的队列的开头，让最终 \(p\) 的字典序尽量小。 过程大概就是这样： 由于字典序大小是从前往后决定的，所以我们考虑从前往后确定这个序列，也就是将题意中的过程倒着做。 我们考虑在某一状态下，选择的两个数在原序列中是 \(p_l,p_r\)，那么再次之前的选择中，不可能出现选择的数为 \(p_{a_l},p_{a_r}\) 使得 \(a_l<l<a_r\) 或 \(a_l<r<a_r\)。 于是我们发现倒着考虑是，选择 \(p_l,p_r\) 时就是把序列分成了 \([1,l-1],[l+1,r-1],[r+1,n]\) 这 \(3\) 段，这 \(3\) 段相互独立。 我们考虑怎样的 \(<l,r>\) 是合法的。显然就是…

一道有趣的题。 查看题目 PDF 3s+O2 原题大概是这道。 看到模 \(3\) 显然是出题人精心构造的。 于是我们打出一张组合数模 \(3\) 的表。 好多 \(0\) 啊～ 于是我们考虑如何快速求出组合数不是 \(0\) 的位置。 先说一下我考场上想到的 \(\log\) 做法： 我们考虑 lucas，对于组合数 \(\binom{m}{n}\)，其实就是 \(\binom{M_i}{N_i}\) 的乘积，其中 \(M_i,N_i\) 表示 \(m,n\) 在 \(3\) 进制下的第 \(i\) 位。 我们发现 \(\binom{M_i}{N_i}\) 只要有一位是 \(0\)，最终结果就是 \(0\)，所以我们只要枚举 \(m\) 后枚举三进制下每一位是比 \(m\) 小的 \(n\) 就行了，这样每次找是 \(\log\) 的，所以复杂度是…

给定一张无向图，要求把边染成黑白两色，要求所有白色边构成的子图没有环，且所有黑色边构成的子图没有环。 多组询问，输出是否有解。 \(n\le 500,m\le 2n,T\le 10\)。 显然，由白边构成的图是一个森林，黑边构成的图也是个森林。 显然森林所有的导出子图也是森林。 那么显然图是一个森林的充要条件为其最大导出子图的 \(|E|-|V|\le -1\)。 我们考虑原问题，如果一张图 \(G\) 要有解，那么 \(G\) 的所有导出子图都要有解，且该图的 \(|E|\le 2(|V|-1)\)，也就是让黑白两种颜色都能是一片森林。 有了这个有理有据的性质，我们就把问题转化成了：对于图 \(G\)，定义 \(\rho_G=|E|-2|V|+2\)，求出一张图所有导出子图 \(\rho?\) 的最大值。 我们考虑网络流，\(S?\) 向所有原图的边（看作点）连边，容量为 \(1?\)，…

一道有趣的贪心题。 查看题目 PDF 给你两种瓷砖 \(a,b\)，每种瓷砖有 \(n\) 块，每块瓷砖有两个属性：高度 \(h\) 和价值 \(p\)。 现在要求你把这些瓷砖重新排成两行（\(2\times n\)）。前一行放瓷砖 \(b\)，后一行放瓷砖 \(a\)。 要求从左到右 \(p\) 递增（单调不减），对于任意一个位置 \(i\)，后面的瓷砖要比前面的瓷砖高。 求一种方案或输出无解。 \(n\le 5\times 10^5\) 对于一段 \(p\) 相同的区间，我们可以将里面的瓷砖随意调换。 考虑如何贪心。 我们发现有两种不同的情况，我们的目的不同： 此时我们是想让匹配完 \(a\) 中 \(p=2\) 情况后，\(b\) 中剩余的 \(p=3\) 的瓷砖的 \(h\) 尽量小。 我们可以将 \(a\) 中 \(p=2\) 的每块瓷砖都找到 \(b\) 中一个恰好比它小的瓷砖…

原题链接 \(n(n\le 10^5)\) 个球排成一排，第 \(i\) 个球有颜色 \(c_i(c_i\le n)\) 和重量 \(w_i(w_i\le 10^9)\)。 Snuke 每次可以选择两个颜色相同，且重量之和不超过 \(x\) 的球，交换他们的位置。 Snuke 每次可以选择两个颜色不同，且重量之和不超过 \(y\) 的球，交换他们的位置。 问可以得到多少种不同的颜色序列。\(1\le x,y\le 10^9\)，答案对 \(10^9+7\) 取模。 我们考虑什么时候连个球能进行交换。 显然如果有三个球 \(a,b,c\)，如果 \(a\) 与 \(b\) 能交换，\(b\) 与 \(c\) 能交换，那 \(a\) 与 \(c\) 一定能通过 \(b\) 的“媒介”交换（\(a\) 先于 \(b\) 交换，\(b\) 与 \(c\) 交换，\(a\) 与 \(b\) 交换）。…

题目链接 有一个长度为 \(L\) 的圆环, 上面有 \(n\) 个蚂蚁, 位置分别为 \(x_i\)，运动方向为 \(d_i\)，\(1\) 表示顺时针，\(2\) 表示逆时针。每只蚂蚁将会同时开始以单位速度运动，如果两只蚂蚁相遇，那么它们会改变自己的方向继续运动。求 \(T\) 秒之后每只蚂蚁的位置。 \(1\le n\le 10^5;1\le L,T\le 10^9;0\le x_1<x_2<\cdots<x_n\le L - 1\)。 显然我们先来看如果没有标号，那么可以把两只蚂蚁的“掉头”无视掉，这样我们就已经知道了蚂蚁的位置。 不难发现每只蚂蚁的相对位置不变，即它左边和右边的蚂蚁是不会变的。 于是我们只要确定其中一只蚂蚁即可。 我们可以记录一下坐标最小的蚂蚁是那只，即越过 \(0\) 坐标的蚂蚁有几只，这样就确定了一只蚂蚁。

题目链接 给出一颗 \(n(n\le 10^5)\) 个节点组成的树，每个节点都可以被染成白色或者黑色。 有高桥（先手）和青木（后手）两个人，高桥可以把任意某个点染成白色，青木则可以把任意一个点染成黑色，每个点只可染色一次。 当所有点都被染色后，只执行一次执行以下操作： 若操作完毕后仍还有白点存在，即高桥（先手）胜，反之则青木（后手）胜。 现在给出这棵树，问当前此树是先手必胜 or 后手必胜。 问题显然就是青木不能让任意一个白点旁边没有黑点。 如果该树有完美匹配，那么显然是后手赢。因为不管先手选什么，后手只要选先手对应的点就可以。 于是我们就来考虑没有完美匹配的情况。 最特殊的应该是叶子节点，因为只有一个点与它相邻。如果叶子节点是白点，那么叶子节点的“父亲”必须是黑点；而如果叶子是黑点，那么叶子节点的“父亲”必须是白点。这里的“父亲”是指它相邻的点。 我们考虑先手先任意一个叶子节点的“父亲…

题目链接 给一个 \(n(n\le 15)\) 个点 \(m\) 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 \(1\) 到 \(n\) 只有 \(1\) 条路径（不经过重复点），问割掉的边权和最小是多少。 问题其实就是需要保留的边权和最大。 问题是有关点集+路径的，不难想到状态：\(f_{i,j}​\) 表示遍历了集合 \(i​\)，这条唯一的路径的已经是从 \(1​\) 到 \(j​\) 的答案。 我们考虑选择路径的形状，大概应该应该是这样的： 就是 \(1\sim n\) 的一条，然后中间许多分叉，连向一些连通块，而这些联通块中所有的边都连上。 于是我们考虑转移。 当 \(j=1\) 时，\(f_{i,j}=E_i\)，其中 \(E_i\) 表示 \(i​\) 集合中所有边的权值和。 可以连下一个链上的点：…

我们定义一棵树的删除序列为：每一次将树中编号最小的叶子删掉，将该节点编号加入到当前序列的最末端，最后只剩下一个节点时将该节点的编号加入到结尾。 例如对于上图中的树，它的删除序列为：2 4 3 1 5。 现在给出一棵 \(n\) 个节点的树，有 \(m\) 次操作： 第一行两个正整数 \(n,q(1 \leq n , q \leq 200000)\) 表示树的点数和操作数。 接下来 \(n-1\) 行每行 \(2\) 个正整数 \(u,v(1 \leq u,v \leq n)\) 表示树上的一条边。 接下来 \(q\) 行每行描述一个操作。 每一个询问输出一行。 对于 when v 询问，输出一个正整数表示 \(v\) 是当前删除序列的哪一个元素。 对于 compare u v 询问，如果 \(u\) 在删除序列中更靠前则输出 \(u\)，否则输出 \(v\)。 显然在任意时刻最大的那个节点…