2015-2016 Moscow SU Trinity Contest

Problem A

Solved by zerol. 01:19 (+3)

题意：求一个矩阵的秩。

题解：某人因为坐地铁迟到了。但迟到了这么久，队友居然签到都没成功。取模真的是套路啊！为什么要调 EPS 呢……

Problem E

Solved by kblack. 01:30 (+)

题意：有向满二叉树，按传递闭包重新建边，求包含指定两个点的最小极大反链。

题解：如果原本就已经是父子关系，那么就GG，否则只要一路到根，把另外一个方向的路都堵死就好了。

Problem F

Solved by zerol. 04:49 (+1)

题意：给一棵带边权的树，每次询问一条路径上的边权集合的 mex。

题解：树上莫队，由于修改比查询多了 $\sqrt n$ 倍，所以用分块处理插入、删除（$O(1)$）、求mex（$O(\sqrt n)$），总复杂度 $O(q\sqrt n+n\sqrt n)$。

Problem G

Solved by zerol. 03:34 (+1)

题意：构造题。一个简单无向图的边 k 染色使得任意一种颜色的边构成的是该图的生成树，且任两点之间不同颜色的路径不能经过同一个中转点。

题解：根据数据范围，猜测要构造 k*k 个点的完全图。发现对于任意一个点，它只能成为某种颜色的中转点。对于每种颜色，分配 k 个专用中转点，中转点之间互相连接，对于其他 k*(k-1) 个点，按照一定规律（每 k 个点加一个颜色相关的偏移连接到 k 个中转点）连向中转点，并保证没有重边。

Problem H

Solved by ultmaster. 03:48 (+4)

题意：大概是问你把一个方块横竖乱切，最小的块的面积的期望值。

题解：蒙特卡洛大概可以找出一些规律，然后注意用 log 避免精度问题就成了。但是！科学计数法！（听说可以用 %lg，学到了。）

某人算浮点数阶乘写错了下标，杀掉了不止半个小时的机时。

Problem I

Unsolved.

题意：给你一个数列，每次询问一个区间内满足条件的最长子区间的长度。条件是该数列的最左和最右元素相等，其它元素不超过二者。

Problem J

Solved by ultmaster. 02:12 (+)

题意：在一棵树上找一条路径，使得这条路径有一个子序列是给定的字符串。

题解：典型的树形 DP。基本上记录一下最大次大值，然后瞎匹配一下，匹配到了直接抛出来就好了（异常还是最好的嘛！）。一边纠结着代码重用，一边怀疑着算法，过得倒是挺顺利。