Codeforces Round #506 Div.3 解题报告

题目链接:Codeforces Round #506 Div.3

A. Many Equal Substrings

寻找最长公共前后缀。

B. Creating the Contest

要寻找的目标序列一定是一个连续的子序列,从前往后枚举右端点,发现不满足条件就更新左端点。

C. Maximal Intersection

前缀和思想,维护前缀交集和后缀交集,那么除去当前位所得到的交集就是该位置前缀交集和后缀交集的交集。

D. Concatenated Multiples

设合成的数字为$x$,$x=a_i \cdot 10^{len_j} + a_j$,如果需要$x\mod k = 0$,则需要$(a_i \cdot 10^{len_j}) \mod k + a_j \mod k = 0 $。我们已经知道$a_j$的长度不超过10位,所以我们可以按照长度对数字分成10类。用10个数组存每个数字对k取模的结果。接着我们枚举$a_i$,对于每个$a_i$,枚举与之匹配的$a_j$的长度,从而我们就可以求出 $a_j\mod k$ 的值是$(k-a_i \cdot 10^{len_j}) \mod k$。我们需要知道这个值在长度位$len_j$的数字里出现了几次,对于每一个分类里的数字二分查找即可。

E. Tree with Small Distances

图论构造题。

一开始连了所有的奇数层除去第三层,疯狂WA。后来看题解是这样构造的:把距离大于2的点放到一个集合里面,每次找最深的点,然后连这个点的父节点,连完之后删掉这个父节点和它的所有儿子,直到集合为空。我也不知道为啥,玄学。

F. Multicolored Markers

面积固定周长最大,所以一定是边长的差尽可能小,于是我从$\sqrt{a+b}$开始向下枚举,然后看看能不能有整数的边。当然这是不够的,还需要判断是否 $a$ 和 $b$ 又一个是矩形,这需要预处理出 $a,b$ 所有的因数对组合,代表它们围成矩形的所有可能情况,再在上述步骤中取到整数边之后判断是否有一个因数对可以被包含在当前枚举到的矩形中。

 

说点什么

avatar
50
  Subscribe  
提醒