P5323 光线
两个玻璃的透光率和反光率可以合并，如下列式解方程即可：
解得：
$$ \left\{ \begin{aligned} p_{12}&=\frac CA=\frac{p_1p_2}{1-q_1q_2}\cr q_{12}&=\frac EA=\frac{p_2^2q_1}{1-q_1q_2}+q_2 \end{aligned} \right. $$从 1 到 n 全合并起来即可。
|
|
NOI 嘉年华
题意
$n\le 200$
做法
$$ f(i,j)\gets \max_{k询问的时候先枚举一个包含当前活动的时间区间，然后和左右拼接，$O(n^5)$。 $$ ans=\max_{l,r,i,j}\min(i+j+in(l,r),f(l,i)+g(r,j)) $$
预处理：
$$ans(x,y)=\max_{[x,y]\subset[l,r],i,j}\min(i+j+in(l,r),f(l,i)+g(r,j))$$这样查询的时候就只需要枚举两维，瓶颈在预处理，$O(n^4)$
$f(l,i),g(r,j)$随着 i,j 增加单调减，因此上面的东西有决策单调性。双指针即可，复杂度 $O(n^3)$。
作业题
题意
给一个图，求出其所有生成树的边权和乘边权 gcd 之和 $n\le 30,w\le 152501$。
小贴士： 矩阵树定理可以在 $O(n^3)$ 时间内求出所有生成树树的边权乘积之和。这里的边权可以是任意数据类型，但要求这个数据类型支持加减乘除，并且符合整数的所有运算规律。
做法
显然是先枚举一个 gcd ，保留边权为 gcd 倍数的边，然后统计当前所有生成树的边权之和。随后做一个高维差分，就得到了 gcd 恰好为每个数的所有生成树边权之和。 现在问题变成了：给一个图，求出所有生成树边权之和。
暴力
枚举一条边，用矩阵树算出来有多少个生成树包含这个边（矩阵树中的边权赋为 1）。 复杂度爆炸，过不了。
智慧
$$ \prod (w_ix+1)\equiv (\sum w_i)x+1 \pmod {x^2} $$$$ (ax+b)^{-1}=(b-a)b^{-2}x+b^{-1} \pmod {x^2} $$复杂度 $O(n^3w)$，依然过不了，但是每次枚举一个 gcd，判断一下当前可选边数是否大于 n-1，就可过。 最多有 $\frac{ m\max(d(w)) }{n-1}$ 个数满足条件，可以通过。
P5336 [THUSC2016]成绩单
题意
$n\le 50,w\le 1000$
主要想 dp 状态
做法
$f(l,r,vl,vr)$ 表示把区间 $[l,r]$ 删到只剩下值在 $[vl,vr]$ 的最小代价。$g(l,r)$ 表示把 $[l,r]$ 全删光的代价，枚举中点转移即可。
CF1637E Best Pair
题意
给一个长度为 n 的数组 a，定义 $cnt_x$ 为 x 这个值在 a 中的出现次数。定义函数 $f(x,y)=(cnt_x+cnt_y)(x+y)$（要求 $x < y$）。 还给出 m 个无序数对，称其为“坏数对”。 对于所有“不坏的”无序数对 $(x,y)$，求出 $f(x,y)$ 的最大值。 $n,m\le 3\times 10^5,a_i \le 10^9$
做法
我们先把 a 排个序，然后相同的一段缩成一个二元组 {值,出现个数}。
想想 m=0 咋做。想了半天，这个函数似乎没法硬维护，只能往性质方向想尤其是根号方面的。
考虑枚举一个 y，看看哪些 x 可能成为答案的：
- 如果出现 $x_1>x_2$，满足 $cnt_{x_1}\ge cnt_{x_2}$ 那 $x_2$ 必然没用
因此，所有可能成为答案的 x，都在 y-1 向左的 cnt 的单调栈上。
因此，我们只需要：
- 枚举右端点 y
- 令 $x\gets y-1$
- 不断进行直到 $x=0$：
- 用 $f(x,y)$ 更新答案
- $x\gets pre[x]$
内部每循环一次，$cnt_x$ 至少增加 1，而 $\sum cnt_i=n$，所以内部的循环最多不会跑超过 $\sqrt n$ 次，复杂度 $O(n\sqrt n)$。
而有 m 的时候，我们稍微改一下即可：
- 枚举右端点 y
- 令 $x\gets y-1$
- 不断进行直到 $x=0$：
- 如果 $(x,y)$ 是好的
- 用 $f(x,y)$ 更新答案
- $x\gets pre[x]$
- 否则
- $x\gets x-1$
- 如果 $(x,y)$ 是好的
代码
考试的时候求前驱的部分写错了调半天没过，吐了
|
|