模板 – Tgotp-Blog

 省选前模板复习

看了 zbww巨佬的博客,我决定也开一篇。

首先,我没有他那么神仙,所以我只会复习一些小水题模板。

 

记录:

 

polya:

洛谷P4980

代码

 

F. The Sum of the k-th Powers

 

Picnic Planning(野餐计划)

最小限度生成树

c++代码如下:

 

2260: 商店购物 && 4349: 最小树形图 朱刘算法

2260的数据应该有误,存在自环,然而网上的题解一看都是一个样子。。。

简直了。。。重点是还能跑出来?!

这题就是最小树形图的板子题。

我的代码必须强行跑一次朱刘才能过2260

 

思路大致如下:
考虑到不存在自环时,每个点一定除了第一次以外均会被以最优方式[......]

Read more

虚树 模板

把要建树的点拿出来按照dfs序升序排列

用栈维护当前的链,然后因为考虑不能破坏树的结构,那么相邻两点的lca一定会插入。

因为可能有自环或者连向0点,add操作对应修改一下

简单维护即可

c++代码如下:

[......]

Read more

2982: combination

lucas定理模板

c++代码如下:

 

NTT & FFT

发现没有FFT板子,就从我CSDN上博客拷过来了。。。

FFT:

ntt:

 

1941: [Sdoi2010]Hide and Seek

突然发现 SCOI之前我tm刷的基本都是SDOI 的题…
kd-tree板子题…
c++代码如下:

 

3172: [Tjoi2013]单词

直接套上ac自动机模板。

然后倒序扫一遍就好了。

c++代码如下:

 

#35. 后缀排序

sa模板

推荐文章:https://zhuanlan.zhihu.com/p/21283102

先学会基数排序,然后倍增sa就是将倍增的两段分别作为第一关键字第二关键字排序,搞定。

c++代码如下:

 [......]

Read more