比赛链接：https://competition.nowcoder.com/3/introduce

受 qcjj 邀请打了个抢钱比赛，结果只抢了 500，太菜了，哭死

初赛

1 小华拼单词

题意：分别给出字母 a 到 z 的个数，求最多能拼出多少个 'huatai'

题解：字母 a 数量的一半，以及字母 i、u、h、t 的数量，取最小值

2 股票买卖的最大收益

题意：给定股票每天的价格，初始持有 手股票，现金 元。每天可以任意次买入或卖出，但最多持有 手股票。求最后一天结束的时候，最终总资产最多为多少。最终总资产=现金数+持有股票数×最终股票价格。

题解：贪心，如果下一天股票要跌就在当天全部卖出，如果下一天股票要涨就在当天全部买入。

3 运货

题意：给一棵 个节点的树，一共有 条路径，每条路径的愉悦值为路径上的最大结点编号，求所有路径愉悦值的和，对 取模。

题解：从小到大添加结点，用并查集维护连通块大小。当添加了一个点时，令它所连接的连通块个数为 ，各个连通块大小分别为 ，那么以该点作为路径上最大点的路径个数为 ，对序列 求前缀和后该式可以  求出，总复杂度 。

4 区间乘积的因子数之和

题意：给定一个数组，数组中每个数都是不大于 的正整数。已知一个区间的权值为该区间所有数乘积的因子数量，求所有区间的权值之和。

题解：由题意得一个区间所有数的乘积可以表示为 ，它的因子个数为 。令 表示前 个数中 的个数， 表示前 个数中 的个数，那么所有区间的权值之和可以表示为：

对序列 与 以及两者的逐元素乘积求前缀和后，该式可以 求出。

决赛

1 股票最小的陡峭值

题意：给定一个序列 ，其中某些元素值是未知的，保证第一个和最后一个是已知的，求 的最小值。

题解：容易想到未知的值只要落在两侧已知的值之间即可保证结果最小，为方便代码，将未知的值直接替换为前一个元素的值即可。

2 小华的字符串后继

题意：给定一个小写字母字符串，求与该串长度相同且字典序大于该串的字符串中字典序第 小的字符串，若不存在输出 -1。

题解：把字符串看作 26 进制数，把 也转化为 26 进制数，作高精加法即可。

3 小华的排列交换

题意：给定一个排列，每次可以交换一个奇数和偶数的位置，求最少多少次交换能使得排列变得有序。

题解：每个位置看作一个结点，将该结点和该位置上的数的对应结点连一条单向边，可以得到若干环，称作置换环。通过推断可以得到如下结论：

• 如果一个长度为 的置换环上既有奇数又有偶数，那么通过 次交换即可将环上的所有数归位。

• 对于一个长度为 的只有奇数的环，和一个长度为 的只有偶数的环，可以先通过一次交换将两环合并成一个既有奇数又有偶数的环，然后再通过 次交换将所有数归位，总次数为 。

• 对于一个长度为 的只有奇数/偶数的环，且没有偶数/奇数环与之合并，那么必须先通过一次交换将一个偶数/奇数加入该环，然后通过 次交换将所有数归位，总次数为 。

4 区间权值和

题意：定义一个数组的极差为该数组最大值减去最小值的差，定义一个区间的权值为该区间内所有连续子数组的极差之和，求给定数组的所有区间的权值和。

题解：最大值与最小值的贡献分开计算。对于每个数，可以通过单调栈分别找到左右两测比它大/小且距离其最近的位置，借此可以确定该数作为最大/最小值时的最长区间。令一个数的位置为 ，其左边比它大的距离最近的位置为 ，其右边比它大的距离最近的位置为 ，计算得该数作为最大值时的总次数为：

可通过等差数列求和公式或维护前缀和算出，最小值同理，最终将最大值的总贡献减去最小值的总贡献即是所求答案，总复杂度 。

5 排队

平衡树，不让用板子，润。

6 项链

群论，不会，润。

算法竞赛交流群：1043272289