OI tricks

注意：本文不是成品，是动态更新的，可能出现各种小问题什么的

原简介：

平时做题的时候发现的一些技巧，还没有仔细整理

因此本文比较像草稿般的个人总结

1.终极快读（稳定&简单版）（较为麻烦但是还要快的见OI模板-其他）

namespace FastIO
{
	#define gc() readchar()
	#define pc(a) putchar(a)
	#define SIZ (int)(1e6+15)
	char buf1[SIZ],*p1,*p2;
	char readchar()
	{
		if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
		return p1==p2?EOF:*p1++;
	}
	template<typename T>void read(T &k)
	{
		char ch=gc();T x=0,f=1;
		while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
		while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
		k=x*f;
	}
	template<typename T>void write(T k)
	{
		if(k<0){k=-k;pc('-');}
		static T stk[66];T top=0;
		do{stk[top++]=k%10,k/=10;}while(k);
		while(top){pc(stk[--top]+'0');}
	}
}using namespace FastIO;

---

2.区间的平均数问题

例：询问一个区间是否平均数大于 $m$

解法：把原区间每个数减去 $m$ ，这样修改后的区间和若大于等于 $\boldsymbol{0}$ ，则平均数大于 $m$​

（这个很还是好想的，平均数大于 $m$ ，那么和就大于 $m\times$区间长度）

---

3.秦九韶算法

double cal(double x)
{
    double ans=0;
    for(int i=0; i<=n; i++)
        ans=ans*x+a[i];
    return ans;
}

---

4.全局k大值的维护

开一个小根堆，先插入 $k$ 个极小值，这样堆顶就是第 $k$ 大，（最大的在堆底）每次pop()+push()以保证始终是 $k$ 个，如果有重复计算或统计的值要把 $k$ 乘以那个值

---

5.lambda表达式

1. 简洁版cmp

   sort(a+1,a+n+1,[](int x,int y){
       return rk[x] == rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];
   });

2. 一般情况

   auto f=[=](int x)
   {
       // do something...
   };
   // 中括号里面=是传值，&是传地址

---

6.顺反则逆

如果发现 $\boldsymbol{+1}$ 标记的操作要反过来跑，可以考虑改成 $\boldsymbol{-1}$ ，然后正着跑

---

7.枚举二元函数

例如 f(a,b) ，如果有单调性（比如单调递增）且 $a,b$ 的范围可以线性求解的话，

则可以 $a=1 \to n,b=n$ ，随着循环去减 $b$ ，这样就是线性的

例：abc246D

#include<bits/stdc++.h>
using namespace std;
long long f(long long a,long long b)
{
    return (a*a*a + a*a*b + a*b*b + b*b*b);
}
int main()
{
    long long n;
    cin >> n;
    long long x=8e18;
    long long j=1000000;
    for(long long i=0;i<=1000000;i++)
    {
        while(f(i,j)>=n && j>=0)
        {
            x=min(x,f(i,j));
            j--;
        }
    }
    cout << x << '\n';
    return 0;
}

可以优化，变成

#include<bits/stdc++.h>
using namespace std;
long long f(long long a,long long b)
{
    return (a*a*a + a*a*b + a*b*b + b*b*b);
}
int main()
{
    long long n;
    cin >> n;
    long long x=8e18;
    long long i=0,j=1000000;
    while(i<=j)
    {
        long long cf=f(i,j);
        if(cf>=n){x=min(x,cf);j--;}
        else{i++;}
    }
    cout << x << '\n';
    return 0;
}

类似于双指针的写法

---

8.最大值&最小值的转化

$\max z = -\min (-z)$

---

9.枚举子矩阵

1. 枚举左下和右上的点，$O(n^4)$
2. 枚举上边界和下边界，左右通过某些题的贪心性质搞成线性 例：洛谷P1369 $O(n^3)$

---

10.快速计算平方根

$$\begin{aligned} \sqrt{x}&= a+\dfrac{x-a^2}{\sqrt{x}+a} \\&\approx a+\dfrac{x-a^2}{2\times a} \end{aligned}$$

