题意简述

ARC 070D

交互题。
$A$ 个诚实的人和 $B$ 个不诚实的人互相知道各自是否诚实。这些人编号 $[0, A+B)$，你希望判断每个编号的人是否诚实。
你可进行不超过 $2n$ 次提问，每次提问可给出两数 $(a,b)$，表示询问 $a$ 号人 $b$ 号人是否诚实。若 $a$ 诚实则他会如实回答，否则他有可能说假话。
有无法判断的情况。$1\le A,B\le 2000$。

题意简述

AGC 041F

给定一个 $n\times n$ 的被破坏的棋盘，其中第 $i$ 列只剩了最底下的 $h_i$ 个。

求有多少种在棋盘中放置「車」的数量使得棋盘被「車」控制，即其他位置均在「車」的攻击范围内。$n\le 400$。

题意简述

AGC 045E

有 $n$ 个箱子 $m$ 个球，第 $i$ 个球开始在箱子 $a_i$，你希望把它移到箱子 $b_i$。
但是移动有限制：想要把某个球移动到某个箱子中，该球原先所在的箱子中至少要有两个球；并且，每个球都是易碎的，所以第 $i$ 个球不能移动超过 $c_i$ 次。

请问是否能达成目标，并求出至少要移动多少次球。保证目标状态中任意箱子中都至少有一个球。$1\le n, m, c_i\le 10^5$。

题意简述

AGC 044E

给出一个长为 $n$ 的环，每个点有 $a_i, b_i$。随机一个点 $i$ 开始，每次你可以选择停止，则获得当前位置的价值 $a_i$；或者耗费 $b_i$ 的价值，等概率随机移动到左右两点中的一个。

求期望获得的最大价值。$2\le n\le 200000, 0\le a_i\le 10^{12}, 0\le b_i\le 100$。

粉兔题解，好！

题意简述

AGC 038E

有 $n$ 个物品，第 $i$ 个物品给定 $a_i$ 和 $b_i$。

每一个单位时间你会获得一个物品，设 $\sum_{i=1}^n a_i = \sum a, \sum_{i=1}^n b_i = \sum b$，则第 $i$ 个物品有 $\dfrac{a_i}{\sum a}$ 的概率获得。

计算第一次对于每个 $i$ 都有第 $i$ 个物品获得至少 $b_i$ 个的期望时间。

$n, \sum a, \sum b\le 400$。

题意简述

AGC 006F

给定平面上的 $m$ 个整点 $(x, y), x, y\in[1, n]$，将这 $n$ 个点染黑。然后任取两个黑色的点 $(a, b), (b, c)$ 并将点 $(c, a)$ 染黑，直至无法再染黑任何点为止。

求最后平面上有多少点被染黑。$n, m\le 5\times 10^5$。

题意简述

AGC 043C

给三个点数均为 $n$ 的无向图 $G_0, G_1, G_2$，构造一张新无向图 $W$，点数为 $n^3$，每个点的形式为 $(x_0, x_1, x_2)$。
对于原来 $G_0$ 中的一条边 $u, v$，连接所有 $(u, x_1, x_2), (v, x_1, x_2)$。$G_1, G_2$ 中的边同理。
点 $(x_0, x_1, x_2)$ 的点权为 $V^{x_0 + x_1 + x_2}$，其中 $V = 10^{18}$。
求 $W$ 的最大权独立集的权值。$n, m_0, m_1, m_2\le 10^5$。

题意简述

AGC 046D

给定一个01串 $S$，每次操作把最前面的两个字符删除，并将其中一个插入回串中。求能获得的串的个数，取模。

$|S|\le 300$。

题意简述

CF 650E

给两棵树 $T_0, T_1$，每次删去 $T_0$ 的一条边后加入一条新边，要求加入后仍为树。求最少次数使得将 $T_0$ 修改为 $T_1$ 并构造方案。$n\le 500000$。

题意简述

CF 641F

对于 $n$ 个布尔元素 $a(x), x\in [0, n)$，给定两个 2-SAT 问题，问是否解集相同，否则构造一组解使得其仅为其中之一的解。

两个 2-SAT 均形如 $\land_{i = 0}^{m - 1}(f(x_{i, 0})\lor f(x_{i, 1}))$。

其中 $x_{i, j}\in[0, 2n)$，并有恒等式 $a(x) = \lnot f(2x) = f(2x + 1)$。

$n, m\le 1000$。