Skip to main content

备战 NOIP2016 - 知识总结

· 26 min read

要复赛了! 要退役了! 快总结一下好了...
(排名不分先后, 慢慢添加内容)

  • 使用 ! 标记的为重要内容
  • 使用 * 标记的为(应该)用不到的内容
  • 如有错误, 请联系我, 感谢

数据结构

  • 链表 表达式树 !线段树 Trie 树 HASH 表

!栈

int Stack[N], top = 0;
void push (int x) {
Stack[top++] = x;
}
int front () {
return Stack[--top];
}
void pop () {
top--;
}
bool empty () {
return top == 0;
}

#include<stack>
std::stack<int>s;
void s::push(int);
int s::top();
void s::pop();
bool s::empty();

!队列

int Queue[N], head = 0, tail = 0;
void push (int x) {
Queue[head++] = x;
if (head == N) head = 0;
}
int front () {
return Queue[tail];
}
void pop () {
tail++;
if (tail == N) tail = 0;
}
bool empty () {
return head > tail ? head-tail : head+N-tail;
}

#include<queue>
std::queue<int>que;
void que::push(int);
int que::front();
void que::pop();
bool que::empty();

!堆

堆分大根堆和小根堆, 可以高效的维护集合中的最值, 支持动态修改, 下面是实现的最好的例子

#include<queue>
std::priority_queue<int>que;
void que::push(int);
int que::top();
void que::pop();
bool que::empty();

二叉搜索树

可选: Splay, Treap, 红黑树, 以及

#include<set>
#include<map>

STL 内部是写的鲁棒性极高的红黑树

!树状数组

树状数组好写好用, 常见的无法解决的问题是区间最值

很重要的事:
关于 lowbit() 的正确性, 理性的证明不重要, 你可以尝试模拟计算过程来感性地认知
树状数组不能维护从 0 开始的区间, 有些时候你需要加 1 来使区间左端点不是 0


使用树状数组的三个阶段:

改点求段

给出若干点修改区间查询, 使用树状数组维护

int bit1[N];
int lowbit (int x) {return x&-x;}
void add1 (p, x) {
while (p > N) {
bit1[p] += x;
p += lowbit(x);
}
}
int sum1 (int r) {
int ret = 0;
while (r) {
ret += bit1[r];
r -= lowbit(r);
}
}
int query1 (int l, int r) {return sum1(r) - sum1(l-1);}

改段求点

给出若干区间修改点查询, 使用树状数组维护

int bit2[N];
void add2 (int r, int x) {
while (r) {
bit2[r] += x;
r -= lowbit(r);
}
}
void add2 (int l, int r, int x) {
add(r, x);
add(l-1, -x);
}
int sum2 (int p) {
int ret = 0;
while (p < N) {
ret += bit2[p];
p += lowbit(p);
}
}
int query2 (int p) {return sum2(p);}

改段求段

给出若干区间修改区间查询, 使用树状数组维护

这个操作需要一前两个为基础
考虑 l 固定的修改与查询(即前缀):

  • 我们使用 bit1 存储的数据会在 r 更大的查询中被用到, 表示它前面的区间修改的总和(即前缀和)
  • 我们使用 bit2 存储的数据会在 r 更小的查新中被用到, 表示它前面区间中每个点的修改

推广即可

void add3 (int l, int r, int x) {
add1(r, x*(r-l));
add1(l-1, -x*(l-1));
add2(r, x);
add2(l-1, -x);
}
int query3 (int l, int r) {return sum1(r) - sum1(l-1) + sum2(r) * r - sum2(l-1) * (l-1);}

三种图的存储方式

邻接矩阵

NONE

下面的内容来自 Coolkid这篇博客
明显比我良心

一般跑 Floyd 的时候这么存
设 G[i][j] 表示 i 到 j 有一条边边权为 G[i][j] 否则 G[i][j] = INF

!邻接表

