1. AGC015F Kenus the Ancient Greek

定义为执行 (辗转相除)所需要的步数。

次询问,给定，求，的最大值，

以及达到了最大值的个数，对取模。

数据范围：。

第一问考虑倒推，每一步让两个数尽量小：

发现答案就是最大的，使得：，。

思考第二问，不妨只统计且满足条件的二元组。

我们设为第一问所求范围内最大次数。

显然，如果，无论第一问为多少，它都无贡献。

我们会发现符合为一定值的组数量很多。

而经过一次辗转相除会使得其中很多变得相同，且。

实际代表了变换前

对于一定值，我们可以打出变换后二元组的表：

发现第行由第行通过变换再多加一组。

多加的正是第行的第个通过变换。

为什么？

对于，如果过大会导致最大值变大从而无贡献。

所以第行首先要求范围。

我们从第行中的二元组回推，每组变换合法。

而的变换中只有时，

用第行第组变换，即：

时合法。

() 。

得到了对于最大值对应的变换后的每个二元组，

我们可以简单的计算出变换前的二元组数量。

于是我们预处理出变换后的二元组，

对于每个询问的计算符合条件的二元组数量。

就可以了。

2. AGC013F Two Faced Cards

给定一个包含个二元组的集合和一个包含个数的数组，存在次相互独立的询问。

每次询问向中加入一个新给的二元组，在每个二元组的两个数中选一个，并将选出的数与中数两两配对，使得每组配对中来自的数小于等于来自的数。

要求出选出数是二元组中第一个数的最大数量，存在无解。

数据范围：。

因为我们要最大化选第一个数的数量，那就先全部选第一个数。

然后我们考虑如何判断能否将选出的数与中数两两配对成功，

我们可以对两组数排序后检查，但更好的是利用 Hall 定理判断。

具体地，先对所有数离散化，然后可以拿个数组，

对从中选出的数做后缀加，对中的数做后缀减，

就只需要保证中的元素新最后都大于等于。

这个方法的优势就在于，我们很好反悔，

我们可以直接对第二个数，第一个数做区间加。

对于每个询问我们枚举选哪个数，条件就变成了。

我们找到满足最大的，

可以证明包含它且左端点最小的区间必选。

ps：证明不想写，看这里比较好。

这样我们从后往前一直选，可以使得。

最后我们从前往后选最少的区间依次满足的条件即可。

我们每次贪心选择包含当前且右端点最大的区间，就可以了。

3. 牛客24157E斐波超级加强版

序列 { } ，满足递推，其中 $，$ 给定。

是一个可重集合，给定，设为。

给定一个数组，存在次操作，每次操作是其中一种：

1.把变为。

2.计算，输出答案模。

数据范围：。

考虑直接求通项，设。

则，化简：

我们后面其实只要求出形如的东西就行了。

考虑每个位置的权值对这个式子上面的指数的贡献，就是。

拿线段树维护区间内这种的即可。

其实需要特判的情况，此时，难以维护。

4. 【UR#18】在路上了

有一个个点的完全图，每条边染红色或蓝色。

已知对所有，连接和的连边为红色。

交互，可以询问次，每次询问和之间边的颜色。

你需要找到一条由个点条边组成的路径，满足所有边的颜色相同。

数据范围：。

yhx 写的极为清楚，我就不想写了。

5. ZROI21省选D2T2 商人

未来天的物品价格可能是枚金币或者枚金币，每天可以买入一个、卖出一个或者什么都不做。

最初你有无限的金币，你想用最优策略从中获利，问 $～$ 时，有多少种价格情况可以使你最多赚到枚金币。

数据范围：；；。

显然的，我们只有在价格为枚金币时买入，价格为枚金币时卖出才能最大获利。

我们将价格序列看成一个长度为的括号序列，我们的就是当前对应括号序列的最长合法子序列的长度。

得到分的做法：设表示当前到第天匹配了对括号前面还剩下对括号的方案数，很好转移。

考虑拿出最长合法子序列后剩下的括号序列，可以发现一定是一段前缀右括号，一段后缀左括号。

这些可以插在最长合法自序列的前面后面或者几段括号之间，可以设表示当前到第天分成了段的方案数。

组合数和卡特兰数转移，卷一下分，拉格朗日反演分。

想想其他的做法，经典的我们可以拿括号序列上折线，设左括号有个，最小前缀和为并且不妨。

起点在，终点在，差分，此时赚取的金币数时，。

所以折线不能经过下方的水平线，则方案数为。

于是我们对于每一个求出，就可以了。

6. AGC011F Train Service Planning

有一条被个站台分为段的铁路，站台标号为，铁路标号为。

列车通过第段所需时间为，铁路可能是双向的或单向的，你需要设计一张列车时刻表。

对于所有的列车，要么从站台前往站台，要么从站台前往站台。

