2018 Multi-University, HDU Day 1

Problem A

Solved by ultmaster. 00:41 (+2)

题意：求 $a$, $b$, $c$ 满足都是 $n$ 的因数也和为 $n$。

题解：各种筛各种暴力发现都布星。过了好久才开始考虑数学性质，好像只能分成 1/3 * 3 或者 1/2 + 1/4 + 1/4 其它都布星。

Problem B

Solved by ultmaster. 04:33 (+3)

题意：给若干个字符串，求一个排列使得最长可匹配括号子序列最长。

题解：先把每个字符串贪心匹配下，形成若干个形如 )))((( 的字符串，并分别记为二元组 $(a,b)$。接下来类似七月月赛大鱼吃小鱼。对 $b-a$ 正负性不同的分别排。对于 $b$ 比 $a$ 大的，按 $a$ 从小到大排；对于 $b$ 比 $a$ 小的，按 $b$ 从大到小排。不能证明。

ultmaster: 很早就开了这道题，在如何排序上产生了争执，卡了好久。尝试了好几种不同的排序，都不能顺利地通过对拍。最后 zerol 指出这个 $a$ 和 $b$ 其实就是需求和获利情况。在括号的泥沼中陷了太久的 ultmaster 终于领悟到此题方法可能与月赛题神似，终于通过了对拍。其实如果叫 kblack 来做的话，可能几小时前就过了。（可惜 kblack 在写 F。。。）

Problem C

Solved by zerol. 00:19 (+)

题意：给 3n 个点（无三点共线），以这些点为顶点构造 n 个三角形使得两两不相交。

题解：按 xy 排序，三个一组即可。温暖的签到。

Problem D

Solved by kblack. 00:56 (+1)

题意：要求构造一个长度为 $n$ 且字典序最小的序列，使得若干指定区间内无重数。

题解：从左往右贪心，当前要求的无重数区间左右边界都是单增的，适时增删，用树状数组维护 mex 即可。

Problem E

Upsolved by kblack.

题意：给出一个由特定方法生成的图，求最大权匹配的值和数量。生成方式为：初始两个点一条边，每次选一条边，复制并插入点。

题解：反过来操作即可，定义价值是 (最大权, 方案数) 枚举左右点是否占用得到一个 value[2][2]，每次选一个度数为 $2$ 的点，替换成一条虚边，并根据两条边的情况计算虚边的价值，并插入。每次插入（包括读入时）如果发现是重边，则直接将其与上一条边合并，操作 n-2 次，唯一剩下的那一条边就包含了所有答案了，想清楚了还是挺好写的。

Problem F

Upsolved by kblack. 04:50 (-1)

题意：给出一个生成数列，循环节大小为 $n$，每循环一次循环节内数字 $+n$，求指定区间内所有子区间的价值，价值为区间内每种数字乘他的出现次数的平方。

题解：平方可以分摊到，同一个数字在区间（可重且有序的）两个出现位置，即是计算每一对数（膜 $n$ 同余）或某一个数字自己对答案造成的贡献，分开计算。两类情况分别枚举一个数字或一对数字可以得到一个很恶心的求和式，扔给 WolframAlpha 化简后，调好参数即可。

Problem G

Solved by zerol. 03:25 (+1)

题解：给递推式，求 Sn。

题解：观察得单增数列 An 中从第二项开始，1,2,3,..., 的出现次数分别为 1,2,1,3,1,2,1,4，记为数列 c，那么有 $2^k < n <= 2^{k+1},c_n=c_{n-2^k}+[n == 2^{k+1}]$。然后随便搞搞，但是这道题参与运算的有好些 long long，模的时候要特别注意。

zerol：事实上这道题 AC 并没有用到 OEIS。如果思路清晰就是 10min 能 AC 的题。

Problem H

Upsolved by ultmaster.

题意：给出一个数列 $a$，求 RMQ 形态与 $a$ 相同的、所有数都是在 $[0,1]$ 区间内均匀分布的数列 $b$ 的和的期望。

题解：虽然 $a$ 有重复出现的数，但题设给出的 RMQ 是下标，所以等于没有。$b$ 数组是实数，所以重复出现也等于没有。$b$ 的笛卡尔树形态与 $a$ 相同，将笛卡尔树建出来以后，可以考虑符合条件的 $b$ 数组元素的全序数量，就是树的拓补序数量：$n! / \Prod size$。由于所有的期望是 $n/2$，每 $\Pi size$ 个中又恰好有一个可以，所以答案就是 $n / 2 \Pi size$。

想清楚的话可能是全场最好写的题？

补：$\Pi size$ 是所有子树大小的积。可以这么考虑：先选所有的排列 $n!$，然后固定第一个 除以 $size_{root}$，之后对于每一棵子树，固定子树的根的代价都是 $size_i$。当然这种证明基于已知答案的前提。如果不知道答案的话，可能会考虑正着做，可能更加麻烦。

Problem K

Solved by kblack. 00:28 (+4)

计算时区，冷冰冰的签到。

kblack: 毒瘤横流的多校,题目冷漠无情,连这签到都是冷冰冰的