发布日期: 2022-07-26

更新日期: 2023-08-02

文章字数: 4.1k

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表达式

简洁版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];
});

一般情况

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.枚举子矩阵

枚举左下和右上的点，\(O(n^4)\)
枚举上边界和下边界，左右通过某些题的贪心性质搞成线性例：洛谷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] 迷路

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

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

AT3913 XOR Tree

可以把边权化点权

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

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

16.因子的一些等价表示

P3935 Calculating

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

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

若 \(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.反悔型贪心常用技巧

比如什么原价 \(w_i\) ，用优惠券 \(p_i\) ，反悔的做法是新增一个物品价格为 \(w_i-p_i\) 以腾出优惠券
延迟删除：比起去优先队列里找元素删，不如延迟删除，即用个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\) 排序，接下来？

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];

\(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意义下的加法

// 返回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！！

\[ 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';

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);

}