题目大意
有 $n$ 个人玩淘汰赛。
每一轮,假设当前还剩 $k$ 人,则他们随机分成 $\lfloor \frac k2 \rfloor$ 组($k$ 为奇数时有一人轮空),最后晋级 $\lceil \frac k2 \rceil$ 人。每个人能力互不相同,两人对打时一定是能力强者获胜。
求所有可能的局面数,答案对 $2^{64}$ 取模。
$1 \leq n \leq 10^{18}$
注意题面坑:Two tournaments are called different if there is a game (between two participants) in one of the tournaments that doesn’t occur in the other tournament. 这句话是错的!
题目大意
有一个 $n\times m$ 的黑白棋盘,初始时候每个格子都是白色。
接下来 $q$ 次操作,每次把第 $a_i$ 行的 $[l_i,r_i]$ 这个区间反色。
每次操作结束就会问你,是否存在 $x_1,y_1,x_2,y_2$,满足
- $1 \leq x_1 < x_2 \leq n$
- $1 \leq y_1 < y_2 \leq m$
- $(x_1,y_1)$ 与 $(x_2,y_2)$ 同色
- $(x_1,y_2)$ 与 $(x_2,y_1)$ 同色
- $(x_1,y_1)$ 与 $(x_2,y_1)$ 异色(即:对于矩形的四个角,对角同色,同侧异色)
若存在,则输出其中一组解。
$n,m \leq 2000,~q \leq 5\times 10^5$
不知不觉大一就过完了。这一年混杂着学习、acm,好多感想。
想想还是觉得要简单写写吧。
题目大意
你有一个数列 $a_1,a_2,\cdots,a_n$。你可以进行这样的一次操作,每次选择数列中其中一个数然后将其除 $2$ 下取整,也就是选择一个数 $a_i$,变成 $\lfloor \frac{a_i}{2} \rfloor$。
一共有 $q$ 个询问,每次你考虑数列中 $[l,r]$ 这段数,即 $a_l,a_{l+1},a_{l+2},\cdots,a_r$,对这些数字进行不超过 $k$ 次操作,这些数字的总和最小值可能是多少。
$1 \leq n \leq 10^5,\ 1 \leq q \leq 5*10^5$
$1 \leq a_i \leq 10^9,\ 0 \leq k \leq 10^9$
5000 ms,256 MB