struct E{
int to, v;
};
vector <E> G[N];

下面的内容来自 Coolkid这篇博客
明显比我良心

刘汝佳推荐的存法, 用一个数组 edges 存边集, G[i][j] 存以 i 为起点的第 j 条边的编号

struct Edge{
int from,to,dist;
Edge(int f=0,int t=0,int d=0){
from=f;to=t;dist=d;
}
};
vector<Edge> edges;
vector<int> G[MAXN];

void addedge(int from,int to,int dist){
edges.push_back(Edge(from,to,dist));
int m=edges.size();
G[from].push_back(m-1);
}//加边

//遍历以u为起点的所有边
void work(int u){
for(int i=0;i<G[u].size();i++){
//do something
}
}

前向星

struct E{
int to, v, nex;
};
vector <E> G;
int head[N];

下面的内容来自 Coolkid这篇博客
明显比我良心

struct Edge{
int to,dist,next;
}edges[MAXM];//边
int head[MAXN],cnt=0;
//加边
void addedge(int from,int to,int dist){
edges[cnt].to=to;
edges[cnt].dist=dist;
edges[cnt].next=head[from];
head[from]=cnt++;
}

注意:无向图时应调用两遍 addedge
上述的 head 初始值为 -1 因此遍历以 u 为 from 的所有边的时候可以采用下面的代码

for(int i=head[u];~i;i=edges[i].next){
//do something
}

!并查集

int fa[N];
int father (int x) {return x == fa[x] ? x : fa[x]=father(fa[x]);}
void Union(int x, int y){fa[father(x)] = father(y);}

并查集可以用来判断图的连通性, 还可以用来做一些奇怪的事情, 比如[NOIP2010]关押罪犯可以用并查集造点

图论

在此板块 %%% Coolkid dalao

拓扑序

bool vis[N];
int tp[N], top = 0;
void tuopu (int p) {
if (vis[p]) return;
for (int i = head[p]; ~i; i = G[i].nex) tuopu (G[i].to);
tp[top++] = p;
}

我在网络流中也用到了这个算法

下面的内容来自 Coolkid这篇博客
明显比我良心

求有向图的拓扑序, 以及判断是否存在有向环

int c[MAXN];
int topo[MAXN],t=n;
bool dfs(int u){
c[u]=-1;//-1表示灰色节点即在系统栈内
for(int i=head[u];~i;i=edges[i].next){
int v=edges[i].to;
if(~c[v]) return false;//存在有向环
else if(!c[v]&&!dfs(v)) return false;
}
c[u]=1;topo[t--]=u;
return true;
}

bool TopoSort(){
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) if(!c[i] && !dfs(i)) return false;
return true;
}//拓扑序存在数组topo中

!最小生成树

常用的最小生成树算法有两个 Kruscal 与 Prim, Kruscal 较为好写

下面的内容来自 Coolkid这篇博客
明显比我良心

Kruscal 的算法基本思想就是贪心, 然后用并查集去维护
稀疏图的情况下 Kruscal 跑的飞快

int fa[MAXN];
void initUFS(){
for(int i=1;i<=n;i++) fa[i]=i;
}
int getfather(int x){
return fa[x]==x?x:fa[x]=getfather(fa[x]);
}
//UFS
int Chosen[MAXN];
void Kruscal(){
initUFS();
memset(Chosen,0,sizeof(Chosen));
sort(edges,edges+cnt);//将边按照从小到大的顺序排序
for(int i=0;i<cnt;i++){
int fax=getfather(edges[i].from);
int fay=getfather(edges[i].to);
if(fax==fay) continue;//已经在同一个联通块中
//若不在同一个联通块中,加边合并
fa[fax]=fay;//合并
Chosen[i]=1;//加边
}
}

讲道理这之后应该还有一个 Prim 算法
但是我并没有用过, 而且两个算法作用几乎一样, 并且大部分题目都是给的稀疏图, 因此 Kruscal 就完全足够了