正整数 $a$ 满足 $a^2\le x < (a+1)^2$

---

11.判断有多少个结点可以到达 $n$ 结点

建反图，然后从 $n$ 结点跑 bfs 即可

---

12.找每个结点能到达的点权最小结点

可以把所有的结点按点权升序排序，然后从最小点权的开始，去尝试影响别的结点的答案

这样做是 $O(n\log n)$ 的

---

13.直径两端到直径上一点的最近距离

从 $x$ 端跑个dis数组，答案就是min(dis[u],dis[y]-dis[u])

---

14.有向图路径长度必须恰好t从1到达n的方案数

P4159 [SCOI2009] 迷路

1. 从样例一发现，并且不考虑题目问题，01邻接矩阵相乘就是通过2条边到达节点的方案数
2. 对于非01邻接矩阵，使用拆点

---

15.树上选一条路径，路径上每条边的边权异或x

AT3913 XOR Tree

可以把边权化点权

把每个结点的点权定义为 该结点所有相邻的边的边权异或和

这样就把路径改边权转化为了修改两个端点

---

16.因子的一些等价表示

P3935 Calculating

1. $$\sum_{i=1}^{n}\sum_{d\mid i}1 = \sum_{i=1}^{n}\left\lfloor{\dfrac{n}{ i}}\right\rfloor$$

这个柿子就可以用数论分块来搞了

1. 若 $n = \prod_{i=1}^{s}p_i^{k_i}$

$$\prod_{i=1}^{s}{(k_i+1)}=\sum_{d\mid n}1 = n \text{ 的因数个数}$$

注意是因数个数！不是质因数个数！

---

17.循环改写->前缀和优化

常见于dp，例题：P4099 [HEOI2013]SAO

for(int i=1; i<=n; i++)
	for(int j=i; j<=n; j++)
		dp[i][j];
// 可以转化为以下形式
for(int j=1; j<=n; o++)
	for(int i=1; i<=j; i++)
		dp[i][j];

---

18.乘法转log 防止爆long long

类似于哈希

要记录这样的值，又不想用哈希

$$a\times b \times c$$

可以转化为

$$\log a + \log b + \log c$$

---

19.移项后二分

求下面柿子的最大值

$$\dfrac{\sum a_i}{\sum b_i}$$

可以假设

$$\dfrac{\sum a_i}{\sum b_i} \ge x$$

然后

$$\sum a_i - x \sum b_i \ge 0$$

while(r-l>1e-6)
{
    double mid=(l+r)/2;
    if(ck(mid))l=mid;
    else r=mid;
}

---

20.判正环 —改符号-> 判负环

RT.P2868 [USACO07DEC]Sightseeing Cows G

---

21.数组中下一个相同的数

for(int i=n; i>=1; i--)
{
    nx[i]=first[val[i]];
    first[val[i]]=i;
} // 数组是val[]

---

22.经典n^3枚举矩阵

$O(n^2)$ 枚举上下界，$O(n)$ 处理中间一条

把上界到下界压到一个数上，这样就变成了一行

枚举上界或者下界也是有用的想法

---

23.环上选不相邻序列，权值最大

见P1484&P1792，反悔型贪心，即a-b-c，选b，反悔选a,c（看作一个几点）

---

24.反悔型贪心常用技巧

1. 比如什么原价 $w_i$ ，用优惠券 $p_i$ ，反悔的做法是新增一个物品价格为 $w_i-p_i$ 以腾出优惠券
2. 延迟删除：比起去优先队列里找元素删，不如延迟删除，即用个vis记录是否被删除，然后每次取堆顶的时候判断

---

25.标记优化树状数组的频繁清空操作

详见 link ，其实也叫时间戳优化

适用场景：

给定 $T$ 组数据，每组数据有 $Q$ 个询问，询问给定 $n$ 个数的区间和

数据范围：$T\le 2\times 10^5,~\sum Q \le 2\times 10^5,~n\le 5\times 10^5$

