最近感觉所有要做的题都是在 CF 上的。
然而今天 CF 挂了。
随便点开最近的 AGC。一看，怎么是造计算机题啊。

题意简述

AGC 047E

给一个大小为 $N=2\times 10^5$ 的内存池 $a_i$，有两种操作：

• + i j k，$a_k\gets a_i + a_j$。
• < i j k，$a_k\gets [a_i < a_j]$。

注意操作时不需要满足i, j, k互不相同。

输出一个操作序列使得按序列操作后 $a_2 = a_0\times a_1$。除了 $a_0, a_1$ 外其他元素初始均为 $0$。
记你的操作序列长度为 $Q$，则应保证 $Q\le 2\times 10^5$。
保证非负整数 $a_0,a_1\le 10^9$，所有元素在使用时应保证不大于 $10^{19}$。

假期尽量冲完 aoi tori 一条线。

——20200930日记
事与愿违，这人咕了。所以只看完了共通线。

题意简述

GYM101741H

交互题。有一棵 $n$ 个点的无根树，你至多询问 $2550$ 次点集 $X$，交互器会告诉你 $X$ 的虚树大小。求这棵树。
$n\le 100$，虚树是也是无根的，没有二度点。

题意简述

GYM102391B

这有个游戏。
有一个 $n\times m$ 的网格图，每个格子可能是空地（.）或障碍物（#）。
还有一个放在空地里的 $2\times 2$ 的箱子（B），一个 $2\times 2$ 的目的地（S），和一个 $1\times 1$ 的玩家（P）。
每一步玩家可以上下左右移动，但是不能走到障碍上、箱子上或走出网格图。
如果玩家移动的方向上下一格是箱子，那么箱子会沿着相同的方向被推动。箱子不能被拉动。箱子不能被推到障碍上或出网格图。
当箱子到达目的地时就赢了。
现在请你构造一个 $n + m\le 100$ 的满足条件的网格图，使得有解且最小操作次数不小于 $40000$。

题意简述

CF1396E

一棵树大小为 $n$（偶数）。将点两两配对，一对的权值为两点在树上的距离。求方案时使所有对的权值和为 $K$。
$n\le 10^5$，需判断无解。

题意简述

CF1407E

$n$ 个点 $m$ 条边的有向图，边有黑白两种颜色。现在要给点染色，每个点染成黑或白，白点只能走它连出的白色边，黑点只能走它连出的黑色边，求一种染色方案使得 $1\to n$ 的最短路径最长，输出方案。

($1 \le n, m \le 500000$)

题意简述

CF1396D

有 $n$ 个豆子，第 $i$ 个坐标为 $(x_i + \varepsilon, y_i + \varepsilon)$，颜色 $c_i$（$\varepsilon = 0.5$）。总的坐标范围 $[0, lim]$，求有多少个格点矩形能够包含所有不同颜色的豆子。$n\le 2000$。

题意简述

CF1406E

交互题。给定 $n$, 猜数 $x$ ($1\le x\le n$)。

交互库将维护一个集合 $S$，初始为不大于 $n$ 的所有正整数。交互库提供三个函数：

$A(a)$，返回求出 $S$ 中 $a$ 的倍数的个数 $(1\le a\le n)$。
$B(a)$，返回 $A(a)$，并将所有 $a$ 的倍数从 $S$ 中删去（$x$ 不删，$a > 1$）。
$C(a)$，报告猜得的数 $x = a$。

三个函数总共可以调用不超过 $10^4$ 次。

题意简述

CF1404D

交互题。给定一个正整数 $n$，两人玩游戏。游戏分两步：

1. 先手把 $1$ 到 $2n$ 拆成 $n$ 对。
2. 后手在每对中，选择恰好一个数。

如果选出的数之和为 $2n$ 的倍数，则后手胜，否则先手胜。

自己选择扮演先手还是后手，并给出必胜策略。$n\le 5\times 10^5$。

题意简述

GYM102059K

$n$ 个物品排列成一排。
从选择某个物品开始，每一步可以选择左/右最近的未被选择的物品，直到所有物品均被选择。
若第 $i$ 个物品恰好在第 $C_i$ 步被选择，则会贡献 $D_i$ 的价值。
对每个 $1\le i\le n$，求出第一步选择 $i$ 能得到的最大价值。
$n\le 300000$。