Revethere の Blog

E Roaming

题面

有 $n$ 个房间 , 开始时每个房间有 1 个人 . 人们可以在各个房间中移动 ( 不能原地移动 ) . 所有人一共移动了 $k$ 次 .

求最后每个房间的人数排列有多少种情况 .

解题思路

明显的 , 数学题 . 当所有人移动完后 , 人数为 0 的房间最多有 $\min(n - 1 , k)$ 间 . 因此可以枚举移动完后空房子的数量 . 设空房间的数量为 $i$ , 则有 $n - i$ 个非空房间放人 . 在 $n - 1$ 个空中插入 $n - i - 1$ 个板 . 对于每一个 $i$ , 有 :

$$C_{n}^{i} \times C_{n - 1}^{n - i - 1}$$

累加即可 . 另外 , 数据较大 , 需要逆元 .

F Modularness

题面

有一个长度为 $k$ 的序列 , $d_0$ ,$d_1$ , … , $d_{k - 1}$.

有 $Q$ 次询问 , 每次询问给出三个数 . 同时定义长度为 $n$ 的序列 $a_0 , a_1 , \ldots ,a_{n - 1}$ . 其中 :

$$\begin{aligned} a_j = \begin{cases} x_i & ( j = 0 ) \newline a_{j - 1} + d_{(j - 1)\ \textrm{mod}\ k} & ( 0 < j \leq n - 1 ) \end{cases}\end{aligned}$$

对于每组询问 , 求有多少个 $j$ 满足 $0 \le j < n - 1$ 且 $(a_j \bmod\ m) < (a_{j+1} \bmod\ m)$ .

解题思路

正难则反 , 统计 $a_i \equiv a_{i+1}\ (\bmod\ m)$ 和 $(a_i \bmod\ m) > (a_{i+1} \bmod m)$ 两种情况的数量 .

先进行预处理 : 将所有 $d$ 对 $m$ 取模 , 对结果无影响 .

当 $d_{i \bmod k} = 0$ 时满足第一个条件 .

$(a_i \bmod\ m) > (a_{i+1} \bmod m)$ , 因为已经将所有的 $d$ 取模了 , 相当于我们现在进行的是 $m$ 进制运算 .

一次进位只可能使前一位的值恰好增加 1 , 因此我们只需要统计发生了多少次进位即可 .

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$ 的情况 .

D Friend Suggestions

题面

某平台有 $n$ 个用户 , 有 $m$ 对是互相关注的 , 有 $k$ 对是互相拉黑的 .

对于用户 $i$ 和 $j$ , 当 $i$ 和 $j$ 满足以下条件时 , $j$ 就是 $i$ 的 “ 推荐用户 “ :

$i$ 和 $j$ 可以通过若干对互相关注的用户连接起来 .

$i$ 和 $j$ 没有互关或者互黑 .

求每位用户的 “ 推荐用户 “ 的数量.

解题思路

并查集再加上容斥原理 . 统计有多少人有 “ 推荐用户 “ 关系 , 多少人不能有该关系 , 根据容斥原理 , 答案就是不考虑条件 2 的每个用户的 “ 推荐用户 “ 的数量 , 再扫一遍互关和互黑的人 , 如果连同 , 答案把 ta 们的 “ 推荐用户 “ -1 .

E Simple String Queries

题面

给定长度为 $n$ 的字符串 $S$ , 以及 $Q$ 次询问 . 其格式如下 :

输入 1 $i_q$ , $c_q$ , 将 $S$ 的第 $i_q$ , 位字符改为 $c_q$ ;

输入 2 , $l_q$ , $r_q$ , 询问区间 $[l , r]$ 不同的字符个数 .

解题思路

开 26 个独立的树状数组 , 每一个存放该字符出现的位置 . 在询问的时候直接询问树状数组 $[l,r]$ 的和 ( $ans$ ) , 如果 $ans > 0$ , 则把 $ans + 1$ 输出即可 .

D String Formation

题面

开始有一个只包含小写字母的字符串 $S$ .

接下来执行 $Q$ 次操作 , 对于每次操作输入一个数 $T$

• 如果 $T = 1$ , 将 $S$ 反转 .
  如果 $T = 2$ , 给定一个数 $F$ 和一个小写字符 $c$

• 如果 $F = 1$ , 将 $c$ 放在 $S$ 的开头

• 否则放在末尾

输出所有操作结束后的字符串 $S$ .

解题思路

水题一道 . 反转过后 , 两个操作就相当于换一下 . 只需要用一个变量来记录这个字符串是否被反转 , 被反转偶数次相当于没反转 . 注意是反转操作而不是字符串 .

E Divisible Substring

题面

给定一个质数 $P$ 和一个字符串 $S$ .

求有多少个 $S$ 的字串 $T$ 满足将 $T$ 视为十进制数后是 $P$ 的倍数 .

解题思路

该题关键在于线性求字串数量的方法 . 在大多数情况下 , 如果两个字串所对应的数字 $\bmod\ P$ 所得的余数相等 , 且一个串是另一个的末尾某一段 , 则他们相减后得到的串符合要求 . ( 2 和 5 除外 , 需特判 ) .