对于每组数据不能直接去清空数组，因为 $T \times n$ 肯定爆炸

考虑维护一个时间戳now，也就是现在是第几组数据

int tree[N],t[N],now=0;
void add(int x,int v)
{
    for(int i=x; i<=n; i+=lowbit(i))
        if(t[i]==now)tree[i]+=v;
        else t[i]=now,tree[i]=v; // tree[i] = 0 + v
}
int sum(int x)
{
    int res=0;
    for(int i=x; i; i-=lowbit(i))
        if(t[i]==now) res+=tree[i];
        else t[i]=now,tree[i]=0; // res+=0
}

---

26.枚举技巧

求柿子的最大值

$$\min(d1[u]+d2[v]+1,d2[u]+d1[v]+1)$$

假设

$$d1[u]+d2[v]\le d1[v]+d2[u] \\d1[u]-d2[u]\le d1[v]-d2[v]$$

然后按 $d1-d2$ 排序，接下来？

---

1. nx[i][j] 表示 $i$ 后面出现的第一个字符 $j$ 的位置

for(int i=0; i<26; i++)
    for(int j=1; j<=n+1; j++)
        nx[i][j]=n+1;
for(int i=0; i<26; i++)
    for(int j=n; j>=1; j--)
        nx[i][j]=(s[j]=='a'+i)?j:nx[i][j+1];

---

1. $x \equiv x_\texttt{十进制下的每个数位的和} \bmod p$

---

29.$a_i \leftarrow a_{i-1}+a_{i+1}-a_i$

等价于交换 $a_i-a_{i-1}$ 和 $a_{i+1}-a_i$

例如

a[3]-a[2]=5
a[4]-a[3]=4

交换以后变成

a[3]-a[2]=4
a[4]-a[3]=5

30.判断两个非最简分数是否相等

struct node {int x,y;};
bool equal(node a,node b)
{
	return a.x*b.y==a.y*b.x;    
}

31.异或=模2意义下的加法

32.

// 返回x符号正负（1或-1）
int sgn(int x){return (x>0)-(x<0);}

---

33.二维限制常见套路

• 枚举一维，维护一维（排序一维，处理一维）

  特例：固定某个 $\min$ ，处理 $\max$ 。

• 转化为平面上的点处理（最小乘积生成树）

• 通过不等式转化为一维问题

  特例：01分数规划 $\frac{a}{b} \ge x \Rightarrow a-bx \ge 0$

---

34.差值不超过 $D$ ，可以记录A-B和B-A，方便转移 [P2592]

---

35.设 $x_i$ 表示最终方案中 $i$ 给 $i+1$ 了多少糖果（如果 $x_i$ 为负，则代表 $i+1$ 给了 $i$ 多少）P2512

---

36.下面这种柿子

$$\sum_{i=1}^{n}|a_i-x|$$

转化为数轴上 $n$ 个点，求距离和最小值

$x$ 取中位数即可

nth_element(a+1,a+(p = (n+1)>>1),a+1+n); // p 是中位数的下标

注意是(n+1)/2！！

---

37.

$$f_{0,0} = 1 \\\\ f_{i,j} = \sum\limits_{1 \le k < i\land S_i-S_k \le M} f_{k,j-1}$$

P2511

前缀和优化一下，即令 $g_i = \sum_{t=i}^{n}f_{t,j}$

这样就可以用 $g_i-g_{k-1}$ 求得这一段的和了。

---

38.两个集求交，如果有交，则有解 CF832C

判断方法：「两个下界 $l_1,l_2$ 的 $\max$ 」小于等于「两个上界 $r_1,r_2$ 的 $\min$ 」

---

39.无权树上任意一个节点，与它距离最远的节点一定是直径的某个端点

---

40.线段树查询答案需要合并左右的，可以这么写

见CF712E