!最短路

有多种算法: Bellman-Ford, Dijkstra, Floyd-Warshall (全源最短路)
常用 SPFA(special fast), 是对 Bellman-Ford 的队列优化版本

queue <int> que;
bool inque[N];
int v[N];
void spfa (int s) {
for (int i = 0; i < N; i++) v[i] = INF;
memset (inque, 0, sizeof(inque));
while (!que.empty()) que.pop();
que.push(s);
inque[s] = 1;
v[s] = 0;
while (!que.empty()) {
int now = que.front(); que.pop();
inque[now] = 0;
for (int i = head[now]; i != -1; i = G[i].nex) if( v[now] + G[i].v < v[G[i].to]){
v[G[i].to] = v[now] + G[i].v;
if (inque[G[i].to]) continue;
que.push(G[i].to);
inque[G[i].to] = 1;
}
}
}

下面的内容来自 Coolkid这篇博客
明显比我良心

一般来说单源最短路最常用的就是以下两种算法
以下存图方式均为前向星

SPFA

一般来说有负权环时用 SFPA。

queue<int> q;
int d[MAXN];
int cnt[MAXN];
int inq[MAXN];

int SFPA(int S,int T){
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++) d[i]=INF;
d[S]=0;
q.push(S);inq[S]=1;cnt[S]++;
while(!q.empty()){
int u=q.front();q.pop();inq[u]=0;
for(int i=head[u];~i;i=edges[i].next){
int v=edges[i].to;
if(d[v]>d[u]+edges[i].dist){
d[v]=d[u]+edges[i].dist;
if(!inq[v]){
q.push(v);inq[v]=1;
if(++cnt[v]>n) return -1;//存在负权环
}
}
}
}
}

Dijkstra

一般来说稀疏图用 Dijkstra
讲道理一般不用 Floyd 的都用 Dijkstra

struct Node{
int d,u;
bool operator < (const Node &rhs) const{
return d>rhs.d;
}
}Hp[MAXM];
int sz=0;

int d[MAXN];
bool done[MAXN];

int Dijsktra(int S,int T){
memset(done,false,sizeof(done));
for(int i=1;i<=n;i++) d[i]=INF;
d[S]=0;
Hp[sz++]=(Node){0,S};
while(sz){
pop_heap(Hp,Hp+sz);sz--;
int u=Hp[sz].u;
if(done[u]) continue;
done[u]=true;
for(int i=head[u];~i;i=edges[i].nxt)if(!vis[i]){
Edge &e=edges[i];
if(d[e.to]>d[u]+e.dist){//松弛
pre[e.to]=i;//记录路径
d[e.to]=d[u]+e.dist;
Hp[sz++]=(Node){d[e.to],e.to};
push_heap(Hp,Hp+sz);
}
}
}
return d[T];
}
最短路径的输出

存储: 定义一个 pre 数组然后在松弛操作处进行更新即可, 具体代码见 Dijkstra
输出: 倒序输出, 从 to 开始一直往前找, 直到找到 from 为止

void printpath(int from,int to){
int u=to;
while(from!=u){
u=edges[pre[u]].from;
printf("from:%d to:%d\n",u,edges[pre[u]].to);
}
}

注意这里输出的路径是倒序的, 如果要正序输出, 将路径暂时存储到栈中即可

全源最短路

Dijkstra SPFA

如果图是稀疏图的话, 对每个节点跑一边单源最短路即可得到全源最短路

Floyd

三重 for 循环

void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i]k]+d[k][j];//松弛
}

差分约束

差分约束系统: 不等式组中每个不等式只含有一个变量

差分约束可以经过转化, 使用最短路算法求解

对于每个不等式, 可以构造出一条边

  • 不等号包含等号(大于等于, 小于等于)时, 边权为 0
  • 不等号不包含等号(大于, 小于)时, 边权为 1

