越来越菜了，我该怎么办？？

AGC002

A - Range Product [Safe]

题面

给定 $a,b$，求 $\prod_{i=a}^bi$ 是整数，负数，还是零。

$-10^9\le a\le b\le10^9$

题解

直接判断区间与 $0$ 的大小关系与即可，复杂度 $O(1)$

B - Box and Ball [Safe]

题面

给定 $n$ 个盒子，初始除了第一个盒子只有一个红球之外其余盒子都只有一个白球，有 $m$ 次操作，每次随机从第 $x_i$ 个盒子里抽取一个球，放入第 $y_i$ 个盒子

问最后有多少盒子，存在一种安排随机抽球的方案，使得其含有红球

$2\le n\le10^5,1\le m\le10^5$

题解

模拟哪些盒子可能有红球，如果 $x_i$ 可能有红球，那么在进行了操作 $(x_i,y_i)$ 后 $x_i$ 与 $y_i$ 均可能有红球，注意此时要判掉 $x_i$ 没球的情况

复杂度 $O(n+m)$

C - Knot Puzzle [Safe]

题面

有 $n$ 个点，有点权 $a_i$，一开始 $i$ 和 $i+1$ 相连，形成一条链，现在如果一个连通块的点权和 $\ge k$，你可以删掉其中的一条边

问你能不能把所有边都删掉，如果能则给出构造

$2\le n\le10^5$

题解

不难发现如果不存在 $a_i+a_{i+1}\ge k$ 那么最后一定会剩下至少两个点断不开

否则，设 $a_x+a_{x+1}\ge k$，那我们可以依次删掉 $(1,2),(2,3),\cdots,(x-1,x)$，然后再依次删掉 $(n-1,n),(n-2,n-1),\cdots,(x+1,x+2)$，最后再删 $(x,x+1)$

复杂度 $O(n)$

D - Stamp Rally [Euclid]

题面

给定一张 $n$ 个点 $m$ 条边的无向联通图，边有边权，是一个 $1\sim m$ 的排列

$q$ 次询问，每次询问给出两个点 $x_i,y_i$ 以及一个整数 $z_i$，问有两个人分别从 $x_i$ 和 $y_i$ 出发，他们一共要经过至少 $z_i$ 个不同的点（可以重复经过一个点），问他们经过的边的边权最大值的最小值

$3\le n\le10^5,n-1\le m\le10^5,1\le q\le10^5$

题解

为什么不难的题我还是想了很久？？？

考虑如果只有一个询问，那么我们很会做。直接二分答案，然后用并查集按边权加边计算连通块大小即可

但是我们有 $q$ 个询问，不能分别二分，但是我们发现并查集一次可以处理很多询问，因此我们对这些二分并行处理，每次二分所有询问，把这轮二分 check 中需要的询问记下来用并查集计算，这样每一轮 check 都是 $O(n+q)$

总复杂度 $O((n+q)\log m)$

E - Candy Piles [Keter]

题面

先手和后手在玩游戏，有 $n$ 堆石子，初始第 $i$ 堆有 $a_i$ 个石子，游戏轮流进行，每次每人可以选择以下两种操作的一种：

选择一个石子数最大的堆，将其中所有石子都吃掉
对每个石子数非零的堆，从中吃掉 $1$ 个

吃掉最后一个石子的人数，问谁有必胜策略

$1\le n\le10^5,1\le a_i\le10^9$

题解

深入人心了属于是。

我们将石子堆的个数从大到小排序，排成一个下降的杨表，那么两种操作相当于每次删掉最左边的一行或者最下边的一列

在进一步转化，就相当于有一个点一开始在左下角，每次可以向左走或向右走一步，走出杨表就算作输

手玩一下可以发现 $(x,y)$ 和 $(x+1,y+1)$ 的胜负状态一定相同，证明很简单，直接反证法讨论一下即可

那么我们只用考虑杨表边界线上的点的胜负状态即可，我们分为三类：向外凸的拐点，在直线上的点，向内凹的拐点

向外凸的拐点一定必输，而在直线上的点则从向外凸的拐点开始胜负交题，那么也可以推出向内凹的拐点的胜负状态，因此我们只需要检查 $(0,0)$ 投射到的点的胜负状态即可

复杂度 $O(n\log n)$

F - Leftmost Ball [Keter]

题面

有 $n\times k$ 个球，其中有 $n$ 种颜色 $1\sim n$，每种颜色各 $k$ 个

你需要把它们排成一列，在这之后每一种颜色最左边的球会变成颜色 $0$

求生成的颜色序列总数，模数 $10^9+7$

$1\le n,k\le2000$

题解

讲过的题还不会做！！！！！！！！

我们可以钦定这 $n$ 种颜色第二个球出现顺序，那么我们的答案就是这个图的拓扑序个数 $\times n!$

我们令 $dp_{i,j}$ 表示下图的拓扑序个数：

下一步只有两种选择，选择灰点或有颜色的点，如果选择灰点，那么直接从 $dp_{i-1,j}$ 转移，否则从 $dp_{i,j-1}$，并且我们还要把剩余的彩色点插到后面形成的序列中，用组合数即可

复杂度 $O(n^2)$