TriCk

KSCD_ · 2024-05-26 14:46:53 · 个人记录

• 24.05.11 枚举 1 到 n 中每个数所有在 n 以内的倍数，复杂度为 O(n\ln n)

• 24.05.26 枚举子集：

  for(int T=S;T;T=(T-1)&S)

  总时间复杂度 O(3^n).

• 24.05.30 括号序列类问题

转化成对应前缀和的一段折线考虑。（/bx @Iceturky）

• 24.06.01 无逆元时要从总乘积中除掉一项

维护前后缀乘积（/bx @Iceturky）

• 24.06.17 !!f int 强转 bool

• 24.06.20 序列问题有后效性，倒序处理 f_i 为 i 到 n 的答案并乘上系数（/bx @Aimtpyim）

• 24.07.17 序列问题可以转成前缀和，之后区间操作可能转化为两点操作

• 24.07.29 两种不同的暴力拼起来可能就是根号分治，参数 B 一定要让各部分复杂度相近，需要考虑到常数因素（SDSC Day5T2）

• 24.10.17 线性求逆元

求出 inv_i\times i \equiv 1\pmod p，考虑计算 p=ri+t,t<i，则 ri\equiv -t,i\equiv-\frac tr,inv_i\equiv -\frac rt\pmod p，所以 inv_i=(p-\lfloor\frac pi\rfloor)inv_{p\bmod i}\bmod p。

• 25.02.06 字典序最优问题

使用可持久化值域线段树维护哈希值，从而快速求出最长公共前后缀，进行比较和更新。

• 25.02.17 点边容斥

当树上每个连通块作为根计算答案时，可用每个点为根计算一遍并累加，再减去以所有边连接的两个点合成大点作为个根的答案，这样每个连通块的贡献只有 1。

• 25.04.29 整点凸包

当凸包的横纵坐标均为 [0,n] 内的整数时，凸包的点数为 O(n^{\frac23})。

• 25.05.01 竞赛图相关

竞赛图强连通缩点后的 DAG 呈链状, 前面的所有点向后面的所有点连边；

竞赛图存在哈密顿回路和哈密顿路径。

• 25.05.04 矩阵快速幂

多次询问时可预处理转移矩阵的 2^k 次方，每次询问做 \log n 次向量乘矩阵，复杂度为 O(k^3\log n+qk^2\log n)。

• 25.09.26 排列字典序

若要最小化排列 p 的字典序，可考虑其逆排列 q（p_{q_i}=i,q_{p_i}=i），并求出倒序字典序最大的 q，再还原回 p 即为答案。

证明考虑首先最小化 p_1，也就是 q 中 1 的位置，以此类推。则 q 从后往前考虑，只能填 1 时再填 1，以此类推。

• 25.11.03 线段树二分

实在困难，记一下。代码选自 P11210。

int getp(int u,int l,int r,int L)
{
    if(r<L) return n+1;
    if(l>=L)
    {
        if(wy[u]<L) return n+1;
        if(l==r) return l;
    }
    int rl=getp(Lc,L);
    return rl==n+1?getp(Rc,L):rl;
}

• 25.11.14 线性基求后继（异或上 x）

  int nxt(int lim,int x)
  {
  int y=x,s=0; ini();
  vector <int> tv;
  for(int i=0;i<=30;i++) if(a[i]) tv.pb(a[i]),s++;
  for(int i=s-1;i>=0;i--) if((y^tv[i])>y) y^=tv[i];
  if(y<lim) return inf;
  for(int i=s-1;i>=0;i--) if((y^tv[i])>=lim) y^=tv[i];
  return y;
  }

• 25.12.02

  [&](int i,int j)->bool{return a[i].x[d]<a[j].x[d];}

• 25.12.12 正则二分图完美匹配

每次随机选一个左部未匹配点 x（可初始随机一个排列）,再随机其连着的某点 y 求增广路，期望复杂度 \mathcal O(n\ln n)。

• 25.12.21 二分图相关

二分图最大匹配数与最小点覆盖数相等，最大独立集为最小点覆盖的补集。

构造一组最小点覆盖，可在最大匹配 M 的基础上，找到所有左部未匹配点通过交错路不可达的左部点和可达的右部点，即为一组最小点覆盖。在最大匹配的网络流图上即残量网络中 S 不可达的左部点和可达的右部点。