即可得到一张图

二分图染色

下面的内容来自 Coolkid这篇博客
明显比我良心

二分图就是对于一张无向图可以分成两个点集使得两个点的集合内没有边相连
我们可以利用二分图染色进行二分图的判断, 即把两个集合的点分别进行染色, 如果出现冲突, 那就不是二分图, 否则为二分图
下面代码中 col 初始值为 0 表示未被访问, 1 和 -1 表示两种相反的颜色

int col[MAXN];
bool Color(int wanted,int u){
col[u]=wanted;
for(int i=head[u];~i;i=edges[i].next){
int v=edges[i].to;
if(col[v]==c) return false;
if(col[v]==0&&!Color(-wanted,v)) return false;
}
return true;
}

欧拉道路/回路

下面的内容来自 Coolkid这篇博客
明显比我良心

欧拉道路

对于一张图可以从一个点出发, 遍历整张图的, 且条道路都只访问一遍的路径称为欧拉道路
对于无向图的欧拉道路

除起点和终点外其他节点的“进出”次数应该是相等的,换句话说,除起点和终点外,其他点的度数(degree)应该是偶数。
如果一个无向图是连通的,且最多只有两个奇点,则一定存在欧拉道路。如果有两个奇点,则必须从其中一个奇点出发,另一个奇点终止。

以上引自刘汝佳入门经典

void Euler(int u){
for(int v=0;v<n;v++) if(G[u][v]&&!vis[u][v]){
vis[u][v]=vis[v][u]=1;
Euler(v);
printf("%d %d\n",u,v);
}
}

对于有向图来说把上面的 vis[u][v] = vis[v][u] = 1 改为 vis[u][v] = 1 即可

欧拉回路

欧拉回路就是在欧拉道路遍历完所有边之后, 在回到起点本身

欧拉回路中如果奇点不存在,则可以从任意点出发,最终一定会回到该点。

强连通分量

下面的内容来自 Coolkid这篇博客
明显比我良心

强连通分量简单说就是在有向图中一个点经过若干个其他点再回到本身的一个点集

Tarjan 的思想就是用一个 dfs-clock 对每个点进行遍历, 找到自己可以到达的 dfs-clock 最小的值的节点

stack<int> S;
int DFN[MAXN],LOW[MAXN],inS[MAXN];
vector<int> G;
int sccno;

void Tarjan(int u){
DFN[u]=LOW[u]=++T;
S.push(u);
inS[u]=true;

for(int i=head[u];~i;i=edges[i].next){
int v=edges[i].to;
if(!DFN[v]){
Tarjan(v);
LOW[u]=min(LOW[u],LOW[v]);
}else if(inS[v]) LOW[u]=min(LOW[u],DFN[v]);
}
if(DFN[u]==LOW[u]){
int x;
while(x!=u){
x=S.top();S.pop();inS[x]=false;
G[sccno].push_back(x);
}
sccno++;
}
}

还有一种算法是 Kosaraju 算法但是它的常数要比 Tarjan 大, 所以并没有什么卵用

*网络流

写了两篇博客: 浅谈预流推进网络流算法 再谈预流推进-更快算法

二分图的最大匹配

下面的内容来自 Coolkid这篇博客
明显比我良心

讲道理这里应该有两种方法, 一种是匈牙利算法, 一种是最大流算法
但是我并不会匈牙利, 因此这里只讨论最大流求二分图的最大匹配

最大流求二分图的最大匹配

大致思路是对于一个二分图, 我们把二分图的边从一个点集 V1 指向另一个 V2, 流量设为 1, 之后建立一个超级源点 S 指向 V1 的所有节点, 流量设为 1, 设一个超级汇点 T 使 V2 所有的节点都指向汇点, 流量设为 1
之后跑一遍最大流 Dinic

例题

请前往 Coolkid dalao 的博客来查看

贪心