在单向铁路上，不能有两辆相反方向的车互相穿过，列车只能在站点停车等待。

给定一个常数，若有一辆开往的车在时刻到达站点，在时刻离开站点，

则下一辆车恰好在时刻到达站点，在时刻离开站点。

求时间表中列车开一次来回的最短时间，或指出无解，。

存在时无解，否则一定有解。

设为的列车在站台等待的时间，

为的列车在站台等待的时间，

。

则模意义下的列车在第条铁路上的时间为，

的列车在第条铁路上的时间为。

我们发现对于一条单向铁路，我们要求区间不交，

即不在中，在其补集中。

我们就只需要在一个数轴上，随便选个点开始走步，

满足走完步后当前点在中，求最小路径长度。

我们发现单调不降，也就是点都是往正方向走，到就回到。

所以我们可以设表示第次操作后走到的最小路径长度。

，于是我们只要维护的区间即可。

7. AGC058C Planar Tree

圆周上有个顶点。顶点按顺时针顺序编号为到，顶点上写着整数。

接下来通过在顶点间连条边使得顶点连成一棵生成树，需要满足以下两个条件。

如果有边向连，需要满足将边画成线段，不能有两条线段相交。

已知序列，判断是否可以构造满足条件的生成树，有组数据。

数据范围：，都出现过。

当时晚上在酒店会议室想了蛮久还是不会。首先可以找到性质：

相邻且权值相同的两点可以合并。
相邻的可以删去，相邻的可以删去。

第一条比较显然，第二条证明（以为例）如下：

显然这样的相邻两点连边不劣于不连边，接下来证明删掉的可行性。

我们如果不删掉，并用与其他的连边，我们来讨论这些连边割出的弧上的点集。

如果点集中没有，即只有，那可以用性质 1 合并，变成的局面。

由于只有一段符合，所以与其连上边后，就可行性只需要后面的情况可行即可。

如果点集中没有，有，那么原本的可能有解，变成了必定无解，变劣了。

如果点集中有或，那“其他的 ”往点集内的连边可用与相邻的往其内连边代替。

于是我们尽可能地用完这两个性质之后，我们会发现相邻的权值组合只剩下。

考虑三个相邻点，以为前两个权值，后面一个点的权值为或。

先把第二个的点向第一个点连边，删去第二个点，发现正好又可以对第一、三个点使用性质合并。

最后相当于是删去了一个或，同理也可以删去。

可以多多手玩，发现只有 “ “、” “、” “、

“ “、” “和” “这几种无法继续删。

其中可以继续连边到符合条件的只有，判断的条件可以直接简化为。

zyf 和 zhy 有一种把一些权值连续段组合做优先级排序的做法，写了6k，恐怖如斯。

8. ZROI21联赛D15T3 水管工

给定一棵树，需要选择若干点对，覆盖这些点对两点之间的简单路径，满足每条边都被覆盖次。

如果存在组个相同点对，方案的权值就为，你需要求出所有方案的权值之和，对取模。

数据范围：。

思维难难难，首先考虑把一条树边拆成两条边，我们在每个结点处匹配边对。

我们构造一种合法方案，并钦定好每条边所属的简单路径。

显然对于同一条树边的两条边考虑是否交换它们所属的简单路径，我们发现几乎可以得到所有的匹配方案。

但是对于每组相同点对，它们的每种匹配方案两两对应相同，所以每个选择方案对应种匹配方案。

因为选择方案权值为，所以计算权值和就可以转化为匹配方案数除以，考虑dp 。

设表示考虑前条边的匹配方案数，我们先后加入同树边对应的两条边。

，，需要多画图理解。

题解设的让我在理解 dp 上绕了很多弯，也有可能是我没领悟到。

9. ZROI21省选D2T3 防御工事

给定一张个点条边的 $图，对于每个询问，给定$ 个点，你需要在图中选择一个点作为首都。

再选择除首都外的一个点建立防御，此时权值定义给定点不经过建立防御的点且可以到达首都的数量的和。

定义选择此首都的权值为选择每个除首都外的点建立防御时的权值的和，求每个点作为首都的权值的最大值。

数据范围：, ，保证图连通。

水一道题/se，图上的连通性问题建出圆方树，然后又可以在圆方树上建虚圆方树。

可以在虚圆方树上进行换根 dp ，细节很多。

10. ARC061F Card Game for Three 超级加强版

三个人每个人有一堆牌，三堆牌中分别有张牌，每张牌上写了下一个摸牌人的编号。

从第一个人开始摸牌，每次摸牌堆顶部的牌，有人把牌摸完就结束，计算种方案中第一个人摸完的方案数。

数据范围：, 。

水一道@xsi /kel/kel 。

首先考虑对于摸到牌的序列，枚举第一个人摸完的时候，第二个人和第三个人在序列中出现次数来计算答案。

。

设，则。

线性计算系数：。

好题合集