2019 Multi-University Training Contest 2
A. Another Chess Problem
B. Beauty Of Unimodal Sequence
题意 给一个序列，求下标字典序最小和字典序最大的，先增后减的序列。
解体过程
- 比赛时首先不知道字典序最小LIS怎么求。
- 试图枚举分界点。【解体的开始】
- 公无渡河，公竟渡河？
- 活鱼在摸鱼，rdc在划水，sdcgvhgj在水深火热。
做法
- 考虑字典序最小的LIS怎么求?
- 这是个经典问题，预处理前缀LIS后缀LIS，check每个元素能都出现在整个序列LIS中，对能出现的元素，记录出现在LIS中的下标。
- 下标为 1 最小元素，下标为 2 的最小元素..... etc
- \(pre[i][0/1], suf[i][0/1]\) 分别维护前缀后缀信息，数组第二维记录表示升or降。
- 逐位考虑填什么。
C. Coefficient
多项式套多项式。好难不会。
D. Double Tree
边分治。好难，不会。
E. Everything Is Generated In Equal Probability
solved by rdc 62min
题意 在 \(1\) 到 \(N\) 随机一个 \(n\)，再随机一个 \(1\) 到 \(n\) 的排列，每次先计算逆序对加入得分，再随机选一个子序列，求得分期望。
做法 考虑一个 pair 对答案的贡献即可。
F. Fantastic Magic Cube
solved by rdc 242min, assisted by F0_0H
题意 一个空间立方体的权值为区域内所有整点 \(x,y,z\) 异或值之和，现需要把 \(n*n*n\) 的立方体，切割成 \(n*n*n\) 个 1*1*1，可以横向或者纵向切割，花费为两部分权值之积，最大化得分。
识破 观察一维的 case，发现得分与切割无关。
做法 每两个点对答案的贡献为常量，与切割方式无关。只需计算 x^y^z=a 的方案数，FWT 即可。
复盘 很早就看了这个题，想法有：按位统计贡献，决策最优点有什么性质，乘法有特殊含义。 最后一条接近真相了，但当时看这题通过人数较少就没有继续考虑下去了。
G. Game
H. Harmonious Army
warning 交题之前仔细检查数据清空。
I. I Love Palindrome String
J. Just Skip The Problem
签到 by rdc 27min
K. Keen On Everything But Triangle
solved by F0_0H 38min
识破 Fib
L. Longest Subarray
solved by rdc 156min
题意 查询极长的子区间，内部出现过的每种元素出现次数超过 k。
做法
- 从小到大枚举右端点，考虑哪些左端点的会被 ban 掉。
- 我们可以发现 ban 掉的左端点是一些区间并，线段树维护。
总结
- X1 阶段(0h-1h)：开场 E、H、I、J、K 靠着技能储备以及战斗经验很稳当地提出了做法，比赛节奏十分紧凑。
- X2 阶段(1h-2.5h)：通过 EIJK 之后，LH 轮流上机，L 题想法犹豫了，H 的实现也遇到了一些问题。这段时间本应做好中期攻坚工作，承上启下，但今天的表现完完全全是在集体划水，LH 拖沓，B 题未能提出合理的做法来。
- Y 阶段：开始集火 B 题，可惜显得有些盲目，rdc 在比赛临近结束时提出了比较真的做法，但时间所剩无几，最终无功而返。