贪心算法的正确性常用临位交换法证明, 简单说就是将贪心方案中的任意两个元素交换位置之后与之前的方案进行对比, 其结果能代表整个贪心方案的正确性(前提是你的证明过程是正确的)

暴力

  • 模拟 枚举 搜索 剪枝 *开关问题 分块

离散化

当数据量小数字却很大时(例如[NOIP2013]火柴排队), 我们可以使用离散化
离散化就是保留数据之间的相对关系(大小关系)而忽略数据本身的数值大小, 没有什么具体代码

分治

  • 归并排序 *树上分治(重心分解)

!快速排序

#include<algorithm>
std::sort(a, a + n);

!二分查找/答案

外层内容相差无几, 注意区间开闭问题, 挂了无数次, 请教 Coolkid

int l = L, r = R, mid;
while (l < r) {
mid = (l + r) / 2;
if (judge(mid)) {
/*---*/
} else {
/*---*/
}
}

字符串

  • HASH

*Manacher

这个算法可以很快的计算出回文子串的长度

void Manacher (char *s, int *length) {
memset (length, 0, sizeof(length));
for (int i = 0; i < strlen(s); i++) {
for (int &j = length[i]; i-j >= 0 && i+j < strlen(s) && s[i-j-1] == s[i+j+1]; j++);
for (int j = length[i]; j > 0; j--) length[i+j] = max(length[i+j], length[i-j]);
}
}

计算得出的 length[] 数组含义如下:
当 length[i] == j 时, s[i] 前面 j 个字符与后面 j 个字符形成回文串

*KMP

字符串匹配算法, 效率很高, 不一定考

void init_kmp (int *last, char *s) {
memset (last, -1, sizeof(last));
for (int i = 1; i < strlen(s); i++) {
int &now = last[i]; now = last[i-1];
while ((~last[now]) && s[last[now]+1] != s[i]) now = last[now];
if (last[now] || s[last[now]+1] == s[i]) now++;
}

int kmp (char *t, char *s, int *last) {
int ret = 0;
for (int i = 0, j = 0; j < strlen(t); i++, j++) {
if (i == strlen(s) ret++, i = last[i-1]+1;
while (i>0 && s[i]!=t[i]) i = last[i-1]+1;
if(i == 0 && s[i] != t[j]) i--;
}
return ret;
}

*AC 自动机

只说一句话: KMP + Trie = AC 自动机

数论

在此板块 %%% Coolkid dalao

  • !二项式定理 加法原理 乘法原理 基本计数问题 *期望与概率 *矩阵乘法 *矩阵快速幂

!斐波那契数列

大部分数学题中会用到, 如果有一道数学题, 你想打表, 最好看一看打出来的表和斐波那契数列有没有关系, 别问我为什么, 问 Coolkid

!素数测试

其实有更快的算法, 但是貌似用不到

bool is_prime (int x) {
if (x < 2) return 0;
if (x == 2) return 1;
for (int i = sqrt(x); i > 1; i--) if (x % i == 0) return 0;
return 1;
}

!素数筛法

这里提到的算法叫做埃氏筛法, 效率比较特别: O(nloglogn), 打素数表专用

bool prime[N];
void sieve () {
fill(prime, prime+N, 1);
prime[0] = prime[1] = 0;
for (int i = 2; i < N; i++) if (prime[i])
for (int j = 2; i * j < N; j++) prime[i*j] = 0;
}

下面的内容来自 Coolkid这篇博客
明显比我良心

void sieve(int n){
int m=sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++)
for(int j=i*i;j<=n;j+=i) vis[j]=1;
}//筛素数
void GetPrimeTable(int n){
sieve(n);
int c=0;
for(int i=2;i<=n;i++) if(!vis[i]) prime[c++] = i;
}//把素数全部放在prime数组里面

!欧几里得与扩展欧几里得

实在重要, 不言而喻

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);}
int exgcd (int a, int b, int &d, int &x, int &y) {//d 是 gcd(a, b)
if (!b) {d = a; x = 1; y = 0;}
else {exgcd(b, a%b, d, y, x); y -= x * (a / b);}
}

