AC. 梦想

frank_c1

CC NOV16

发布于2016年11月17日 | 暂无评论 | 525阅读 | 比赛经历

十天的NOV16终于结束啦。这次比赛真是喜闻乐见呐。

总结一下吧。

ALEXTASK

给定n个整数A_i,求任意两个整数最小公倍数的最小值。T组数据。

1 \le T \le 10, 2 \le n \le 500, 1 \le A_i \le 10 ^ 9

略。

CHSQR

构造一个k \times k的矩阵,满足所有元素1(\frac{k+1}{2},\frac{k+1}{2})的曼哈顿距离的最小值尽量大。k是奇数,T组数据。

1 \le T \le 10, 1 \le k \le 400

容易证明最小值的最大值是\frac{k-1}{2},于是观察样例构造一下即可。

CPERM

求有多少n元排列P,存在位置i,满足对于任意2 \le k \le i,有P_{j-1} \lt P_j,对于任意i \le k \le n - 1,有P_j \lt P_{j+1}。输出方案数对10 ^ 9 + 7取模的值。T组数据。

1 \lt T \le 100, 1 \le n \le 10 ^ 9

注意此处要求严格单峰和特判。答案是2 ^ {n-1} - 2

GIFTCHEF

给定串s和串t。开始时你只拥有串s,每次你可以从你拥有的串中选择一个,从中切下一个串t,原有的串可能也会随之断成多截。求至少切下一个t的切分方案数模10 ^ 9 + 7

两种方案不同,当且仅当切下的t的数量不同或存在下标不同。T组数据。

1 \le T \le 10, 1 \le |t| \le |s| \le 3 \times 10 ^ 5

先KMP预处理匹配的位置。设f_i为前i长度的方案数,f_0 = 0, f_i = f_{i-1}。当i是匹配点时f_i += f_{i-|t|} + 1

时间复杂度O(n)

FRIEMEET

给定n个点的带边权树。有m个特殊点A_1, A_2, ..., A_m

求下列式子的值

\frac{1} {m ^ 2} \sum_{i=1} ^ {m} \sum_{j=1} ^ {m} {\mathrm{dist}(A_i, A_j)}

1 \le T \le 5, 1 \le m \le n \le 50000

树形DP。和经典问题类似的处理方法。

时间复杂度O(n)

URBANDEV

平面上有n条线段。线段与坐标轴平行。

求每条线段与其他线段形成的交点个数。注意如果某交点的度数小于3,则不计算。

1 \le n \le 10 ^ 5,端点值1 \le x \le 10 ^ 5

扫描线经典。用树状数组维护一下即可。注意有一个神奇的交点判断条件,于是我们可以多扫几遍去掉不合法的情况。

时间复杂度O(n \log n)

KIRMEME

给定一棵树。第i个点的权值是a_i

求树中有多少条链,满足a_{j-1} \lt a_ja_j \gt a_{j+1}的下标j的数量在[L,R]中。

1 \le T \le 20, 1 \le n \le 50000, 1 \le L \le R \le 10 ^ 7, 1 \le a_i \le 10 ^ 7

考虑点分治。整个过程是比较经典的。唯一需要考虑的是当前分治点是否是合法的下标,对于这个问题,我们需要分成两种情况讨论。 每一层用两个树状数组维护一下即可。

时间复杂度O(n \log ^ 2 n)

BIKE

n个点m条边的有向图。第i条边从u_iv_i,权值为(a_i, b_i)

设你当前的状态是(p, q),在通过这条边后状态变为((p + a_i) \mod n, (q + b_i) \mod (n-1))

对于任意i,j,k,求从点k出发经过t条边回到点k,末状态是(i,j)的方案数,对1163962801取模。

2 \le n \le 22, 2 \le m \le 10000

这一题乍一看条件非常不知所谓,难以下手。

我们先考虑通过一条边带来的改变,可以发现这是一个二维DFT的过程。

考虑二维DFT的公式

F(u,v) = \sum_{x=0} ^ {N-1} \sum_{y=0} ^ {M-1} {f(x,y) e ^ {-i2\pi (\frac{ux}{N} + \frac{vy} {M})}}

考虑到

e ^ {-i2\pi} \equiv g ^ {p - 1} \pmod {p}

可以改写成

F(u,v) = \sum_{x=0} ^ {N-1} \sum_{y=0} ^ {M-1} {f(x,y) g ^ {\frac{p-1} {NM} (uxM + vyN)}}

W = g ^ {\frac{p-1} {NM}},进一步有

F(u,v) = \sum_{x=0} ^ {N-1} {W ^ {uxM} \sum_{y=0} ^ {M-1} {f(x,y) W ^ {vyN}}}

现在只要能够计算出W,我们就能在O(n ^ 3)的时间完成一次DFT了。

考虑W = g ^ {\frac{p-1} {NM}}。由于在原题中,M = N-1,而模数P = 2 ^ 4 \cdot 3 ^ 2 \cdot 5 ^ 2 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 + 1,我们惊喜地发现,对于任意2 \le N \le 22,都有(N(N-1)) | (P-1)

这样问题中所有奥妙重重的地方就都可以解释了。下面的做法就比较套路。考虑快速幂,每次转移枚举起终点s,t,枚举中间点mid,用(s,mid)(mid,t)的信息去更新(s,t)。在转移开始前,对n ^ 2个矩阵二维DFT展开,复杂度O(n ^ 5)。枚举一组s,t,mid,转移复杂度O(n ^ 2),总复杂度O(n ^ 5)。乘上快速幂的复杂度,问题的总复杂度就是O(n ^ 5 \log t)啦。

SEAPERM3

我们称一个排列P是好的,当且仅当P中存在至少一对(i,j),满足p_j \gt i, p_i \gt j

此外,排列P还需要满足m个条件,第i个条件要求P(X_i) = V_i

1 \le T \le 10, 1 \le n \le 10 ^ 9, 0 \le m \le 10 ^ 4, 1 \le X_i, V_i \le n

X: SEAWCU

给定n \times n \times n的数字立方体,(i,j,k)处的整数是A_{i,j,k}

求一条路径,满足若路径中相邻的原立方体中也相邻,路径中不相邻的原立方体中也不相邻。

最大化路径经过格子的权值总和。评分方式是你的分数除以最高分。

n = 50, 1 \le A_{i,j,k} \le 10 ^ 6

我的做法只有53分,膜拜写了800+行的ceilks……

总体的思路就是勇敢地舍弃一大部分格子,对面行列分为可扩展和不扩展的,可扩展的单元不能相邻。以这个为状态O(n ^ 3)DP,就可以获得一个不是那么劣的解。至于更高明的做法,我就不会啦QAQ 欢迎大家在评论中指出。