【题解】[AHOI2022] 山河重整
题目链接:[AHOI2022] 山河重整
题意:
计数有多少个元素在 $[1,n]$ 的集合,其 $01$ 背包能表示 $[1,n]$ 中的所有数。
$1\le n\le 5\times 10^5$,时间限制 $\text{3s}$。
题目链接:[AHOI2022] 山河重整
题意:
计数有多少个元素在 $[1,n]$ 的集合,其 $01$ 背包能表示 $[1,n]$ 中的所有数。
$1\le n\le 5\times 10^5$,时间限制 $\text{3s}$。
联合省选 $2021$ 考场上,本人因为没有理解 $\text{ranklist}$ 一题的题意,导致至少失去了 $\mathcal{O}(n!)$ 的 $60\text{pts}$;$\text{dominator}$ 甚至因为心态崩掉,出现了爆零的情况,最后连公示都没上。
因此,对今年的省选,我其实是有很大期待的,我也想在省选公示上看到自己的名字,也想证明“看起来没有想象的难”。
高二赛季的 $\text{round 2}$,希望能实现愿望。
题目链接:[BJOI2018] 双人猜数游戏
题意:
提交答案题。
现有 $\text{Alice},\text{Bob}$ 两人,要猜出两个数字 $m,n\ (m\le n)$。一开始 $\text{Alice}$ 知道 $m\times n$,$\text{Bob}$ 知道 $m+n$,两人同时知道一个下界 $s$,即 $s\le m\le n$。
从 $\text{Alice}$ 或 $\text{Bob}$,交替回答现在自己是否已经知道了 $m,n$。要求是两人在说了总共 $t$ 次“不知道”之后,同时知道了 $m,n$。
给出 $s,t$ 和从谁开始,构造一组合法的 $m,n$,使得 $m+n$ 最小的情况下,$m$ 的值最小。
对于 $100\%$ 的数据,满足 $1\le s\le 200,\ 2\le t\le 15$,数据保证有解。