下面的内容来自 Coolkid这篇博客
明显比我良心

求解方程 ax+by=gcd(a,b)的一组解,并且使|x|+|y|的值最小

int gcd(int a,int b){
return b==0? a:gcd(b,a%b);
}//递归实现

int GCD(int a,int b){
int r=b%a;
while(r){
b=a;
a=r;
r=b%a;
}
return a;
}//非递归实现
void exgcd(int a,int b,int &d,int &x,int &y){//注意d,x,y均为引用
if(!b){ d=a;x=1;y=0; }
else{
exgcd(b,a%b,d,y,x);
y-=(a/b)*x;
}
}

!唯一分解定理

每个合数都可以唯一的分解为多个质数的积

void wyfj (int *prime, int *num, int x) {
memset (num, 0, sizeof(num));
for (int i = 0; x; i++)
while (x % prime[i] == 0) {
num[i]++;
x/=prime[i];
}
}

上面的函数(貌似)可以求出分解后的质数, 要求传入质数表

下面的内容来自 Coolkid这篇博客
明显比我良心

一个数可以唯一分为几个不同质数的的乘积

void Divide(int n){
for(int i=2;i<=n;i++){
while(n%i==0){
a[i]++;
n/=i;
}
}
}//表示n=i^a[i]

!快速幂

同样是数学基础算法

int mod (int a, int b, int c) {
int ret = 1;
while (b) {
if (b & 1) ret = ret * a % c;
a = a * a % c;
b >>= 1;
}
retrun ret;
}

下面的内容来自 Coolkid这篇博客
明显比我良心

求 a ^ p mod n 的值

long long quickpow(long long a,long long p,long long n){//a,p,n含义如上
long long res=1;
while(p){
if(p&1) res=res*a%n;
a=a*a%n;
p>>=1;
}
return res;
}

欧拉函数

下面的内容来自 Coolkid这篇博客
明显比我良心