P query(int nl,int nr,int l,int r,int at)
{
    if(nl <= l && r <= nr) return {tr[at].f, tr[at].g};
    int mid = (l+r) >> 1;
    if(nr <= mid) return query(nl,nr,l,mid,ls(at));
    else if(nl > mid) return query(nl,nr,mid+1,r,rs(at));
    P res1=query(nl,nr,l,mid,ls(at)), res2=query(nl,nr,mid+1,r,rs(at));
    return {res1.F * res2.F / (1 - (1 - res2.F) * (1 - res1.S)),
            res1.S * res2.S / (1 - (1 - res2.F) * (1 - res1.S))};
}

---

41.UOJ21 枚举取值，用调和级数证明复杂度

注意到 $\left\lfloor\frac{a_i}{T}\right\rfloor$ 只有至多 $\left\lfloor\frac{\max\{a_i\}}{T}\right\rfloor$ 种取值，即

$$\forall a_i \in [kT-T,kT-1],~\left\lfloor\frac{a_i}{T}\right\rfloor=k-1\quad 1 \le k \le \left\lfloor\frac{\max\{a_i\}}{T}\right\rfloor \land k \in \mathbb{N}$$

比如 $\forall a_i \in [T,2T-1],~\left\lfloor\frac{a_i}{T}\right\rfloor=1$ 。

暴力处理所有的区间 $[kT-T,kT-1]$ ，然后看看每一段区间里面有多少个 $a_i$ 。

---

42.不超过 $x$ 的素数有 $O\left(\frac{x}{\ln x}\right)$ 个

---

43.期望的线性性质（ $E(A+B) = E(A) + E(B)$ ，即和的期望等于期望的和）

---

44.路径上点权的最大值

可以转化为边权的最大值，如下

$$w(u,v) = \max\{a_u,a_v\}$$

---

45.根据 border 定理，一个串有长度为 $k$ 的周期当且仅当它有长为 $d-k$ 的 border 。

$O(n^2)$ 预处理所有子串的border （P4302）

void KMP(int t)
{
    int *fail = g[t]+t-1; char *s = str+t-1;
    // cout << (s+1) << '\n';
    fail[1]=0;
    for(int i=2,j=0; i<=n-t+1; i++)
    {
        while(j && s[j+1] != s[i]) j=fail[j];
        if(s[j+1] == s[i]) ++j; fail[i]=j;
    }
}

// 然后主函数加入下面这段
cin >> (str+1); n=strlen(str+1);
for(int i=1; i<=n; i++) KMP(i);
// g[i][j]就是[i,j]的最长border

---

46.稠密图期望 $O(n)$ 确定连通块个数（直接bfs是 $O(n^2)$ 的）

P3452 这题是建了个反图，所以边是注释里那个“可以访问”

不难发现，此时的连通块数量一定不会很多

因此在拓展一个连通分量的时候，无需再考虑已经在连通分量里的点。

这个东西可以用并查集维护。

具体地， f[x] 表示的是编号大于 $x$ 的点中第一个未被访问的点

有点像那个线性区间推平的题目 -> 洛谷P2391 白雪皑皑 题解

因为 $G^{\prime}$ 是稠密图，所以时间复杂度为期望 $O(n)$

void bfs(int st)
{
    q.push(st); val[++cur]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop(); ++tim; f[u]=find(u+1);
        for(int i=head[u]; i; i=e[i].next) used[e[i].v]=tim;
        for(int i=find(1); i<=n; i=find(++i))
            if(used[i] != tim) // 可以访问
                ++val[cur], f[i]=find(i+1), q.push(i);
    }
}

// 主函数加上这个
init(n+1); // 一定要 n+1 ！！！否则++i可能会挂！！
for(int i=1; i<=n; i = find(++i)) bfs(i);
cout << cur << '\n';

1. P2272

• Tarjan 缩点后的点的排列顺序是逆拓扑序

• 拓扑序下的判重边（used数组）（计数性dp需要判重边！！！）

for(int u=scnt; u; u--)
{
    if(!f[u]) {f[u] = sz[u]; g[u] = 1;}
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(used[v] == u) continue; // here
        used[v] = u;
        if(f[u] + sz[v] > f[v])
        {
            f[v] = f[u] + sz[v]; g[v] = g[u];
        }else if(f[u] + sz[v] == f[v])
        { add(g[v], g[u]); }
    }
}

