2019ICPC-Nanjing

来自PC Wiki
跳到导航 跳到搜索

Records

Solution

A

猜结论

B

最短距离不变等价于任意时刻同一行或者同一列中的两个黑点之间不会有白点

那么爆搜用这个剪枝

打表发现是组合数,配个系数就是$$4\binom{n+m-2}{n-1}$$

C

注意到图中不会有环,所以构建出来DAG然后dp一下

D

E

通过打表/OEIS发现$$\frac {f_d} 6$$是积性函数

且当p为质数且$$p=4k+1$$时,$$f(p^e)=p^e$$;

当p为质数且$$p=4k+3$$时,$$f(p^e)=p^e+\frac{2(p^e-1)}{p-1}$$

注意到区间长度$$n=R-L+1\le 10^6$$,因此通过预处理$$\sqrt R$$以内的素数,之后通过区间筛的方式求出$$f_x(L\le x \le R)$$,然后就可以$$O(n)$$求上面那个式子了

总复杂度$$O(Tn\log n)$$

F

考虑用Trie存一下每个串,然后$$LCP=k$$相当于在Trie上走$$k$$步

然后这个对应dfs序连续的一段区间

把dfs序当做一维,下标当做另一维

二维数点

交换操作对应删两个点,加两个点

矩形查询拆成四个点进行

cdq分治解决

G

H

$$a\leq b+c$$无解,否则$$2*(b+c)+1$$ 特判$$1 0 0$$

I

首先把$$0$$拿出来,再最后做一个插入的计数即可.

我们考虑,当你的能量$$\geq 50$$时,后面的步骤是任意的,所以只需要乘上一个排列即可.

现在的问题在于如何统计出能量$$< 50$$的方案数,考虑$$50$$的划分数并不太大,关于划分数做一个动态规划即可.

J

KM裸题 $$O(n^3)$$的板子才能过

K

几何,讨论一下给定点在不在边上和在不在顶点上,然后把左右边界向量拿出来二分

也可以利用三角形面积比例推公式