Contest Info

date: 2018.10.17 12:40-15:40

practice link

Solutions

D. Pagodas

签到题。

E. Efficient Tree

题目大意：

\(n\times m\)的完全网格图，边带权，求最小生成树的权值和是多少，定义生成树的\(\tau(T)\)为每个点与它左边和上边格子连边的数量加一的累乘，求所有最小生成树的\(\tau(T)\)和。

\(n\le800,m\le7\).

题解：

轮廓线dp，逐格转移，记录最后\(m\)格的状态，转移时保证不存在环以及不会不连通。

F. Frogs

简单容斥。

H. Chessboard

题目大意：一个 \(n\times m\) 的网格，有 \(r\) 个障碍物。现在给出一个长度为 \(l\)，由 RUDL 组成的序列。对于每个格子，按照这一序列移动，如果遇到障碍或走到边界就忽略这一步。问每个格子走到的终点到起点的欧氏距离的平方和。

题解：考虑对每个格子分别求解。注意到所有格子只要不碰到障碍物，移动的方向都是一样的。

我们记录一个全局的偏移量，那么这样就相当于所有碰到障碍物的格子往指令的反方向移动一格。对于移动到同一格的格子用并查集合并。

时间复杂度 \(\mathcal{O}(nm+(n+m+r)l)\)。

I. Triple

题目大意：

有大小为\(n\le10^5\)的二元组multiset\(A=\{(a_1,b_1),\cdots,(a_n,b_n)\}\).

和大小为\(m\le10^5\)的三元组multiset\(B=\{(c_1,d_1,e_1),\cdots,(c_n,d_n,e_n)\}\).

定义multiset\(C=\{(a,c,d)|(a,b)\in A,(c,d,e)\in B, b=e\}\)

求\(C\)中有多少个三元组\((a,b,c)\)满足不存在\((u,v,w)\in C, (u,v,w)\not = (a,b,c)\)且\(a\le u,b\le v, c\le w\).

题解：

\(A\)中对于每一个\(b\)，只保留\(a\)最大的，这样剩下的就只有\(O(m)\)个三元组，判断每一个是不是即可。

\(a\)这一维排序，\(c\)，\(d\)二维树状数组维护。

时间复杂度\(O((n+m)(\log{n}+\log{c}\log{d}))\).

K. Kykneion asma

题目大意：用 \(0,1,2,3,4\) 组成一个整数，每个数字有最大数量限制，且不能有前导 \(0\)。求方案。

题解：简单 FFT。