人工智能AB组大讨论"/>
21人工智能AB组大讨论
ZR模拟赛
Day 1
A
显然可以斜率优化，不过太蠢了
注意到一个很重要的性质，以每个点为圆心，以到别的点的最短距离的 1 2 \large \frac{1}{2} 21为半径画圆，可以发现这若干个圆是不相交的，用反证法易证
所以以最短距离为半径画圆的面积和最多为 2 n m 2nm 2nm
暴力一圈圈往外判断即可（记一下每一行的区间容易实现）
code
B
显然一开始染的颜色可以归到一个联通块上
可以发现，按照题目的那种方式变换，联通块的周长是不会变的，所以可以逆推，最开始的联通块的周长
规定一个方向
然后对于每个小正方形，如果左边，左上，正上都有格子的话这个格子就没有必要染色了
代码实现也非常简单
code
C
首先套一手拉格朗日乘子法，得到每一处的导数是相等的
然后暴力冲一发结果爆精度了。。
不太会，先咕咕咕着
Day 2
A
发现左上和右下可以分开考虑，最后再乘起来
枚举每一个格子，然后从左往右维护一个列的扫描线，对于障碍暴力清空，对于障碍一下的全部+1，那个线段树xjb搞即可
code
然而考场降智维护了平方和，写到一半发现不对把那部分全删了。。
B
BC都是多项式，我需要先研究一下。。
C
同上
Day 3
出题人不给大样例，痛失AK /dk
A
OSU人感觉很亲切，然而早已退坑
首先发现和Day 1 T 3一样可以套拉格朗日乘子法的套路
先把每一块的导数写出来，是钦定全部相等
对于第 i i i项
f ′ [ i ] = ( ( d i − 1 x ) 2 ) ′ = 2 d 2 i − 2 x \large f'[i]=((d^{i-1}x)^2)'=2d^{2i-2}x f′[i]=((di−1x)2)′=2d2i−2x
于是乎可以得到每一块 x x x的比值为 d 2 d^2 d2
可以得到
x + d 2 x + d 4 x + . . . d 2 n − 2 x = W W = x ( d 2 − 1 d 2 n − 1 ) x+d^2x+d^4x+...d^{2n-2}x=W \\ W=x(\frac{d^2-1}{d^{2n}-1}) x+d2x+d4x+...d2n−2x=WW=x(d2n−1d2−1)
x = W d 2 n − 1 d 2 − 1 x=W\frac{d^{2n}-1}{d^2-1} x=Wd2−1d2n−1
然后在把这个带入
x 2 + d 2 x 2 + d 4 x 2 + . . . d 2 n − 2 x 2 = W 2 d 2 − 1 d 2 n − 1 \large x^2+d^2x^2+d^4x^2+...d^{2n-2}x^2 \\ =W^2\frac{d^2-1}{d^{2n}-1} x2+d2x2+d4x2+...d2n−2x2=W2d2n−1d2−1
直接计算即可
code
B
支配树板子题
考虑对起点跑一遍最短路，最短路图显然是个DAG，所以直接做在DAG上建的支配树即可
由于这题比较特殊，yy一下可以发现如果在入点的支配点不同，那么这个点肯定不会被支配，不用找LCA，直接判断即可，可以去掉一个log
code
C
sb题，冲一波AC自动机+DP就过了
然而这样时间复杂度是不对的
考虑压缩fail，每次暴力往上跳到第一个是某个文本串结尾的节点，可以发现压缩后最多跳 m \sqrt{m} m 次
因为跳一次长度至少-1，然而总字符串长度是 m m m所以最多跳根号次
懒得写压缩了,凑合着看吧
code
Day 4
今天的题目真恶臭
感觉出题人对红茶颇有研究
A
瞎写一个线段树合并就过了。。
没啥好讲的
有一万种做法
code
B
不太会，玄妙DP，先研究一下
C
WTM，这么多年NTT白学了
只会打NTT，连DFT都不会了
考场上完全没有往随机方面去想
考虑生日悖论，大概取到 l e n = P len=\sqrt{P} len=P 的时候相同的可能性很大
先考虑次数 < = 1 0 5 <=10^5 <=105的情况
随机带 l e n len len个数进去跑一遍多项式多点求值就可以了
然而蠢得一批，既然是随便带数，带原根进去就好了
所以跑一遍DFT，就可以得到把 g 0 , g 1 , g 2 , . . , g l e n − 1 g^0,g^1,g^2,..,g^{len-1} g0,g1,g2,..,glen−1带入多项式的值了
再翻 ( m o d − 1 ) / l e n (mod-1)/len (mod−1)/len倍即可
现在考虑次数 > = 1 0 5 >=10^5 >=105的情况
注意到原根是有循环节的，所以直接把次数 % l e n \% len %len即可
可以考虑画一个单位圆，g跳len+r步和跳r步的位置是一样的
code
Day5
Day6
A
sb题，9mins就切了
code
B
那么写成式子就是
∑ i n ∑ j = i + 1 n V i V j × ∑ k = 0 ( n − 3 ) ∗ ( n − 4 ) / 2 p n ( 1 − p ) k S k p n − j p i − 2 \sum_i^{n}\sum_{j=i+1}^nV_iV_j\times\sum_{k=0}^{(n-3)*(n-4)/2} p^n(1-p)^kS_kp^{n-j}p^{i-2} i∑nj=i+1∑nViVj×k=0∑(n−3)∗(n−4)/2pn(1−p)kSkpn−jpi−2
i i i枚举的是 a 2 a_2 a2, j j j枚举的是 a n a_n an, p n p^n pn是查询到存在的边的概率， k k k枚举的是逆序对个数为 k k k的(长度为n-3(去掉a1,a2,an))排列数，后面的两项表示的是 a 2 , a n a_2,a_n a2,an贡献的逆序对数
考虑化简，吧与 i , j i,j i,j相关的提出来，显然可以分成两个部分算
p n ∑ i n ∑ j = i + 1 n V i p i − 2 V j p n − j × ∑ k = 0 ( n − 3 ) ∗ ( n − 4 ) / 2 ( 1 − p ) k S k p^n\sum_i^{n}\sum_{j=i+1}^nV_ip^{i-2}V_jp^{n-j}\times\sum_{k=0}^{(n-3)*(n-4)/2} (1-p)^kS_k pni∑nj=i+1∑nVipi−2Vjpn−j×k=0∑(n−3)∗(n−4)/2(1−p)kSk
前面那部分显然可以线性算，主要是看后面这部分
∑ k = 0 ( n − 3 ) ∗ ( n − 4 ) / 2 ( 1 − p ) k S k \sum_{k=0}^{(n-3)*(n-4)/2} (1-p)^kS_k k=0∑(n−3)∗(n−4)/2(1−p)kSk
考虑关于逆序对个数个数的生成函数
∏ i = 1 n − 3 ( ∑ j = 0 i ( 1 − p ) j x j ) \prod_{i=1}^{n-3}(\sum_{j=0}^i(1-p)^jx^j) i=1∏n−3(j=0∑i(1−p)jxj)
然后你要求的就是系数之和，这样的话就不用管 x x x了
∏ i = 1 n − 3 ( ∑ j = 0 i ( 1 − p ) j ) = ∏ i = 1 n − 3 1 − ( 1 − p ) i + 1 p \prod_{i=1}^{n-3}(\sum_{j=0}^i(1-p)^j)=\prod_{i=1}^{n-3}\frac{1-(1-p)^{i+1}}{p} i=1∏n−3(j=0∑i(1−p)j)=i=1∏n−3p1−(1−p)i+1
然后这个东西现在也可以线性算了
最后把两块乘在一起即可
code
C
咕
Day 7
T1 FST，痛失Rank 7，真的下饭
A
已经连了 n n n条边，剩下的要怎么连才可以被两种颜色染色（二分图）
因为二分图的充要条件是不存在奇环，所以考虑一种连边使得不会出现奇环即可
( 2 i − 1 ) − − − > ( 2 i ) (2i-1) ---> (2i) (2i−1)−−−>(2i)
容易发现这种连边是满足要求的（分奇偶讨论一下易证），直接冲即可
code
B
考场上一直在冲C，导致这题白给
容易发现，一个子树是BST的充要条件是它在中序遍历对应的区间内的权值是单调不降的
于是我们可以纪录满足在中序遍历中 a i − 1 < = a i < = a i + 1 a_{i-1}<=a_i<=a_{i+1} ai−1<=ai<=ai+1的点的数量
我们对于每一个点，记录它的前驱和后继，以及是否是BST（用树状数组+dfn序），每次修改，需要更新它以及它前驱和后继的答案，然后容易发现每次更新肯定是会将x以及向上的一段祖先的状态（二分即可）
时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)实现还算简单
code
Day 8
数组开小，痛失rank4
丢脸
A
网络流一眼题，因为太困了写得有点慢
code
B
Day 9
第二题和题解的打得反了过来，。。。
A
看一眼数据范围可以很容易想到区间DP，但是如果考虑每次拿走哪一个点话会有后效性，不适合DP，于是我们考虑将状态改为每次枚举最后一个拿走的是哪个，这样只需要将 i i i和 a [ l − 1 ] , a [ r + 1 ] a[l-1],a[r+1] a[l−1],a[r+1]比较就行了
挺不错的
code
B
更多推荐
21人工智能AB组大讨论
发布评论