分类 题解 下的文章

CF1406E Deleting Numbers

交互题。
给定 $n$,则一开始有集合 $S=\{x|x\le n,x\in \mathbb{N}^+\}$,其中有一个特殊值 $x$,你需要通过以下操作找到他。
$\texttt{A}\ a$:询问集合 $S$ 中 $a$ 的倍数个数 $(1\le a \le n)$。
$\texttt{B}\ a$:先询问集合 $S$ 中 $a$ 的倍数个数,然后删去所有还在 $S$ 中的 $a$ 的倍数,而 $x$ 不会被删去 $(2\le a \le n)$。
$\texttt{C}\ a$:回答 $x=a$。
$\texttt{A,B,C}$ 操作的个数和不能超过 $10000$。
$1 \le x \le n\le 10^5$。







- 阅读剩余部分 -

CF961G Partitions

给出 $n$ 个物品,每个物品有一个权值 $w_i$。
定义一个集合 $S$ 的权值为 $W(S)=|S|\sum_{x\in S} w_x$,对于一个集合的划分,定义其权值为 $W'(R)=\sum_{S\in R} W(S)$。
求所有将 $n$ 个物品分为 $k$ 个集合的方案的权值和。
$n,k \le 2\times 10^5,w_i \le 10^9$




- 阅读剩余部分 -