洛谷4244 [SHOI2008]仙人掌图
Luogu 分析 设 $f_i$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。 如果当前边是桥，直接转移，同时更新 $ans$ 。 否则当前边在环上，先不处理。 假设我们现在在 $u$，$v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。 我们把这个环找出来单独考虑。 先考虑怎么用环上的点更新答案。 要求的实际上是 $\max\{f_i+f_j+dis(...
分类 题解 下的文章
- 首页
- 题解
洛谷5332 [JSOI2019]精准预测
Luogu LOJ 分析 每个人在每个时刻只有 $2$ 种状况，考虑 2-SAT 。 设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。 另外还有一个隐藏条件：如果 $x$ 在 $t$ 时刻活着，那么在 $t-1$ 时刻也活着；如果 $x$ 在 $t$ 时刻死了，那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。 问题变为在建好的图上，从 $(...
CF1110G Tree-Tac-Toe
CodeForces 分析 以下所有图片均来自官方题解。 首先初始就为白色的点不太好搞，考虑怎么样把它当成无色点。 假设 $A$ 是一个白色点，我们在它上面挂 $3$ 个新点： 可以发现这样子对游戏胜负没有影响。 可以这么考虑：如果白方把 $A$ 涂白了，那么黑方只能把 $B$ 涂黑。所以这就相当于多用一轮回到了给定的状态。 现在是一个没有颜色的树，考虑这上面的胜负情况。 显然黑色不可...
洛谷5302 [GXOI/GZOI2019]特技飞行
Luogu LOJ 分析 首先考虑怎么求出所有交点。 注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ 。 那么可以用 set 来维护 $y_{x,1}$ ，然后暴力求出所有交点。 因为交点个数 $\leq 500000$ ，所以可以过。 容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立的。 先考虑怎...
洛谷2250 [ZJOI2016]旅行者
Luogu 分析 考虑对网格图进行分治。 假设当前分治的范围是 $(lx,ly)\sim(rx,ry)$ ，询问的范围是 $ql\sim qr$ 。 找到矩形范围的长边，然后用一条中轴线切成两半。 这时每个询问有两种情况： 查询的两点不在中轴线同侧，此时最短路一定经过了中轴线上的某个点。那么对于中轴线上的每一个点，跑最短路，然后更新询问区间内每个询问的答案。 查询的两点在中轴线同侧，此时最...
CF835F Roads in the Kingdom
CodeForces 分析 直接考虑删哪条似乎很不可做的样子，我们考虑枚举删掉哪条然后快速算直径。 把环拉出来，这样子每个环上的点就对应了一颗子树。 显然我们只能删掉环上的边。这里为了表述方便，把环上的点顺时针重编号为 $1\sim sz$ 。 假设当前删掉了 $(x-1,x)$ 。设 $f[i]$ 表示 $i$ 的子树中的节点到 $i$ 的最长路径长度， $sum[i]$ 表示 $i$ 逆...
CF1097F Alex and a TV Show
CodeForces 分析 对每个集合维护一个 bitset，第 $i$ 位表示 $i$ 作为因数的出现次数的奇偶性。 $1$ 操作预处理后直接赋值即可； $2$ 操作直接异或即可； $3$ 操作直接与即可。下面考虑 $4$ 操作怎么做。 设 $f(i)$ 表示 $i$ 作为因子的出现次数， $g(i)$ 表示 $i$ 的出现次数，那么有 $f(x)=\sum\limits_{x|d}g(d...
洛谷4688 [Ynoi2016]掉进兔子洞
Luogu 分析 显然一个询问 $(l_1,r_1,l_2,r_2,l_3,r_3)$ 的答案是 $(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times size$ ，这里的 $size$ 表示三个区间内出现了多少个公共的颜色。 那么只需要考虑如何求 $size$。 首先对所有数离散化，令它离散化后的值为小于等于它的数的个数。 然后当加入一个值 $p$ 的...
洛谷3306 [SDOI2013]随机数生成器
Luogu BZOJ 分析 已知 $X_{i+1}\equiv aX_i+b\pmod p$ 。 两边加上 $\frac{b}{a}$ 后再乘上 $a$ ，变为 $a$、$b$、$X_1$、$X_i$（就是题目中的 $t$） 全部已知，BSGS 解出 $i$ 即可。 然后还有一些特判： $X_1=t$，答案为 $1$ 。 $a=0$，此时对于任意的 $i$ ，都有 $X_i=b$ 。所以...
洛谷2371 [国家集训队]墨墨的等式
Luogu 分析 同余类最短路。 设 $a$ 中的最小值为 $k$ 。容易发现，如果能表示出 $xk+t\;(0\leq t<k)$ ，那么也能表示出 $(x+1)k+t$ 。 把 $t$ 看做余数，然后对于每个 $a_i$ ，从 $t$ 向 $(t+a_i) \bmod k$ 连一条边权为 $a_i$ 的边。 然后跑 SPFA 求出最短路，再对每个余数统计答案即可。 代码 //It ...