2015-2016 Moscow SU Trinity Contest

From EOJ Wiki
Jump to navigation Jump to search

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。基本上记录一下最大次大值,然后瞎匹配一下,匹配到了直接抛出来就好了(异常还是最好的嘛!)。一边纠结着代码重用,一边怀疑着算法,过得倒是挺顺利。