ACM板子¶
重链剖分（HLD)¶
namespace HLD{
//树的常规信息---
vector<int>tree[N];
int fa[N],size[N],depth[N];//深度用于lca
//---树的常规信息
int top[N];//链头
int wson[N];//重儿子
int hld_dfn[N],dfncnt;//dfn序（一条重链和一个子树dfn序连续
void dfs1(int u,int father){//第一次dfs找到重儿子，父亲,子树重量和深度
size[u]=1;fa[u]=father;
depth[u]=depth[father]+1;
for(int v:tree[u])
{
if(v!=father){//不回父边
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[wson[u]]) wson[u]=v;//重儿子更换
}
}
}
void dfs2(int u,int father,int utop){//第二次dfs创建重链，标记链头，找到dfn序
top[u]=utop;
hld_dfn[u]=(++dfncnt);//dfs序
//.........//可添加dfs序维护的东西
if(wson[u]!=0) dfs2(wson[u],u,utop);//先遍历重儿子，链头不变
for(int v:tree[u]){
if(v!=father&&v!=wson[u]){
dfs2(v,u,v);//再遍历轻儿子，链头变为轻儿子自身
}
}
}
int lca(int u,int v){//使用HLD找到LCA//也可改为返回ans
while(top[u]!=top[v])
{
if(depth[top[u]]>depth[top[v]]) swap(u,v);//保证v的链头深度较深
//...//这里可以更新dfs序中的[hld_dfn[top[v]],hld_dfn[v]]
v=fa[top[v]];
}
if(depth[u]>depth[v]) swap(u,v);// 保证v比较深
//...//这里可以更新[hld_dfn[u],hld_dfn[v]]
return u;
}
}
树状数组¶
namespace BIT{
int bit[N];//树状数组本体
int n;//树状数组大小
int lowbit(int x) {return x&(-x);}
void update(int id,int date)//单点加
{
for(int i=id;i<=n;i+=lowbit(i)) bit[i]+=date;
}
int query(int id)//查询前缀和
{
int res=0;
for(int i=id;i>0;i-=lowbit(i)) res+=bit[i];
return res;
}
}
快速幂¶
递归写法¶
long long fast_pow(long long a,long long k){
if(k==0) return 1;
long long res=fast_pow(a,k>>1)%p;
if(k%2)
return ((res*res)%p*a)%p;
else
return (res*res)%p;
}
非递归写法¶
long long fast_pow(long long a,long long k)
{
//a为当前位对应的a的幂次
long long res=1;
while(k>0)
{
if(k&1) res=(res*a)%p;
a=(a*a)%p;
k>>=1;
}
return res;
}
memset¶
无论t是几维数组，均可以使用
memset(t,val,sizeof(t));
进行初始化，使其全部为val，例如当val=0时数组将被全部初始化为0
Note
注意：int数组只能初始化为-1或0，char数组则可以任意（有关字节存储问题）
SAM¶
注：并未完全完善
namespace SAM{
void text();
int last=0;//原串所在节点
int cnt=0;//目前开创节点
struct node
{
int son[26];
int father=-1;//link树上的
int num;
int len;
}sam[N<<1];
void newnode(int length,int number){//建立新节点满足
//cnt++;
sam[++cnt].len=length;
sam[cnt].father=-1;//先设父节点未知（建完后只有根节点0父节点未知）
sam[cnt].num=number;
memset(sam[cnt].son,0,sizeof(sam[cnt].son));
}
void insert(int c){//输入单字符（按字母表转化为数字）
newnode(sam[last].len+1,1);//建立新endpos
int now=cnt,p=last;//现在的节点编号和正在跳father的节点编号
//cout<<now<<" "<<p<<endl;
while(!sam[p].son[c]&&p!=-1)//跳father直到有这个儿子或者到头(越过0节点的头)
{
//cout<<p<<endl;
sam[p].son[c]=now;
p=sam[p].father;
}
if(p==-1)
sam[now].father=0;//cout<<"ee"<<endl;//父亲为根
else{
int sonnode=sam[p].son[c];//待拆点/处理的点
if(sam[sonnode].len==sam[p].len+1) sam[now].father=sonnode;//不用拆点
else{//拆点
//cout<<"ee";
newnode(sam[p].len+1,0);
int newson=cnt;
sam[newson].father=sam[sonnode].father;
sam[sonnode].father=newson;//父亲关系
memcpy(sam[newson].son,sam[sonnode].son,sizeof(sam[sonnode].son));//儿子关系
//前面的儿子关系
while(p!=-1&&sam[p].son[c]==sonnode)
{
sam[p].son[c]=newson;//变更关系
p=sam[p].father;
}
sonnode=newson;//便于后边统计数量
sam[now].father=newson;
}
//cout<<sonnode<<endl;
}
last=now;
}
int query(string s)//查询字符串s次数
{
int now=0,flag=1;
for(int i=0;i<s.length();i++){
int id=s[i]-'a';
if(!sam[now].son[id]) {flag=0;break;}
now=sam[now].son[id];
}
if(flag) return sam[now].num;
else return 0;
}
void add(string t){//往后插入t
for(char i:t)
{
insert(i-'a');
//cout<<sam[cnt].len-sam<<endl;
//text();
}
}
long long total()//找子串个数
{
long long res=0;
for(int i=1;i<=cnt;i++)
{ if(sam[i].num!=1)
res=max(res,1ll*sam[i].num*sam[i].len);
}return res;
}
void text(){//输出SAM
cout<<"-----------------------------------------------"<<endl;
for(int i=1;i<=cnt;i++)
{
cout<<i<<":father-"<<sam[i].father<<endl;
cout<<"len:"<<sam[i].len<<" num:"<<sam[i].num<<endl;
cout<<"son:";
for(int j=0;j<=25;j++){
if(sam[i].son[j]) cout<<j<<"-"<<sam[i].son[j]<<" ";
}
cout<<endl<<endl;
}
cout<<"-----------------------------------------------"<<endl;
}
}
AC自动机¶
给你一个文本串 \(S\) 和 \(n\) 个模式串 \(T_{1 \sim n}\)，请你分别求出每个模式串 \(T_i\) 在 \(S\) 中出现的次数。
第一行包含一个正整数 \(n\) 表示模式串的个数。
接下来 \(n\) 行，第 \(i\) 行包含一个由小写英文字母构成的非空字符串 \(T_i\)。
最后一行包含一个由小写英文字母构成的非空字符串 \(S\)。
数据不保证任意两个模式串不相同。
输出包含 \(n\) 行，其中第 \(i\) 行包含一个非负整数表示 \(T_i\) 在 \(S\) 中出现的次数。
对于 \(100 \%\) 的数据，\(1 \le n \le 2 \times {10}^5\)，\(T_{1 \sim n}\) 的长度总和不超过 \(2 \times {10}^5\)，\(S\) 的长度不超过 \(2 \times {10}^6\)。
#include<bits/stdc++.h>
#define N 1145141
using namespace std;
namespace AC{//对应P5357即求各串出现次数的统计
int cnt=0;//动态开点
int total[N];//对于串出现次数的统计
struct node{
int ch[26];
int fail=0;
int num=0;
vector<int>end;//注意可能有重复的字符串
}actree[N];//ac自动机本体
int inq[N];
void newnode(){
actree[++cnt].fail=0;
actree[cnt].end.clear();
inq[cnt]=0;
memset(actree[cnt].ch,0,sizeof(actree[cnt].ch));
}
void insert(string s,int id)//加入一个字符串
{
int now=0;
for(int i=0;i<s.length();i++)
{
int id=s[i]-'a';
if(!actree[now].ch[id]) {
newnode();
actree[now].ch[id]=cnt;
}
now=actree[now].ch[id];
}
actree[now].end.push_back(id);
}
void bfs_fail()//bfs求fail指针
{
queue<int>BFS;
for(int i=0;i<26;i++) if(actree[0].ch[i]) BFS.push(actree[0].ch[i]);
while(!BFS.empty())
{
int now=BFS.front();
//cout<<now;
BFS.pop();
for(int i=0;i<26;i++)
{
if(actree[now].ch[i]){//有了话fail为父亲的fail后继并且入队
actree[actree[now].ch[i]].fail=actree[actree[now].fail].ch[i];
inq[actree[actree[now].fail].ch[i]]++;
BFS.push(actree[now].ch[i]);
}
else{//无了话儿子就是父亲的fail后继
actree[now].ch[i]=actree[actree[now].fail].ch[i];
}
}
}
}
int query(string s){//询问有多少种字串出现
int res=0;
int now=0;
for(int i=0;i<s.length();i++)
{
int id=s[i]-'a';
now=actree[now].ch[id];
actree[now].num++;
}
return res;
}
void init()//初始化AC自动机
{
cnt=-1;
newnode();
cnt=0;
}
void topo(){//拓扑排序求total
queue<int>BFS;
for(int i=1;i<=cnt;i++)
{
if(inq[i]==0){
BFS.push(i);
}
}
while(!BFS.empty()){
int now=BFS.front();BFS.pop();
for(int id:actree[now].end) total[id]+=actree[now].num;
int nxt=actree[now].fail;
if(nxt!=0){
actree[nxt].num+=actree[now].num;
inq[nxt]--;
if(inq[nxt]==0) BFS.push(nxt);
}
}
}
}
int n;
string s[214514],t="";
int main()
{
AC::init();
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
AC::insert(s[i],i);t+='&';
t+=s[i];
AC::total[i]=0;
//cout<<"kk";
}
AC::bfs_fail();
AC::query(t);
AC::topo();
int maxid=0;
for(int i=1;i<=n;i++){
cout<<AC::total[i]<<endl;
}
}
最小圆覆盖¶
给出 \(N\) 个点，让你画一个最小的包含所有点的圆。
输入：第一行一个整数 \(N\) 表示点的个数。接下来 \(N\) 行每行两个实数 \(x_i,y_i\) 表示点的坐标。最多两位小数。
输出：第一行一个实数表示圆的半径。第二行两个实数表示圆心的坐标。
#include<bits/stdc++.h>
#define N 114514
const double eps=0.000001;
using namespace std;
std::mt19937 rng(std::random_device{}());
bool is_equal(double A,double B){
if(fabs(A-B)<=eps) return 1;
return 0;
}
namespace geo{
struct point{
double x,y;
};
struct circle{
point O;
double r;
};
double dis(point A,point B){
double dis2=(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
double res=sqrt(dis2);
return res;
}
int point_in_circle(point P,circle C){//in:1,on:0,out:-1
double dis_o=dis(P,C.O);
if(is_equal(dis_o,C.r)) return 0;
if(dis_o<C.r) return 1;
else return -1;
}
circle O_for_point(int N_p,point Plist[])//N_p:1,2,3
{
if(N_p==1)
return {Plist[0],0.0};
else if(N_p==2){
point reso={(Plist[0].x+Plist[1].x)/2.0,(Plist[0].y+Plist[1].y)/2.0};
double resr=dis(Plist[0],Plist[1])/2.0;
return {reso,resr};
}else{
point a=Plist[0],b=Plist[1],c=Plist[2];
double a1, a2, b1, b2, c1, c2;
point reso;
a1 = 2 * (b.x - a.x), b1 = 2 * (b.y - a.y),
c1 = b.x*b.x - a.x*a.x + b.y*b.y - a.y*a.y;
a2 = 2 * (c.x - a.x), b2 = 2 * (c.y - a.y),
c2 = c.x*c.x - a.x*a.x + c.y*c.y - a.y*a.y;
if (is_equal(a1, 0)) {
reso.y = c1 / b1;
reso.x = (c2 - reso.y * b2) / a2;
} else if (is_equal(b1, 0)) {
reso.x = c1 / a1;
reso.y = (c2 - reso.x * a2) / b2;
} else {
reso.x = (c2 * b1 - c1 * b2) / (a2 * b1 - a1 * b2);
reso.y = (c2 * a1 - c1 * a2) / (b2 * a1 - b1 * a2);
}
double resr=dis(reso,a);
return {reso,resr};
}
}
circle SEC(int N_p,point Plist[]){//下标从1开始
// point
shuffle(Plist+1,Plist+1+N_p,rng);
point p1[1]={Plist[1]};
circle res=O_for_point(1,p1);
for(int i=1;i<=N_p;i++)
{
if(point_in_circle(Plist[i],res)!=-1) continue;
point p2[2]={Plist[1],Plist[i]};
res=O_for_point(2,p2);
for(int j=2;j<=i;j++){
if(point_in_circle(Plist[j],res)!=-1) continue;
point p2[2]={Plist[i],Plist[j]};
res=O_for_point(2,p2);
for(int k=1;k<=j;k++)
{
if(point_in_circle(Plist[k],res)!=-1) continue;
point p3[3]={Plist[i],Plist[j],Plist[k]};
res=O_for_point(3,p3);
}
}
}return res;
}
}
geo::point P[N];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
//shuffle(P+1,P+1+n,rng);
geo::circle ans=geo::SEC(n,P);
printf("%.14lf\n%.14lf %.14lf\n",ans.r,ans.O.x,ans.O.y);
}
Lucas 定理¶
对于素数 \(p\)，有
\[\binom{n}{k} \equiv \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor}\binom{n \bmod p}{k \bmod p} \pmod{p}.\]
其中，当 \(n<k\) 时，二项式系数 \(\binom{n}{k}\) 规定为 0。
int C(int n, int m,int p) {
if(m==0) return 1;
return (C(n/p,m/p)*C(n%p,m%p))%p;
}
特别的对于较小的素数，考虑小规模数提前处理可以解决：
如\(p=3\)
int smallC[3][3] = {
{1, 0, 0},
{1, 1, 0},
{1, 2, 1}
};
int C(int n, int m) {
if(n<3&&m<3) return smallC[n][m];
if(m==0) return 1;
return (C(n/3,m/3)*C(n%3,m%3))%3;
}
bitset转int¶
int a=(int)b.to_ulong();
long long x = (long long)b.to_ullong();
//下为实际，上为常用
unsigned long x = b.to_ulong(); // ≤32 位
uint64_t y = b.to_ullong(); // ≤64 位
极大值极小值¶
const int INF = 0x3f3f3f3f;const long long LLINF = 0x3f3f3f3f3f3f3f3fLL;
快读快写¶
同样可以用于int128的输入输出等
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
//快读
void write(int x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
//快写
输入输出优化¶
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
LCA¶
#include<bits/stdc++.h>
#define N 514514
using namespace std;
int n,m,s;
namespace BIT{
struct bitnode{//信息包括最大权值和权值和
};
}
namespace HLD{
//树的常规信息---
vector<int>tree[N];
int fa[N],size[N],depth[N];//深度用于lca
//---树的常规信息
int top[N];//链头
int wson[N];//重儿子
int hld_dfn[N],dfncnt;//dfn序（一条重链和一个子树dfn序连续
void dfs1(int u,int father){//第一次dfs找到重儿子，父亲,子树重量和深度
size[u]=1;fa[u]=father;
depth[u]=depth[father]+1;
for(int v:tree[u])
{
if(v!=father){//不回父边
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[wson[u]]) wson[u]=v;//重儿子更换
}
}
}
void dfs2(int u,int father,int utop){//第二次dfs创建重链，标记链头，找到dfn序
top[u]=utop;
hld_dfn[u]=(++dfncnt);//dfs序
//.........//可添加dfs序维护的东西
if(wson[u]!=0) dfs2(wson[u],u,utop);//先遍历重儿子，链头不变
for(int v:tree[u]){
if(v!=father&&v!=wson[u]){
dfs2(v,u,v);//再遍历轻儿子，链头变为轻儿子自身
}
}
}
int lca(int u,int v){//使用HLD找到LCA//也可改为返回ans
while(top[u]!=top[v])
{
if(depth[top[u]]>depth[top[v]]) swap(u,v);//保证v的链头深度较深
//...//这里可以更新dfs序中的[hld_dfn[top[v]],hld_dfn[v]]
v=fa[top[v]];
}
if(depth[u]>depth[v]) swap(u,v);// 保证v比较深
//...//这里可以更新[hld_dfn[u],hld_dfn[v]]
return u;
}
}
void precalc()
{
HLD::dfs1(s,0);
HLD::dfs2(s,0,s);
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<n;i++) {
int x,y;
cin>>x>>y;
HLD::tree[x].push_back(y);
HLD::tree[y].push_back(x);
}
precalc();
while(m--){
int a,b;
cin>>a>>b;
cout<<HLD::lca(a,b)<<endl;
}
}
FHQ treap¶
#include<bits/stdc++.h>
#define int long long
#define N 1145141
using namespace std;
struct node{
int val,size,pri;
int ls,rs;
}tree[N<<1];
int cnt,root;
int newnode(int date)
{
++cnt;
tree[cnt]={date,1,rand(),0,0};
return cnt;
}
void push_up(int now)
{
tree[now].size=tree[tree[now].ls].size+tree[tree[now].rs].size+1;
}
void spilt(int now,int x,int &L,int &R)
{
if(now==0){
L=R=0;return;
}
if(tree[now].val<=x){
L=now;
spilt(tree[now].rs,x,tree[now].rs,R);
}
else{
R=now;
spilt(tree[now].ls,x,L,tree[now].ls);
}
push_up(now);
}
int merge(int L,int R)
{
if(L==0||R==0) return L+R;
if(tree[L].pri>tree[R].pri)
{
tree[L].rs=merge(tree[L].rs,R);
push_up(L);
return L;
}else{
tree[R].ls=merge(L,tree[R].ls);
push_up(R);
return R;
}
}
int serchk(int now,int k)//求第k大数
{
if(tree[tree[now].ls].size+1==k) return tree[now].val;
if(tree[tree[now].ls].size>=k) return serchk(tree[now].ls,k);
else return serchk(tree[now].rs,k-tree[tree[now].ls].size-1);
}
void insert(int date)
{
int id=newnode(date);
int L,R;
spilt(root,date,L,R);
root=merge(merge(L,id),R);
}
void del(int date)
{
int L,p,R;
spilt(root,date,L,R);
spilt(L,date-1,L,p);
p=merge(tree[p].ls,tree[p].rs);
root=merge(merge(L,p),R);
}
int rankk(int date)
{
int L,R;
spilt(root,date-1,L,R);
int re=tree[L].size+1;
root=merge(L,R);
return re;
}
int pre(int date)//找到前趋
{
int L,R;
spilt(root,date-1,L,R);
int re=serchk(L,tree[L].size);
root=merge(L,R);
return re;
}
int nxt(int date)
{
int L,R;
spilt(root,date,L,R);
int re=serchk(R,1);
root=merge(L,R);
return re;
}
signed main()
{
srand(time(0));
int n;
scanf("%lld",&n);
while(n--)
{
int opt,x;
scanf("%lld%lld",&opt,&x);
switch(opt)
{
case 1:insert(x);break;
case 2:del(x);break;
case 3:printf("%lld\n",rankk(x));break;
case 4:printf("%lld\n",serchk(root,x));break;
case 5:printf("%lld\n",pre(x));break;
case 6:printf("%lld\n",nxt(x));break;
}
}
}
逆元¶
扩展欧几里得算法求逆元¶
求解逆元，就相当于求解线性同余方程。因此，可以使用 扩展欧几里得算法 在\(O(\log\min\{a,m\})\)时间内求解逆元。同时，由于逆元对应的线性方程比较特殊，可以适当地简化相应的步骤。
// Extended Euclidean algorithm.
void ex_gcd(int a, int b, int& x, int& y) {
if (!b) {
x = 1;
y = 0;
} else {
ex_gcd(b, a % b, y, x);
y -= a / b * x;
}
}
// Returns the modular inverse of a modulo m.
// Assumes that gcd(a, m) = 1, so the inverse exists.
int inverse(int a, int m) {
int x, y;
ex_gcd(a, m, x, y);
return (x % m + m) % m;
}
这一算法适用于所有逆元存在的情形。
快速幂求逆元¶
这一方法主要适用于模数是素数 \(p\) 的情形．此时，由 费马小定理 可知对于任意 \(a\perp p\) 都有
\[a\cdot a^{p-2} = a^{p-1} \equiv 1 \pmod{p}.\]
根据逆元的唯一性可知，逆元 \(a^{-1}\bmod p\) 就等于 \(a^{p-2}\bmod p\)，因此可以直接使用 快速幂 在 \(O(\log p)\) 时间内计算：
// Binary exponentiation.
int pow(int a, int b, int m) {
long long res = 1, po = a;
for (; b; b >>= 1) {
if (b & 1) res = res * po % m;
po = po * po % m;
}
return res;
}
// Returns the modular inverse of a prime modulo p.
int inverse(int a, int p) { return pow(a, p - 2, p); }
范德蒙德卷积¶
\[\sum_{i=0}^{k}\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}\]
组合意义：从 \(n\) 个一类物品、\(m\) 个二类物品里一共选出 \(k\) 个，按"选了几个一类物品"分类，就是 \(\sum_{i}\binom{n}{i}\binom{m}{k-i}\)；而不管怎么分类，总的选法就是 \(\binom{n+m}{k}\)，两边相等。
语法，STL 记录¶
reverse(a, a + n)可以翻转 \(a\) 的前 \(n\) 个元素（需要<algorithm>）。scanf()返回EOF（即 \(-1\)）时表示输入结束 / 读入失败。low = x & -x取出 \(x\) 最低位的 1（lowbit）；__builtin_ctz(low)返回这个 1 所在的位置（从 0 开始计），常用于状压 dp。map内部按 key 升序排序（红黑树，弱序），遍历写法：
for (auto& [key, val] : mp) {
cout << key << " " << val << "\n";
}