D Pairs
题面
$n$ 个数两两相乘的结果共有 $\dfrac{n(n - 1)}{2}$ 种 , 求第 $k$ 小的乘积 .
输入 $a_i$ 到 $a_n$ .
解题思路
求第 $k$ 小 , 相当于求第 $\dfrac{n(n - 1)}{2} - k + 1$ 大 .
考虑二分 , 记该值为 $mid$
当 $mid < 0$ , 则任意 $a_i$ 为整数或 $0$ ,都满足要求 . 然后对于每个 $a_i > 0$ , $a_j < 0$ 的组合是否大于 $mid$ .
当 $mid = 0$ , 除了 $a_i > 0$ , $a_j < 0$ 的组合都满足要求 .
当 $mid < 0$ , 当 $a_i$ 和 $a_j$ 同号时满足要求 .
复杂度 : $(n \log n)$ .
E Payment
题面
有 $10^{100} + 1$ 种纸币 , 面值分别为 $10^0$ , $10^1$ , $10^2$ … , $10^{100}$ .
给定正整数 $n$ , $f(x)$ 表示 $x$ ( 付的钱 ) 在十进制下各个数位的和 , 求一个正整数 $x$ , 满足 $x \geq n$ 且最小化 $f(x) + f(x - n)$ .
解题思路
$dp$ 一道 , 转移方程如下 :
$$dp_{i,0} = \min (dp_{i - 1,0} + a_i,dp_{i - 1,1} + a_i + 1)$$
$$dp_{i,1} = \min (dp_{i - 1,0} + 10 - a_i ,dp_{i - 1,1} + 10 - a_i - 1)$$
F Perils in Parallel
题面
有 $n$ 个电灯 , 编号为 $1$ 到 $n$ , 第 i 个电灯在 $a_i$ 处 , 状态为 $b_i$ ( 1 或 0 ) .
有 $m$ 个开关 , 编号为 $1$ 到 $m$ , 第 $i$ 个开关控制 $[l_i,r_i]$ , 如果按下该开关 , 则该区间内电灯状态取反 .
求是否有可行解 , 使得所有电灯状态为 0 . 有则输出方案 , 否则输出 -1 .
解题思路
在异或的意义下进行差分 , 那么区间的操作就会变成点的操作 . 即给一个 01 串和一些点对 , 将统一对数 $\operatorname{xor}1$ , 得到全为 0 的串 .
既然有点对了 , 那就直接上无向图了 . 即在无向图中选择一些边 , 将这些边 $\operatorname{xor}1$ , 问能否得到一张全 0 图 .
将其简化为一棵树 , 进行搜索 , 用所有与该点对有关系的点对进行修改 . 由于每次操作奇偶性不变 , 所以如果 $\operatorname{xor}$ 的值不为 0 则无解 .
另外 , 差分后 $n + 1$ 对答案是没有影响的 , 所以要先跑一个 $n + 1$ 的情况 .