ABC287Ex - Directed Graph and Query
顺序枚举点,记 \(a_{i,j}\) 表示从 \(i\) 点出发能否到达 \(j\) ,从初始对于每条边 \((u_i,v_i)\) ,有 \(a_{u_i,v_i}=1\) ,然后跑 \(\text{floyd}\) 即可,\(\text{bitset}\) 优化一下即可做到 \(O(\frac{n^3}{64})\) 。
ABC286G - Unique Walk
将不在 \(S\) 里的边加上缩点判欧拉回路即可。
ABC286Ex - Don't Swim
将起点、终点跟多边形的每一个点放在以其跑凸包,如果两个点都在凸包内,就是两边取个 \(\min\) ,否则就是两点直线距离。
CF1777E. Edge Reverse
考虑如果缩完强联通分量之后,只存在一个无入度的点的话,就符合条件。直接二分答案,每次判定就是将边权小于二分值的边加上反向边,跑 \(\text{tarjan}\) 即可,时间复杂度 \(O((n+m) \log w)\) 。
CF1777F. Comfortably Numb
此题直接考虑以每个点为左端点的区间并不好做。由于所求有一个 \(\max\) ,我们可以直接通过枚举区间的最大值来解决。这个可以使用笛卡尔树。注意异或的性质,区间 \([l,r]\) 异或和可以转化成 \(r\) 的前缀异或和异或上 \(l-1\) 的前缀异或和。
因此我们对于笛卡尔树上的每一个节点, 用 \(\text{0-1 Trie}\) 维护这个节点子树内所有点的前缀异或和,向父节点合并更新的时候启发式合并就行了。时间复杂度 \(O(n \log n \log w)\) 。
CF1780E. Josuke and Complete Graph
如果小于等于 \(l\) 的 \(a\) 在 \([l,r]\) 的子图中出现,那么等价于:
\[\left \lfloor \frac{r}{a} \right \rfloor-\left \lfloor \frac{l-1}{a} \right \rfloor \geq 2 \]对于后者由于 \(l \leq 10^9\) 不同的取值只有 \(\sqrt{10^9}\) 种,直接数论分块就可以做了。
CF1780F. Three Chairs
考虑容斥,先让答案是 \(n \choose 3\) ,然后去除掉所有的以 \(a(a>1)\) 为公约数的不合法的方案数,容斥系数是 \(\mu(a)\) 。
CF1780G. Delicious Dessert
\(\text{SAM}\) 板子题,预处理出 \(1-n\) 所有数的约数即可。
CF1790G. Tokens on Graph
只考虑可行的点跑最短路,然后在看某个出发点边上可行点数量,如果有连续两个点在边上就可以走无限次。
标签:frac,log,text,异或,1.29,即可,Graph From: https://www.cnblogs.com/oscaryangzj/p/17080850.html