感谢 Frank_DD， stff577， Fangs， Sariel_snow， HoshimiOWO， LoserOfSWUST， gxucm， thusloop， maomeng， caterto， aiyoupass， llzzxx712， Agateth， Secqin， 996007， GameTheory， handsomePeach， AcidMango 参与验题。

也感谢各位前来捧场！

如果您需要数据，可以访问我校的校内 OJ，注册即可下载数据。

A 别恶心啊

这题是签到，模拟一下就好了。需要判断若干个字符串 $t$ 是否出现在字符串 $s$ 中，逐一的枚举 $s$ 中的各个位置，逐字符判断是否出现了字符串 $t$ 即可，复杂度 $O(∣s∣∗∣t∣)O(\lvert s \rvert*\lvert t \rvert)$ 。用 C++ 的 STL 可以实现的更轻松。

这里是代码

B 瓜瓜的字符串(easy)

考虑比赛整体难度，放过了 $O(n^2)$ 的暴力做法。

考虑第一次操作，注意到序列 ${a_i\}$ 互不相同，不难发现把序列中最大值翻到前面最优。此段翻转后就不能再翻转，继续去翻后面序列的最大值即可，直到翻至序列结束。

寻找序列最大值，可以每次暴力的扫描序列，复杂度 $O(n^2)$ 。也可以排序，复杂度 $\log n)$ ；注意到值域不大，也可以使用桶排，复杂度 $O (n)$ 。

这里是代码

C 瓜瓜的字符串(hard)

与本题的 easy 版本类似的，我们每次应当保证每次翻转后字符串的字典序尽可能大。贪心的考虑，每一次翻转不具有后效性，因为此段翻转后就不能再翻转。

问题转化为如何找到翻转后字典序最大的前缀。由于 easy 版本序列中的各个数互不相同，因此翻转后字典序最大前缀的位置一定是最大值的位置。而在本题中，我们可以把原串翻转后，求出字符串的后缀数组，根据后缀排名来找到这个位置进行翻转。

这里是代码

本题具有一定的特殊性，翻转暴力在做一定优化下的复杂度是对的。也可能不对，我和验题人斗智斗勇了好几天，最终我败下阵来，承认我卡不掉（

这里是代码

D 瓜瓜爱数数

注意到若 $\oplus b = w$ ，则有 $\oplus a$ ，即确定第一位后，相邻位置的数码就确定了。故整个序列只可能有 $ababab...\texttt{ababab...}$ 这样的形式。

可以使用 $10 \times 10 \times \lg 10^{17}$ 的枚举暴力计算所有可能。也可以注意到答案不会有很多，预处理所有的数字，每次询问二分查找即可。当然，如果愿意写数位 DP 也行。

这里是代码（数位DP）

这里是代码（爆搜）

E 瓜瓜的中国剩余定理

注意到若 $x=mia_i \bmod x = m_i$ ，则说明 $a_i - m_i$ 是 $x$ 的倍数，即 $x$ 是所有 $a_i - m_i$ 的公共因子。

这说明 $x$ 是所有差的最大公因数的因子，可以使用 $gcd⁡\gcd$ 计算最大公因数，然后 $O(n)O(\sqrt{n})$ 的枚举其因数即可。

另外请注意， $x=mia_i \bmod x = m_i$ 蕴含着 $x > m_i$ ，样例中的 $1$ 只是个特例。

这里是代码

F 瓜瓜的跳棋

考虑倍增。维护每个点跳 $2^i$ 次后的目标值、沿途经过坐标的最小最大值，这样即可 $O(log⁡n)O(\log n)$ 的回答跳 $k$ 次是否合法。

二分最大的合法跳跃次数即可。如果超过 $n$ ，则说明可以永远跳跃。复杂度 $\log n + m \log^2 n)$ ，或者在二分时判断合法，复杂度 $\log n + m \log n)$ 。

这里是代码

G 瓜瓜的弹簧

节点 $x$ 与其父节点的距离是 $1 + w_x$ cm，其中 $w_x$ 是节点 $x$ 所在子树的质量之和。这个描述很清晰的告诉我们应该树形 DP 得到子树的质量，以及到根的距离。

接下来考虑分析挂一个节点对树的影响。不难发现节点 $x$ 到根的所有弹簧的距离都增长了 $u$ cm，因此对 $y$ 的影响就只有公共祖先，故增加的距离是

dep⁡(LCA⁡(x,y))×u\operatorname{dep}(\operatorname{LCA}(x, y)) \times u

所以是 DP 之后对询问求 LCA 即可。

这里是代码

H 祖玛

注意到一个事情，当这个序列是完美序列时，序列两头的颜色是相同的，故所有的完美序列都是这样一层一层的套上去的层次结构。

