CF578F Mirror Box
Codeforces Luogu 分析 我们把顶点黑白染色，那么一面镜子就可以看成是连接同色点的一条边。 接下来给出一个结论：一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。 （比较感性理解的）证明： 首先，当黑点连边确定时白点连边一定唯一确定，所以我们只考虑黑边确定的情况。 先证必要性： 先考虑后面那个限制。如果连成了环，则环内部的边一定没有光线会穿过，所以不能有环。 再考虑前...
分类 题解 下的文章
- 首页
- 题解
SPOJ NSUBSTR2 - Substrings II
SPOJ Luogu 分析 首先思路肯定就是建 SAM，询问就找到对应位置然后求 $size$。 然而我们要支持插入，也就是要动态维护 $size$。 可以用 LCT 维护 Parent 树，每次相当于求子树和，用维护子树信息那一套即可。当然也可以直接链修改。 代码 我的写法可能有点奇怪 /kel // ==================================== // au...
洛谷4233 射命丸文的笔记
Luogu 分析 先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为 多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #includ...
CF582D Number of Binominal Coefficients
Codeforces Luogu 分析 首先有一个定理： ${a+b\choose a}$ 质因数分解后 $p$ 的幂次等于 $p$ 进制下 $a+b$ 的进位次数。 于是可以把 $A$ 转成 $p$ 进制，然后考虑数位 DP。设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 位，进位 $j$ 次，第 $i-1$ 位是否向第 $i$ 位进位，$a+b$ 是否顶着 $A$ 的上界的...
JOISC2019 简要题解
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
洛谷6295 有标号 DAG 计数
Luogu 分析 设 $f_i$ 为 $i$ 个点的 DAG 数量。 一个想法是枚举入度为 $0$ 的点的数量，有 多项式求逆即可。 现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blo...
UOJ236 【IOI2016】railroad
UOJ Luogu 分析 我们把速度看成点，铁路看成边，相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路，且加入的边从大到小连边的边数最小。 既然要存在欧拉回路，那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上，然后根据每个点两个方向被覆盖的次数连一些边即可。 然而欧拉回路还需要连通，所以我们还要求个 ...
CF1062F Upgrading Cities
Codeforces 分析 一个结论：拓扑排序时，任意时刻同时在队列中的两个点不能互相到达。 设已经访问到的点数为 $tot$，那么 如果队列中只有 $u$ 一个点，那么它可以到达剩下的 $n-tot$ 个点。 如果队列中有 $u,x$ 两个点，那么首先 $u$ 不能到达 $x$；其次如果 $x$ 的出边中有一个点 $v$ 入度为 $1$，则 $u$ 一定无法到达那个点，那么 $u$ 就不...
UOJ513 【UR #19】清扫银河
UOJ 分析 结论：如果有解，那么步数必然 $\leq m+1$。 证明：首先操作 $2$ 可以合并，所以只需要进行至多一次；其次，我们随便造一个生成森林，那么每条非树边就相当于一个简单环，从而操作 $1$ 的次数不会超过非树边数。所以总操作数至多为 $m-n+2\leq m+1$。 于是我们只需要判是否有解即可。 那么我们相当于要选若干个简单环异或 $1$，使得所有 $1$ 边变成 $0$...
洛谷3547 [POI2013]CEN-Price List
Luogu 分析 显然最短路只有三种可能： 全走 $a$ 边。 把两条 $a$ 边看成一条 $b$ 边，如果还剩一条 $a$ 边就走 $a$ 边。 全走 $b$ 边。 前两种只需要简单 0/1 BFS 一遍即可，关键在于第三种如何处理。 有一个显然的 $\mathcal{O}(m^2)$ 思路是，枚举 $u$ 的出边 $v$ 和 $v$ 的出边 $w$，如果 $u,w$ 间没有连边就用 ...