看到置换，除了想到群论等等，还要想到

• 置换满足双射的性质，会不会和二分图有关呢？ P1963

48.线段树维护欧拉序 见 P2056

struct node
{
    int l,r,lc,rc,ld,rd,ans;
    node (int v = 0) : l(0), r(0), lc(-INF), rc(-INF), ld(-INF), rd(-INF), ans(-INF)
    {
        switch(v)
        {
            case -1: r = 1; break;
            case -2: l = 1; break;
            case 1: lc=rc=ld=rd=0; break;
        }
    }
}tr[N * 12]; // 4 * 3n

49.对于概率型dp，可能会出现概率过小导致 double 都存不下的情况

这种情况可以考虑收缩dp的范围，去掉一些无用的状态

CF464D

由几何分布，概率为 $p$ 的时间期望 $\frac{1}{p}$ 次才能成功，则对于一个特定的装备

它从第 $j$ 级升到第 $j+1$ 级的概率为 $\frac{1}{k(j+1)}$ ，因此其期望的次数为 $k(j+1)$ 。

则从 $1$ 级升到 $m$ 级的期望次数为 $2k + 3k + \cdots + mk \sim \frac{1}{2}m^2k < n$

则有 $m < \sqrt{\dfrac{2n}{k}}$ ，即期望等级大约在 $500$ 左右。

事实上，超过 $1000$ 在 double 中已经存不了了，因此不会对答案产生影响。

50.树剖维护边权化点权，要注意以下几个小区别 详见 P4180

代码里的 S 就是 S[v] = S[u] + e[i].w ，用于找父亲连儿子那条边的边权。

void dfs2(int u,int ftop)
{
    top[u] = ftop; id[u] = ++idx; val[idx] = S[u] - S[fa[u]]; // 区别1
    if(!son[u]) return; dfs2(son[u], ftop);
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(v != fa[u] && v != son[u]) dfs2(v,v);
    }
}
pii query(int nl,int nr,int l,int r,int at)
{
    if(nr < l || r < nl) return {-INF,-INF}; // 区别2，因为 id[x]+1 可能大于 id[y]
    if(nl <= l && r <= nr) return {tr[at].mx, tr[at].smx};
    int mid = (l + r) >> 1;
    if(nl > mid) return query(nl,nr,mid+1,r,rs(at));
    if(nr <= mid) return query(nl,nr,l,mid,ls(at));
    pii r1=query(nl,nr,l,mid,ls(at)), r2=query(nl,nr,mid+1,r,rs(at));
    return {max(r1.Fi, r2.Fi), getsmx(r1.Fi, r1.Se, r2.Fi, r2.Se)};
}
int qRange(int x,int y,int z)
{
    int res = -INF; pii r;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        r = query(id[top[x]], id[x], 1,n,1);
        up(res, (r.Fi == z) ? r.Se : r.Fi);
        x = fa[top[x]];
    }
    dep[x] > dep[y] ? swap(x,y) : void(0);
    r = query(id[x]+1, id[y], 1,n,1); // 区别3
    return max(res, (r.Fi == z) ? r.Se : r.Fi);

}

51.计算 $a\times \frac{b}{c}$ 的时候，可以先计算 $\frac{a}{d}\times b\times \frac{d}{c}$ ，其中 $d = \gcd(a,c)$ 。可以防止溢出

或者开 __int128 也行，但是 CodeForces 不支持。

1. uoj340

多组询问 + 行向量乘矩阵， 可以预处理矩阵的 $2^k$ 次幂，然后直接像快速幂一样乘就好了

$M^3\log n \to M^2\log n$ ，快在了不用拿 $M\times M$ 的矩阵相乘。原理是矩阵具有结合律。

1. 初始状态确定时顺推，终止状态确定时逆推。

1. $n$ 个点之间两两相连，可以建一个虚点（地铁站），然后用它和其他所有点连双向边

   复杂度需要根据这个两两相连的数量分析。