因此对于 $f_n$ ，我们只需在长度小于 $n$ 的序列外套一层其他颜色。假设从长度为 $f_i$ 外套一层长 $n - i$ 的其他颜色，有 $n - i - 1$ 种套法，并且其他颜色有 $k - 1$ 种选法。这可以自然的导出转移方程（觉得难以理解的，可以在 DP 中增加一维层数）

fn=∑i=1n−3(n−i−1)(k−1)fif_n = \sum_{i=1}^{n-3} (n-i-1) (k-1)f_i

直接做的复杂度是 $O(n ^ 2)$ ，可以用前缀和优化转移的过程，复杂度为 $O (n)$ 。当然也可以使用快速幂、整式递推等科技优化到 $O(log⁡n)O(\log n)$ ，可以自行尝试。

这里是代码（写法一）

这里是代码（写法二）

I FF 的婚介所

首先这是个二分图匹配问题，但是结点的个数太多无法建图。不难发现，其中很多人是等效的，如“12”、“21”、“1121”都可以视作同类的人。从数位的角度看，最多只有 $2 ^{10}$ 种人。因此可以先用数位 DP 预处理出每种人有多少个，然后建图跑最大流匹配即可。

这里是代码

J FF 的 V 形函数

我们可以将直线 $y=10^5$ 和 V 形函数（下面称作三角形），逆时针旋转 $45 °$ ，这样每进行一次操作，就相当于插入两条平行于 $x$ 轴和 $y$ 轴的直线，交点为三角形的顶点。

我们需要维护的就是下方轮廓线，初始情况下是一条斜线。

从图中可以看出，每当我们插入一个三角形，轮廓线就有一部分需要区间推平。我们需要二分得到其推平左边界，然后对三角形进行区间推平。

线段树比较模板，就是写起来比较痛苦。

还有通过 set 维护轮廓的想法，但至今没人愿意写这个 std，感兴趣的可以尝试。

这里是代码

K 农场主瓜瓜

首先是如何选边，显然 $O(2^n)$ 的枚举是不行的。很容易猜想从小到大依次选择，但是最后一个样例否定了这样的想法。

正确想法只需稍微更正。注意到一个贪心，对于给定的多边形，增加一根不长于最长边的边面积一定变大。因此当选定好最大边时，一定可以选择所有比它小的边，故可以 $O (n)$ 枚举。

接下来只需求已知所有边下的外接圆，这是个经典的计算几何问题，二分圆心角即可。注意需要根据圆心是否在多边形内分类。也需要注意外接圆的半径上限，二分范围不要错了。

这里是代码

另外，这题为了避免精度问题，已经限制了边长为整数，但是 acos 写法的误差较大，需要 long double 。不理解的，可以试试

int main() {
	double a = 3.14159265358979323846;
    double b = a * 1E-12;
    double c = a - a * (1 - 1E-12);
    printf("b = %.30lf\nc = %.30lf\n", b, c);
}

L 植物系魔法师 FF

（解法一）考虑对序列求和，当两个序列可区分时，前缀和不同，求前缀和不同的第一个位置即可。求前缀和需要类欧算法。复杂度 $O(n2n)O(n\log^2 n)$ 。

（解法二 By HoshimiOWO）类似于二分前缀和，似乎有只需要一次万欧的方法。出题人表示我也没看懂，吊打标程了。复杂度 $\log n)$ 。

这里是代码（解法一）

这里是代码（解法二）

M 炼金术士 FF

考虑组合类 $F_q$ ，表示质量为 $i$ 的 $q$ 阶元素有 $x^i] F_q(x)$ ，则 $q + 1$ 阶元素的组合类为

Fq+1=SEQ⁡i⩾1Fq=∑i=1∞Fqk=Fq1−FqF_{q+1} = \operatorname{SEQ}_{i \geqslant 1} F_q = \sum_{i=1}^\infty F_q^k = \frac{F_q}{1 - F_q}

故 $k$ 次复合即是答案

Fk(x)=F0(x)1−kF0(x)F_{k}(x) = \frac{F_0(x)}{1 - k F_0(x)}

组合类建议去这里学。

DP 解释先咕了，出题人补作业去了（

这里是代码

题解 | #浙江农林大学第二十三届程序设计竞赛#

A 别恶心啊

B 瓜瓜的字符串(easy)

C 瓜瓜的字符串(hard)

D 瓜瓜爱数数

E 瓜瓜的中国剩余定理

F 瓜瓜的跳棋

G 瓜瓜的弹簧

H 祖玛

I FF 的婚介所

J FF 的 V 形函数

K 农场主瓜瓜

L 植物系魔法师 FF

M 炼金术士 FF