MENU

题解

Solution. CF1951G Clacking Balls

Description

有 $m$ 个篮子放在一个环上,篮子按顺时针顺序编号为 $1\sim m$。有 $n$ 个球,第 $i$ 个球放在篮子 $a_i$ 中,$a_i$ 互不相同。接下来反复进行如下操作:从 $1\sim n$ 中等概率选出一个数 $i$,若球 $i$ 已被扔掉则什么都不做;否则将球 $i$ 移动到顺时针方向的下一个篮子里,如果下一个篮子里本来有一个球 $j$,则将球 $j$ 扔掉。进行一次上述操作总是花费 $1$ 单位时间,所有篮子中只剩下一个球时结束此过程。求过程持续的期望时间,答案对 $10^9 + 7$ 取模。

$1\le n\le 3\times 10^5, n\le m\le 10^9$

Read More

Solution. LG10220 [省选联考 2024] 迷宫守卫

Description

给一棵 $n+1$ 层的完全二叉树(共 $2^{n+1}-1$ 个结点,$2^n$ 个叶子),结点从上到下,从左到右编号为 $1\sim 2^{n+1}-1$,每个非叶结点有一个激活代价 $w_i$,每个叶子有一个权值 $q_i$,所有 $q_i$ 构成 $1\sim 2^n$ 的排列。Alice 和 Bob 在这棵树上玩游戏,Alice 可以用不超过 $K$ 的代价激活一些结点,随后 Bob 会对这棵树进行 dfs。对于 Alice 激活的结点,Bob 必须先走左儿子再走右儿子;其余时候,Bob 可以任意决定 dfs 顺序。

按照 Bob 访问叶子的顺序将所有 $q_i$ 排成序列 $Q$,Alice 希望 $Q$ 的字典序最大,Bob 希望 $Q$ 的字典序最小,问最终的 $Q$ 是什么。

$T$ 组数据。

$1\le T\le 100,1\le n\le 16,1\le \sum 2^n\le 10^5,0\le K\le10^{12},0\le w_i\le 10^{12}$

Read More

Solution. LG10218 [省选联考 2024] 魔法手杖

Description

给你 $n$ 个 $[0,2^k)$ 中的整数 $a_1,a_2,\dots,a_n$,第 $i$ 个数对应代价 $b_i$。

你需要选取一个 $U=\{1,2,\dots,n\}$ 的子集 $S$,满足 $\sum_{i\in S} b_i\le m$,以及一个 $[0,2^k)$ 中的整数 $x$,最大化 $\min\{\min_{i\in S}\{a_i+x\},\min_{i\in U\setminus S}\{a_i\oplus x\}\}$。

共 $T$ 组数据。

$1\le n\le 10^5,1\le \sum n\le 5\times 10 ^5,0\le k\le 120,0\le m\le 10^9,0\le b_i\le 10^9$

Read More

Solution. LG10199 [湖北省选模拟 2024] 时与风 / wind

Description

给定 $n$ 个点 $m$ 条边的有向图,第 $i$ 条边有开放时间 $[O_i,C_i]$ 和到达时间 $[L_i,R_i]$,可以经过相邻的两条边 $i,j$ 当且仅当 $[L_i,R_i]\subseteq [O_j,C_j]$,给定起点 $S$,第一条边不受限制,求哪些边可达。

$1\le n,m\le 5\times10^5,1\le O_i\le C_i\le 10^9,1\le L_i\le R_i\le 10^9,{\color{yellow}1\le O_i,L_i\le 20}$

Read More

Solution. LG10201 [湖北省选模拟 2024] 永恒 / eternity

Description

给一张 $n\times m$ 的网格,每个格子上有数字 $0\sim 9$ 或 $-1$,其中 $-1$ 表示该格子被封锁。可以在网格上走出一条路径,要求相邻格子四联通,可以经过相同格子,不可以经过被封锁的格子,路径的权值为将格子上的数字按顺序拼成十进制数并对 $P=1145141$ 取模的值。支持两种操作:

  1. 修改一个格子上的数。
  2. 查询是否存在从 $(sx,sy)$ 到 $(tx,ty)$、权值为 $v$ 的路径。

操作共 $q$ 次。

$1\le n,m\le 500,1\le q\le 2\times 10^5$

Read More