int Euler_Phi(int n){
int ans=n;
for(int i=2;i<=n;i++) if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
if(n>1) ans=ans/n*(n-1);
return ans;
}//求单个数的欧拉函数
//筛法求欧拉函数表
void Phi_Table(int n){
memset(phi,0,sizeof(phi));
phi[1]=1;
for(int i=2;i<=n;i++) if(!phi[i])
for(int j=i;j<=n;j+=i){
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}

!高精度

模拟人的算数过程, 下面的模板仅供参考, 不是完全正确的代码

struct Bign{
static const int N = 1000,M = 1;
static const int powm = 10;// powm = pow(10,M);
int a[N];
// bool_type;
bool operator < (const Bign &num) const {
if(a[0] != num.a[0])return a[0] < num.a[0];
const int *b = num.a;
int th = a[0];
while(a[th] == b[th] && th > 0) th--;
return a[th] < b[th];
}
bool operator > (const Bign &num) const {return num < *this;}
bool operator <= (const Bign &num) const {return !(num < *this);}
bool operator >= (const Bign &num) const {return !(num > *this);}
bool operator != (const Bign &num) const {return num < *this || num > *this;}
bool operator == (const Bign &num) const {return !(num != *this);}
// =_type;
Bign operator = (int num){
memset(a,0,sizeof(a));
while(num){
a[++a[0]] = num % powm;
num /= powm;
}
return *this;
}
Bign (int num = 0){*this = num;}
// +_type;
Bign operator + (const Bign &num) const {
Bign ret = 1;
const int *b = num.a;
int *c = ret.a, buf = 0;
for(int &i = c[0]; i <= max(a[0], b[0]) || buf; i++){
c[i] = a[i] + b[i] + buf;
buf = c[i] / powm;
c[i] %= powm;
}c[0]--;
return ret;
}Bign operator += (const Bign &num) const {return *this + num;}

Bign operator + (const int num) const {
Bign ret = num;
return *this + ret;
}Bign operator += (const int num) const {return *this + num;}
// -_type;
Bign operator - (const Bign &num) const {
if(a < num.a) return num - *this;
Bign ret = 1;
const int *b = num.a;
int *c = ret.a, buf = 0;
for(int &i = c[0]; i < a[0] || a[i] + buf; i++){
c[i] = a[i] + powm - b[i] + buf;
buf = c[i] / powm - 1;
c[i] %= powm;
}
while((!c[c[0]])&&c[0]>0)c[0]--;
return ret;
}Bign operator -= (const Bign &num) const {return *this - num;}

Bign operator - (const int num) const {
Bign ret = num;
return *this - ret;
}Bign operator -= (const int num) const {return *this - num;}
// *_type;
Bign operator * (const Bign &num) const {
Bign ret;
const int *b = num.a;
int *c = ret.a;
for(int i = 1; i <= b[0]; i++){
int buf = 0;
for(int j = 1; j <= a[0] || buf; j++){
c[i+j-1] += a[j] * b[i] + buf;
buf = c[i+j-1] / powm;
c[i+j-1] %= powm;
}
}c[0] = a[0] + b[0];
if(!c[c[0]]) c[0]--;
return ret;
}Bign operator *= (const Bign &num) const {return *this * num;}

Bign operator * (const int num) const {
Bign ret = num;
return *this * ret;
}Bign operator *= (const int num) const {return *this * num;}
// /_type;
Bign operator / (const int num) const {
Bign ret = 1;
int *c = ret.a, buf = 0;
for(int i = a[0]; i > 0; i--){
buf = buf * powm + a[i];
c[i] = buf / num;
buf %= num;
}c[0] = a[0];
for(int &i = c[0]; !c[i]; i--);
buf = 0;
for(int i = 1; i <= c[0] || buf; i++){
c[i] += buf;
buf = c[i] / powm;
}
return ret;
}Bign operator /= (const int num) const {return *this - num;}
// sqrt;
friend Bign sqrt (const Bign&);
// io;
void in () {
*this = 0;
a[0] = 1;
char buf;
bool brea=0;
for(int &i = a[0]; !brea; i++){
for(int j = 1; j <= M; j++){
buf = getchar();
if(buf < '0' || buf > '9')
{brea = 1; break;}
a[i] += (buf - '0') * pow(10, j - 1);
}
}a[0]-=2;
int l=1,r=a[0];
while(l<r){
int buf=a[l];
a[l]=a[r];
a[r]=buf;
l++; r--;
}
}
void out () {
int *a = this -> a;
for(int i = a[0]; i > 0; i--)
printf("%d", a[i]);
if(a[0]==0)putchar('0');
}
};

Bign sqrt (const Bign &num){
Bign l = 1, r = num;
Bign mid, buf;
while(l < r){
mid = (r + l) / 2;
buf = mid * mid;
if(buf == num) break;
if(buf >= num) r = mid;
else l = mid + 1;
}l=l-1;
return l;
// return l * l > num? l-1: l;
}

例题

请前往 Coolkid dalao 的博客来查看

倍增

  • !LCA 倍增 ST 表

DP

  • 阶段类 区间类 预处理 前缀和优化

关于单调队列/栈, 我另有一篇博客在此
下面代码以升序为例

单调栈

int a[N], top = 0;
void push (int x) {
while (a[top-1] > x) top--;
a[top++] = x;
}

单调队列

struct A{
int num, time;
};
A a[N], head = 0, tail = 0;
void push (int x, int t, int l) {
while (head > tail && a[tail].time < t-l) tail++;
while (head > tail && a[head-1].num > x) head--;
a[head++] = (A){x, t};
}