[人工智能]21人工智能AB组大讨论

ZR模拟赛

Day 1

http://zhengruioi.com/contest/940

A

显然可以斜率优化，不过太蠢了
注意到一个很重要的性质，以每个点为圆心，以到别的点的最短距离的$\frac{1}{2}$为半径画圆，可以发现这若干个圆是不相交的，用反证法易证
所以以最短距离为半径画圆的面积和最多为$2nm$
暴力一圈圈往外判断即可（记一下每一行的区间容易实现）

code

B

显然一开始染的颜色可以归到一个联通块上
可以发现，按照题目的那种方式变换，联通块的周长是不会变的，所以可以逆推，最开始的联通块的周长
规定一个方向
然后对于每个小正方形，如果左边，左上，正上都有格子的话这个格子就没有必要染色了
代码实现也非常简单
code

C

首先套一手拉格朗日乘子法，得到每一处的导数是相等的
然后暴力冲一发结果爆精度了。。
不太会，先咕咕咕着

Day 2

http://zhengruioi.com/contest/942

A

发现左上和右下可以分开考虑，最后再乘起来
枚举每一个格子，然后从左往右维护一个列的扫描线，对于障碍暴力清空，对于障碍一下的全部+1，那个线段树xjb搞即可
code
然而考场降智维护了平方和，写到一半发现不对把那部分全删了。。

B

BC都是多项式，我需要先研究一下。。

C

同上

Day 3

http://zhengruioi.com/contest/943
出题人不给大样例，痛失AK /dk

A

OSU人感觉很亲切，然而早已退坑
首先发现和Day 1 T 3一样可以套拉格朗日乘子法的套路
先把每一块的导数写出来，是钦定全部相等
对于第$i$项
$$f^{\prime }[i]=((d^{i?1}x{)}^2{)}^{\prime }=2d^{2i?2}x$$
于是乎可以得到每一块$x$的比值为$d^2$
可以得到
$$\begin{gathered} x+d^{2}x+d^{4}x+...d^{2n?2}x=W \\ W=x(\frac{d^2?1}{d^{2n}?1}) \end{gathered}$$
$$x=W\frac{d^{2n}?1}{d^2?1}$$
然后在把这个带入
$$\begin{gathered} x^2+d^2{x}^2+d^4{x}^2+...d^{2n?2}{x}^2 \\ =W^2\frac{d^2?1}{d^{2n}?1} \end{gathered}$$
直接计算即可
code

B

支配树板子题
考虑对起点跑一遍最短路，最短路图显然是个DAG，所以直接做在DAG上建的支配树即可
由于这题比较特殊，yy一下可以发现如果在入点的支配点不同，那么这个点肯定不会被支配，不用找LCA，直接判断即可，可以去掉一个log
code

C

sb题，冲一波AC自动机+DP就过了
然而这样时间复杂度是不对的
考虑压缩fail，每次暴力往上跳到第一个是某个文本串结尾的节点，可以发现压缩后最多跳$\sqrt{m}$次
因为跳一次长度至少-1，然而总字符串长度是$m$所以最多跳根号次
懒得写压缩了,凑合着看吧
code

Day 4

http://zhengruioi.com/contest/945
今天的题目真恶臭
感觉出题人对红茶颇有研究

A

瞎写一个线段树合并就过了。。
没啥好讲的
有一万种做法
code

B

不太会，玄妙DP，先研究一下

C

WTM，这么多年NTT白学了
只会打NTT，连DFT都不会了
考场上完全没有往随机方面去想
考虑生日悖论，大概取到$len=\sqrt{P}$的时候相同的可能性很大
先考虑次数$<=10^5$的情况
随机带$len$个数进去跑一遍多项式多点求值就可以了
然而蠢得一批，既然是随便带数，带原根进去就好了
所以跑一遍DFT，就可以得到把$g^0,g^1,g^2,..,g^{len?1}$带入多项式的值了
再翻$(mod?1)/len$倍即可
现在考虑次数$>=10^5$的情况
注意到原根是有循环节的，所以直接把次数$\%len$即可
可以考虑画一个单位圆，g跳len+r步和跳r步的位置是一样的
code