【练习记录】平日里口胡的题目系列1

大概就是有些题实在不想写,就把这些题给嘴了。

由于同一篇文章太长会造成很差的观感。所以就分成很多 $parts$ 了。

对于个人认为比较妙的题,会打上 * 的图标。

MdOI2020

当成月赛打了。T1写了个诡异的算法结果因为特判时没输出换行拿了64,然后就没有打的兴趣了(

A

考虑对于一种拆分是最优的。即 $(a,b,c)=d$,$d$ 为所求,那么发现会有 $d\cdot (\frac{a}{d}+\frac{b}{d}+\frac{c}{d})=n$。发现当 $\frac{a}{d},\frac{b}{d},\frac{c}{d}$ 三者不同时,一定可以转化成其中一个数 $=d$ 的构造方式。

所以考虑质因数分解之后枚举 $\frac{n}{d}$。发现当 $\frac{n}{d}\leq 5$ 的时候,当前枚举的 $d$ 不可以让 $\frac{a}{d},\frac{b}{d},\frac{c}{d}$ 三者不同。所以判掉这些数据,剩下的取 $\rm max$ 即可。

发现现在要求的,就是从 $n$ 的所有分解里面,挑出一个最接近 $6$ 且 $\geq 6$ 的构造 $\frac{n}{d}$ 的方案。发现最多需要三个素因子才可以超过 $6\to (2,2,2)$,最少的话一个就足够了。所以考虑 $\log ^3n$ 三重循环枚举所有的质因子即可。

质因数分解完全可以 $\rm pollard-rho$。最后复杂度 $O(T\max(\log^3 n,n^\frac{1}{4}))$

(这个题写的长是因为直接把自己写的题解给粘过来了)

B

考虑一个性质,排好序后,最后不变的一定是一个连续区间。所以考虑枚举这个连续区间,尺取或者二分出右端点,检验一下就可以了。复杂度 $O(n)$。

C

考虑一个性质。发现其实左上角的数定住之后,之后的数都确定了。所以可以随便用点差分 $trick$ 实现 $n^2$ .

D*

比较有趣的题。根据第二个子任务的提示可以发现,对于每个询问可以把当前点旋到根,然后求的就是一个区间内点的 $lca$ 的深度。发现这个东西有结合律,比较容易用线段树维护。

然而每次换根复杂度显然不对。考虑进一步分析性质,当询问点 $q$ 不在原树上的 $lca$ 的子树内时,换根不会影响距离,所以直接统计即可;当询问点 $q$ 不在 $lca$ 的子树内时,考虑换根之后的 $lca’$ 一定也是原树里 $p$ 的某个祖先。通过画图可以知道,只需要倍增找出 $p$ 的第一个包含 $[l,r]$ 内点的祖先即可。求交集可以用主席树来维护。复杂度 $(n\log^2n+q\log^2n)$。

E*

发现可以转化成枚举一个点 $x$ ,从 $x$ 的子树内外各选一对点使得 xor 值最大,发现直接拿Trie维护一个回滚莫队状物即可。复杂度 $n\sqrt n\log V$ 。

似乎可以用什么值域分块的黑科技优化一下。emmm但我还不会。

F

是个推式子题,暂时不是很想推。

EA的练习赛

发现自己被叫去验题结果啥都不会十分丢人.jpg

A

发现如果第一个字符和后面的任意一个字符相同,那么就一定不合法;反之一定合法。所以答案是 $26\times 25^{n-1}$ 。

B*

根据期望的线性性,发现可以将每个点的答案转化一下:$E=\sum_{i=1}^{n-1}P(x\geq i)$ 。

考虑每个点什么时候被删除。发现只跟离他最近的前后两个比他大的数有关,每当有一个与 $x$ 相邻时 $x$ 就会挂。所以用容斥原理算一下,$P(x\geq i)=1-P(pre\sim x)-P(x\sim~nxt)+P(pre\sim nxt)$ 。发现这东西显然有组合意义,所以算一波组合数即可。复杂度 $O(n^2)$ 。

C

有意思的题。发现切割方式严格要求从左到右,那么对于两根弦,如果以 $u_j\geq u_i,v_j\leq v_i$ 的方式相交,那么就可以把 $j$ 这条弦给删掉。所以删掉之后重新排序,然后按弦 $dp$。$f_i$ 表示处理完前 $i$ 根弦的 $\min$ 。那么转移就枚举一下把哪个 $j\sim i$ 的连续区间给删掉。

那么转移大概是 $f_i=\min_{0\leq j<i}(f_j+A_{u_{j+1}-1}\times B_{v_i+1})$ 。其中 $A,B$ 分别是 $a_i,b_i$ 的前后缀最小值。

发现稍微变一下形,就是 $f_j=-A_{u_{j+1}-1}\times B_{v_i+1}+f_i$。发现斜率 $B$ 单调,$x$ 坐标 $A$ 单调递减。所以就是在维护一个下凸壳,直接最裸的斜率优化就好了。

D**

很有意思的组合题。发现对于每个点,如果在访问他之前访问了比他深度更小的叶子节点,他就不会被访问。所以考虑对于一个点 $x$ 的每个祖先 $anc_x$ ,设 $anc_x$ 有 $n’$ 个儿子,其中有 $m’$ 个子树内叶节点的最小深度小于 $x$ 的深度,那么这一层不会进入死亡分叉的方案数就是 $\binom{n’}{m’+1}\cdot (n’-m’-1)!\cdot (m’)!$ ,计数思路大概就是选出 $m’+1$ 个位置来,每次选都把这 $m’+1$ 位置中的第一个位置留给当前的 $x$ 所在子树放,剩下就是排列数。

然后考虑进入 $x$ 的概率就是很神奇的 $\prod \frac{1}{m_{anc_i}’+1}$。考虑这个东西怎么快速算。发现对于同一棵子树,$lca$ 上方的信息都是一样的,改变的只有子树内部的方案。那么考虑对于每个儿子,直接按照「子树内叶子的最小深度」排序,就可以顺序处理出结果。

类似于用栈来维护 $k$ 级祖先的过程,发现只需要一个可撤销的树状数组即可。复杂度 $n\log n$。

E

似乎是一道神秘的插值题。鸽了鸽了。

LG二月月赛 · 加油武汉

没参加的一场月赛,似乎被爆破了.jpg

A**

这题本来想枚举最后选的哪个数来做,但是发现根本不科学,自闭了半天。就是考虑钦定了一个数,如果不是最后一个取他,那么前 $k$ 个一定都放比他小的数,同时可以在他的位置和 $k$ 个之间也放一些比他小的数,但是这些方案对于不同的前 $k$ 个元素的最大值,方案是不同的,所以复杂度很假也很麻烦。

发现似乎直接枚举前 $k$ 个元素的最大值比较容易做。分成两类来讨论,一类情况是取到了某个 $x$,另一类情况是不得不取最后一个,发现当且仅当集合里的最大值在前 $k$ 个才会发生。

1、第一种情况。对于每个最大值 $x$,取到他的概率是 $\frac{\binom{x-1}{k-1}}{\binom{n}{k}}$,在取到最大值为 $x$ 的情况下,期望就再乘上一个 $\frac{\mathrm{S-S_{p_x}}}{n-p_x}$。其中 $\rm S$ 表示集合元素的总和,$\rm S_x$ 表前 $x$ 小的元素的和,$p_x$ 表示 $x$ 是第几小的。不难发现这样是对的。

2、第二种情况。不难发现概率是 $\frac{\binom{n-1}{k-1}}{\binom{n}{k}}=\frac{k}{n}$ 。那么期望的话,发现这种情况下最后一个数是谁情况相同。所以乘上一个 $\frac{\mathrm{S}-x_{\max}}{n-1}$ 就完了。

嗯。这个故事告诉我们有时候期望题并不可以直接大力去组合所有情况来算,还是需要一定技巧的。

啊…不会转换组合对象…我太弱了…

B

由于是完全图,那么每个点贡献的异色三角形个数就是 $(n-1-b)\cdot b$ 。

所以最后算一下补,答案就是 $\binom{n}{3}-\frac{1}{2}\sum_{i=1}^n(n-1-b_i)\cdot b_i$ 。做完才发现是一道做烂了的题.jpg

C

sb费用流。发现最大流的情况下,不会出现一个点覆盖了另一个强连通分量中的某个点。所以可以直接流。用一些贪心的 $trick$ 就可以边数消掉一个 $n$ 了 。

D*

很有意思一道题。首先发现原来 $min_25$ 筛并不可以过得去。之后发现

于是可以发现,大概对于每个 $n$,他的 $\sigma_0$ 都是一个关于 $k$ 的 $\omega(n)$ 次多项式。于是就可以筛出多项式来,前缀和一下。然后就做完了。复杂度大概 $O(\max(\omega\cdot n, \omega\cdot q))$ 。

可能筛多项式需要一些诡秘的 $trick$ 吧。不过大概还是通过记录最小质因子来转移。

由于以前没见过这种题,于是写了个代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void sieve(int n){
poly[1][0] = 1 ;
for (int i = 2 ; i <= n ; ++ i){
if (!chk[i]){
frm[i] = 1 ;
chk[i] = 1 ;
mind[i] = i ;
mindc[i] = 1 ;
pr[++ cnt] = i ;
poly[i][0] = 1 ;
poly[i][1] = 1 ;
}
for (int m, j = 1 ; j <= cnt ; ++ j){
m = 1ll * pr[j] * i ;
if (m > n) break ; chk[m] = 1 ;
if (i % pr[j]) {
mind[m] = pr[j] ;
mindc[m] = 1, frm[m] = i ;
}
else {
mindc[m] = mindc[i] + 1 ;
mind[m] = mind[i] ; frm[m] = frm[i] ;
}
for (int k = 0 ; k <= 8 ; ++ k)
poly[m][k] = poly[frm[m]][k] ;
for (int k = 8 ; k >= 1 ; -- k)
(poly[m][k] += 1ll * mindc[m] * poly[m][k - 1] % P) %= P ;
if (!(i % pr[j])) break ;
}
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 0 ; j <= 8 ; ++ j)
poly[i][j] -= (poly[i][j] += poly[i - 1][j]) >= P ? P : 0 ;
}

E

有很长的题面以及红色的难度标签。于是决定跳过。

F

辣鸡二分答案题。难点在于知道要去二分答案。