1866

李超线段树二次离线。 容易发现，将和某个点 \(x\) 相邻的边权翻若干倍后，直径所在位置有两种可能：经过或不经过该点。不经过可以跑一次直接求，否则还要分类讨论一下。 \(\operatorname{deg}_x=1\) 那么它会作为直径的一个端点。 否则 直径会从一条边进，另一条边出。 前者是简单 ......

前置知识：如果 \(p=x^a,q=x^b\)，那么 \(\gcd(p,q)=x^{\min(a,b)},\operatorname{lcm}(p,q)=x^{\max(a,b)}\)。 对于每个 \(x \in a_i\)，令 \(x\) 在 \(Y\) 中的指数为 \(d_i\)（实际上不一定） ......

Problem - 1866D - Codeforces Digital Wallet - 洛谷 不妨为选数钦定一个顺序：不同行之间无影响，列从左到右取一定不劣。 设计状态：设 \(dp_{i,j}\) 表示前 \(i\) 次操作操作到第 \(j\) 列的最大答案 转移：因为对于同一列不互相影响， ......

Problem - 1866M - Codeforces Mighty Rock Tower - 洛谷 先考虑一个 \(O(n^2)\) 的 dp 设计状态： \(dp_i\) 表示搭 \(i\) 层的期望 转移：\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j ......

link 每个车厢的人可以到的是一段区间。 题面显然提示二分答案，二分答案 \(x\)，每个车厢可以承受 \(x\) 个人，考虑如何 check 每个人能否都能到一个区间。 有一个比较显然的网络流来 check 的做法，原点向每个车厢连流量 \(a_i\) 的边，每个车厢向自己能到的区间连边，然后每 ......

待补 CF1866 C 考虑在每个边权为 1 的边 \((u,v)\) 计算贡献。考虑 \((u,v)\) 被经过 \(m\) 次，表示为 \(r_1,\dots,r_m\) 。\(r_1,r_2\) 之间的 0 边被计算 \(1\) 次，\(r_2,r_3\) 之间的 0 边被计算 \(2\) 次 ......

## 思路 首先对于 $p$ 和 $q$，他们都必须是 $Y$ 的倍数，不然 $\gcd$ 就不是 $Y$ 了。 再算出来 $\frac X Y$ 的值，当然如果 $X$ 不是 $Y$ 的倍数，那肯定无解。 因为此题特殊的输入方式，所以我们可以很轻易的得到 $\frac X Y$ 的质因子和个数。 ......