大数定律: \lim\limits_{n->\infty} \sum\limits_{i=1}^{n} a_i \times (\frac{1}{n}) = E(a_i)
P5296 [北京省选集训2019]生成树计数
把边权 w 变成 e^{wx} 然后求一下在 \pmod{x^{k+1}} 意义下的行列式即可 .
因为 k 比较小 , 所以求逆和多项式乘法只能写O(k^2) , 直接套多项式板子会变慢 .
复杂度 O(n^3k^2).
P3746 [六省联考2017]组合数问题
循环卷积快速幂.
感觉和2020年联考A卷 d1t2 很像? 因为我当场做那个题的时候也是用的组合意义.
O(k^2(\log n+\log k))
CF474F Ant colony
线段树维护区间gcd,min以及cntmin即可.
如果写了O(n)-O(1) \gcd 可以做到一个 log.
CF585F Digits of Number Pi
建SAM/AC自动机之后数位dp.
我代码里写的是SAM,因为这样省空间.
O(nd^2*10)
每天一个爆零小技巧 : 计算 trans 不 return
P5308 [COCI2019] Quiz
$O(n*T),T$为$check$次数$.
每天一个爆零小技巧 : 斜率优化不弹队首
P5488 差分与前缀和
差分一次相当于和 (1-x) 卷积
前缀和一次相当于和 (1-x)^{-1} 卷积
注意到
(1-x)^k$ 的 $i$ 次项系数是 $(-1)^{i}\binom{k}{i}
(1-x)^{-k}$ 的 $i$ 次项系数是 $\binom{k+i-1}{i}$ $($ 这个可以通过广义二项式定理证明 $)
然后直接O(n)递推出所有系数,然后NTT就解决了.
每天一个爆零小技巧 : 在 k 是 10^{2328}的时候读入优化不取模
CF685C Optimal Point
先二分答案然后换元解方程,细节比较多.
CF708E Student's Camp
考虑一个\large dp_{i,l,r}表示目前到第i行,这一行的区间为[l,r]的方案数.
再记一个\large sum_{i,L}表示 \large \sum\limits_{l',r'\leq L} dp_{i,l,r}
然后推一推式子就可以O(nm)求出所有的sum_{i,L},这个问题就解决了.
CF698D Limak and Shooting Points
暴力枚举打的顺序然后bfs check.
O(n \times k!\times k)
CF521E Cycling City
在dfs树上如果有两个相交的环,那么必然有解：
1.$ $e1_x->e1_y->x
2.$ $e1_x->e2_x->e2_y->x
3.$ $e1_x->x
P3747 [六省联考2017]相逢是问候
首先可以想到通过欧拉定理计算.
不难发现只有前log次修改是有用的,那么直接维护就可以了.
实现的好可以做到O(nlog^2max(p,n))
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
dsu$ $on$ $tree$ 练习题$.
大概就是把字母x的权值看成2^{x-'a'},然后check一条链合法相当于链上异或和为0或2^h, dsu 一下就好了 .
---
[CF643G Choosing Ads](https://www.luogu.com.cn/problem/CF643G)
感觉这个套路已经做了一万次了吧..
线段树维护信息$,$每次删去 $\lfloor \frac{100}{p} \rfloor +1$ 个不同的数 $,$ 最后剩下的 $k$ 种数中必然包含答案$.
记 k = \lfloor \frac{100}{p} \rfloor +1, 复杂度为 O(nk^2logn)
P3224 [HNOI2012]永无乡
线段树合并/启发式合并板子题.
CF1364E X-OR
交互题.
CF536D Tavas in Kansas
先求完最短路,然后O(n^2) dp.
CF611G New Year and Cake
计算几何题.
考虑求出凸包然后在凸包上O(n)扫( 类似2-pointers, 同时维护面积大小 ), 然后用前缀和快速计算答案 .
CF527E Data Center Drama
欧拉回路题.
突然发现自己以前写的欧拉回路复杂度是假的!
O(nlogm)
每天一个爆零小技巧 : 在交题之前一不小心 shift + delete + enter 删掉自己的代码
CF587D Duff in Mafia
首先忽略边权,考虑求一组可行的方案.可以使用2-SAT实现,建图需要前后缀优化.
加上边权的限制就是加一个二分.
强制让一个东西不能选就是加一条 (x,1)->(x,0) 的边.
O(mlogm),$实现的时候注意节省空间$.
我的代码是|V|\leq 7m, |E| \leq 17m
CF516D Drazil and Morning Exercise
不难发现权值分布组成了一棵以f_x最小的x为根的树,其中父亲的权值一定\leq儿子的权值.
那么直接two-pointers,然后用并查集维护当前的答案就可以做到 O(nα(n))处理一组询问 .
复杂度 O(nα(n)q).
CF605E Intergalaxy Trips
考虑倒着做,从小到大更新概率,并维护不出现边的概率和出现边时的期望.
---
[P3825 [NOI2017]游戏](https://www.luogu.com.cn/problem/P3825)
$2-SAT.
枚举类型为x的场地的类型然后2-SAT即可.
O(2^d(n+m))
CF538H Summer Dichotomy
贪心的考虑n1,n2的取值然后二分图染色即可.
O(n+m)
CF571D Campus
对M操作带来的合并建树,并用dfs序建线段树,可以求出一个数最近的Z操作的时间,这样我们把询问差分成两个前缀询问,用启发式合并维护一下就可以了.
O(n\log n),$注意这题的空间限制$,$尽量不要用空间带$log$的做法$.
P6630 [ZJOI2020] 传统艺能
矩乘题.
CF568C New Language
2-SAT+$贪心$.
O(nm).
CF566E Restoring Map
首先非叶节点之间的边可以直接集合之间两两取and得到.
然后特判掉非叶节点个数\leq 2的情况,叶节点>3个的时候可以通过比较bitset得到叶节点的父亲.
\large O(\frac{n^3}{w}),$其中$w=64.
CF603E Pastoral Oddities
不难发现题目中的条件等价于所有联通块大小都是偶数.
可以用lct维护最小生成树,也可以分治.
O((n+m)\log(n+m))$ 或 $O(n\log n \log m),$ 但在实际效果上分治比 $lct$ 快 $.
CF585E Present for Vitalik the Philatelist
考虑求出f_d = [\gcd \{ S \} = d的 \{ S \} 的数量 ],
和 g_d = [ x \perp d 的 x 的数量 ] ,
那么答案为 ans =\sum\limits_{i>2}^{10^7} f_ig_i
可以反演之后 Dirichlet 前缀和 , O(w\log \log w)
P5787 二分图 /【模板】线段树分治
线段树分治 / \ LCT.
CF576E Painting Edges
线段树分治,当一个操作生效之后把它insert到线段树上即可.
O(n\log^2n+nk)
需要注意的是 , 理论上是可以用 lct 维护这个东西的 , 但是如果使用 lct 来维护会爆空间 .
CF553E Kyoya and Train
首先有一个O(mt^2)的暴力,然后容易发现转移是一个卷积的形式,并且转移图是一个DAG.
那么就可以分治FFT解决这个问题了 .
O(mt\log ^2t).
CF643F Bears and Juice
一道好题.
我们从信息熵的角度去考虑问题,即在这样一个问题中会有多少种熊醉酒情况( 在哪一天喝醉以及是否喝醉 ), 这个数值 Ans=\sum \binom{n}{i}\times x^i (x表示天数),不难发现这个数值是答案的上界.
并且我们可以构造出对应的方案使得在有Ans个桶的时候可以正确判断出哪一桶是酒 , 所以这个上界也是可以达到的 .
那么我们计算这个式子就可以算出答案了.
O(\frac{p^3}{\ln p}+pq).
CF547E Mike and Friends
把询问差分,建出AC自动机,用树状数组维护对答案的贡献.
也可以在广义SAM上线段树合并,但是很容易MLE,需要注意空间常数.
CF704B Ant Man
可以直接O(n^2)贪心,也可以用堆优化到O(n\log n).
CF611H New Year and Forgotten Tree
枚举prufer序列得到关键点的连接方式,然后跑网络流check.
记m=\lfloor \log_{10}n \rfloor \leq 6,复杂度为
O(m^{m-2}\times Dinic(m^2,m^2)).
P6627 [省选联考 2020 B 卷] 幸运数字
随便做.
P6628 [省选联考 2020 B 卷] 丁香之路
对于每组询问把编号为奇数的点之间通过一些(i,i+1)的边连接起来,然后做mst即可.
O(n^2).
CF704C Black Widow
考虑把布尔表达式当成点,在有下标绝对值相同的x_i的表达式之间连一条边.
不难发现只会有一些链和环,分类讨论dp一下就好了.
O(n+m).$ 代码细节很多$.
CF704D Captain America
考虑最大化花费较小的那个元素.
建图,有源汇上下界最大流.
O(Dinic(n,n)),$网络流图是个二分图$,$所以是$O(n\sqrt n)?
两维都要离散化,注意细节.
CF708D Incorrect Flow
对每条边(x,y)分别考虑.
1.$ $f\leq c:
(x,y,c-f,1)$ $(y,x,f,1)$ $(x,y,+\infty,2)
2.$ $f>c:
先加上f-c的花费再加边:
(y,x,f-c,0)$ $(y,x,c,1)$ $(x,y,+\infty,2)
然后考虑本来的流量f:加入上下界,连上上界=下界=f,费用为0的边
然后跑上下界最小费用流即可.
O(Zkw(n,n+m))
P4094 [HEOI2016/TJOI2016]字符串
建出SA,然后考虑二分答案后用主席树check.
时间O(n\log^2 n),空间O(n\log n)
如果离线可以做到时间O((n+m)\log n),空间O(n+m)
P3987 我永远喜欢珂朵莉~
P5610 [Ynoi2013]大学
用并查集维护可能要/x的数字的下标,每次修改先二分一下然后在并查集上往后跳.
每个a_i的变化次数为O(\log a_i)次.
每次a_i的值发生变化的时候在BIT上修改即可.
O(nd\alpha(n)+n\log n\log a_i).
CF679E Bear and Bad Powers of 42
势能线段树.
考虑维护每个数字到下一个42的次幂的距离,修改的时候如果这个距离被减成了负数就递归下去,就好了.
O(nlogn\times T),$其中$T$值域内的$42$的次幂的个数$,$为$11.
CF626G Raffles
经典贪心题.
对每个点记一下他+1和-1对答案造成的影响,每次修改之后计算一下彩票位置的变化即可.
O(n\log n).
CF578E Walking!
题目相当于找若干个子序列形如LRLRLR...或者RLRLRL...然后把它们拼起来.
我们把分出的子序列分为四类: LR,RL,LL,RR.
如果有形如LL或者RR必然有解.
否则如果只有一种RL/LR可以直接输出,在同时有RL,LR的情况下可以用一对RL LR 拼出一个 LL 和一个 RR
O(n).
CF643D Bearish Fanpages
在每个点x上记除了f_x之外a_x的权值,并把这个扔到f[i]的multiset里,然后模拟就可以了.
O((n+q)\log n)
虽然说起来很简单但是细节特别多.
CF578F Mirror Box
不难发现题目要求等价于给黑白染色后的图连出黑色生成树/白色生成树.
dfs$缩一下点$,$跑$Matrix-Tree$即可$.
O(nm\alpha+k^3).
CF671D Roads in Yusland
一种做法是dp,用堆维护对答案的贡献.
另一种做法比较有趣.线性规划的对偶
我们需要知道这个式子 :
max\{ c^Tx|Ax\leq b \}$ $=$ $min\{ b^Ty|A^Ty \geq c\}
这里b,c,x,y都是列向量, c,x长度相同 b,y长度相同.
然后我们把这个式子套进题目.
题目可以相当于我们选一些0/1放到y里使得A^Ty\geq一个全1列向量c.
对偶过去就变成:给每条边设置一个权值使得每条链上的权值和\leq这条链的权值.
然后用可并堆维护贪心即可. O(n\log n).
CF504E Misha and LCP on Tree
树剖,按dfs序建SA,然后每次询问查O(\log)次lcp即可.
O((n+m)\log n)
CF506E Mr. Kitayuta's Gift
先O(n^3)dp出答案的前7n+10项,然后跑BM即可.
CF568E Longest Increasing Subsequence
首先重复填数对答案没有影响,所以先忽略这个条件.
记f_i为 以i为结尾的LIS的长度, g_i 为以i为结尾的LIS的上一位.
记Min_x为 当前长度为x的LIS的最小的结尾 pos_x当前长度为x的LIS的最小的结尾的位置.
这些都可以简单dp出来.
然后我们考虑怎么构造方案.
不是-1的位置x我们可以直接跳到g_x .
如果x所在的位置是-1,那么我们优先找a_y ≠ -1 ,且a_y<a_x,f_y=当前的长度-1,那么我们就跳到位置y.
否则,我们就只能跳到最近的一个-1的位置.
O(n\log n+m\log m+(n+m)k)
CF704E Iron Man
考虑对每条重链/轻边分别做,最后答案取个min就可以了.
求线段最早相交的时间可以用set维护.
O(n\log n\log m).
AT3858 [AGC020D] Min Max Repetition
简单构造.
不难证明最小的次数k=max(\lceil \frac{a}{b+1} \rceil,\lceil \frac{b}{a+1} \rceil),然后数列一定是形如AAAABAAAABAAAAB...然后BBBABBBBABBBBA...的形态,二分一下分隔点然后对每个位置O(1)判断即可.
O(T(\log a+(d-c)))
AT3859 [AGC020E] Encoding Subsets
直接记忆化搜索即可.可以证明,状态总数不会超过O(2^{\frac{n}{8}}+n^3).
复杂度是O(n^2S)的,其中S表示状态数.
AT3860 [AGC020F] Arcs on a Circle
首先破环为链,令最长的l_i所在的位置为0.
然后对其它的l_i,枚举它们位置的小数部分的大小关系,然后再dp即可.
O((n-1)!\times 2^{n-1} \times (c\times n)^2).
P5894 [IOI2013]robots 机器人
my solution
首先题意可以转化为:每个玩具有两个属性值x_i,y_i,弱机器人可以拿掉x_i<A_i的玩具,小机器人可以拿掉y_i<B_i的玩具.
不难想到可以二分答案.
考虑如何check是否能在mid分钟的时间内拿走所有的玩具.
首先如果只有一维,显然可以直接对x_i和A_i排序然后丢掉多余的机器人,直接比大小即可.
那么多加了一维就是对x先贪心,每次尽量拿走y更大的数字即可.
这个贪心很容易用一个堆来实现.
O(n\log ans \log n).
CF526G Spiders Evil Plan
首先选y条链相当于找2y个叶子节点,把它们都联通的边集的边权和.
不难发现必然会选到直径的两个端点,所以把两个直径拿出来分别建树.
如果没有强制包含x的限制,那么就可以直接长剖贪心.
但是x不一定会在选2y-1个叶子节点的方案当中,
那么我们考虑这两种情况:
在2y-2的方案上加一条包含x的长链.
在2y-1的方案上换掉一条长链,并加上一条包含x的长链.
这个过程可以用树上倍增实现.
O((n+q)\log n).
CF1043F Make It One
不难发现答案\leq 7.
枚举答案,容斥check就可以了.
O(n\log n\times ans).
CF241D Numbers
只保留a_i\leq 24的数值,然后O(2^{24})暴力即可.
P4491 [HAOI2018]染色
二项式反演题.
$g_n = $ 恰好 $n$ 种颜色满足条件的方案数
我们要求的是$g_{0..n},$但是$g$不容易直接求$,$那么就先求出$f_{0..n}$然后二项式反演即可得到$g.
反演的部分可以用NTT实现.
O(T\log T),$其中$T=\min(m,\lfloor\frac{n}{S} \rfloor).
P3943 星空
CF79D Password
状压dp.
把问题转换为差分序列上的问题,然后就可以状压dp了.
转移值可以通过bfs提前求出.
CF809E Surprise me!
反演题.
记p_i为权值为i的点是什么.
\large \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}φ(a_ia_j)dis(i,j)
\large = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}φ(ij)dis(p_i,p_j)
\large = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac {\large φ(i)φ(j)\gcd(i,j)}{\large φ(\gcd(i,j))} dis(p_i,p_j)
\large = \sum\limits_{d=1}^{n} \frac{\large d}{\large φ(d)} \sum\limits_{i=1}^{\large \lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\large \lfloor \frac{n}{d} \rfloor} φ(id)φ(jd)dis(p_{id},p_{jd})[i\perp j]
\large = \sum\limits_{d=1}^{n} \frac{\large d}{\large φ(d)} \sum\limits_{p=1}^{\large \lfloor \frac{n}{d} \rfloor} \mu(p)\sum\limits_{i=1}^{\large \lfloor \frac{n}{dp} \rfloor}\sum\limits_{j=1}^{\large \lfloor \frac{n}{dp} \rfloor} φ(idp)φ(jdp)dis(p_{idp},p_{jdp})
令T=dp,把T提出来:
\large \sum\limits_{T=1}^{n} (\large \sum\limits_{d|n}\frac{\large d}{\large φ(d)} \mu(\large \frac{\large T}{\large d}))\sum\limits_{i=1}^{\large \lfloor \frac{n}{T} \rfloor}\sum\limits_{j=1}^{\large \lfloor \frac{n}{T} \rfloor} φ(iT)φ(jT)dis(p_{iT},p_{jT})
枚举T,然后建虚树,在虚树上求答案即可.
O(n\log n).
SP22549 DIVFACT4 - Divisors of factorial (extreme)
对于每组询问,小于\sqrt n的部分暴力,大于\sqrt n的部分可以数论分块.
问题变为若干个询问区间质数个数的问题,且询问端点( 除了其中最多一个 ) 都是形如\lfloor \frac{n}{i} \rfloor 的数,因此Min25筛即可解决.
O(T(\large \sqrt{n}+\frac{n^{\frac{3}{4}}}{\log n}))
注意模数很大,要使用快速乘.
CF666D Chain Reaction
O(2^4)$枚举每个点的移动方向$.
然后分五类讨论即可(
P3380 【模板】二逼平衡树（树套树）
在值域上建线段树,线段树上套平衡树维护每个点所包含值域区间的下标集合.
所有操作的复杂度都是O(\log^2).
P4916 [MtOI2018]魔力环
考虑Brunside然后计数.
令F(n,m)为不考虑环,有n个黑的, m个白的方案数.
令G(n,m)为考虑环的方案数.
F(n,m)$可以枚举连续$k+1$个黑色的总数并容斥$,O(\lfloor \large \frac{n}{k+1} \rfloor)$ 计算$.
G(n,m)=\sum\limits_{i=0}^k (i+1)F(n-i,m-1).
所以G(n,m)可以O(n)计算.
然后枚举\gcd (n,m)的约数并计数即可.
复杂度O(n\sqrt n)
CF1149D Abandoning Roads
考虑一条路径存在的条件:在已经把A边形成的联通块合并起来的时候,当且仅当路径中的所有B边连出了一个环时不合法,否则必定合法.
那么很容易有一个O((n+m)2^n)的状压DP.
发现大小\leq3的联通块是不用记录进状态里的,只需要临时判一下就好.
这样联通块个数就变成\lfloor \frac{n}{4} \rfloor 了.
O((n+m)2^{\lfloor \frac{n}{4} \rfloor}.)
P5279 [ZJOI2019]麻将
考虑建出麻将自动机,用dp_{0/1,0/1/2,0/1/2}和cnt来表示胡牌状态.
搜索一下可以发现自动机里的点数只有2092种.
然后O(n^2\times 2092) DP一下即可.
P4314 CPU监控
区间赋值/区间加/查询区间最大值/查询区间历史最大值.
维护加标记,区间历史最大加标记,赋值标记,历史最大赋值标记即可.
设序列长度为n,操作次数为m,则复杂度为O((n+m)\log n).