XCPC 程序设计竞赛模板 杂项
sp1ke0ne
|
|
74
|
编程

3276 字
|
23 分钟

基础算法

模拟

  • 计算时间复杂度判断可行性，按题意写
  • 列出所有条件与操作，注意分类讨论
  • 时间复杂度可行

构造

排序

  • STL 中 sort 是快排 $O(nlogn)$ ；归并稳定 $O(nlogn)$
  • 比较相邻或逆序对用归并，无序数组排序用快排

自动取模整数

int mod;//模数
struct Mint{
    int v;
    Mint():v(0){}
    Mint(const ll&x){v=static_cast<int>((-mod<=x && x<mod) ? x : x%mod); if(v<0)v+=mod;}
    friend Mint operator+(const Mint& a, const Mint& b){return (a.v+b.v)%mod;}
    friend Mint operator-(const Mint& a, const Mint& b){return (a.v-b.v+mod)%mod;}
    friend Mint operator*(const Mint& a, const Mint& b){
        return static_cast<int>(1ll * a.v * b.v % mod);
    }
    Mint qpow(int x) const{
        ll res=1, a=v;
        while(x){
            if(x&1) res=res*a%mod;
            a=a*a%mod;
            x>>=1;
        }
        return Mint(res);
    }//只有 mod 为质数时才能用于除法
    friend Mint operator/(const Mint& a, const Mint& b){
        return static_cast<int>(1ll * a.v * b.qpow(mod-2).v % mod);
    }
	friend bool operator!=(const Mint& a, const Mint& b){return a.v!=b.v;}
};
using ll=Mint;//模运算下 Mint 替代 ll

二分

bool check(int x){}
void binary(int l, int r){
    int ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid, l=mid+1;//最小值最大化
        else r=mid-1;
    }
}

二分搜索

  • lower_bound 首个大于等于
  • upper_bound 首个大于

二分答案

  • 答案有界且满足单调性
  • 最小值最大化/最大值最小化问题

倍增

  • $\forall x(x=\sum 2^k)$
  • 从大到小枚举 $2^k$ ，实现倍增查找满足条件的整数

双指针

双指针实现

同时使用两个指针，在序列、链表结构上指向的是位置，树、图结构中指向的是节点，通过同向或相向移动来维护、统计信息。

双指针应用

双指针维护的区间信息必须满足随着区间左端点的递增，区间右端点不减。

不同序列双指针

  • 子序列匹配

  • 归并排序

快慢指针

  • 判断环问题（看慢指针是否能追上快指针）

  • 单链表找中间节点问题（快指针到单链表结尾，慢指针到一半）

  • 有序数组去重

对撞指针

  • 利用序列有序性查找两数之和等于特值

  • 对称性相关的问题（判断回文串&反转字符串）

  • 选择排序

滑动窗口

  • 维护区间信息（随着区间左端点的递增，区间右端点不减）

分治

分治实现

分治步骤：

  1. 寻找当前区间 $[l,r]$ 中点 $mid$
  2. 递归处理左子区间 $[l,mid]$
  3. 递归处理右子区间 $[mid+1,r]$
  4. 处理左子区间对右子区间的影响，并对于右区间或者答案进行更改与修正

分治应用

分治问题具有最优子结构，即大问题可分解成独立且类型相同的子问题，子问题的答案可合并成大问题的答案。

将大问题分解成同类且相互独立的小问题，通过直接解决容易解决的小问题然后合并答案成大问题的答案。

  • 若满足递归终止条件（问题规模小于该阈值可直接解决）
    • 直接解决问题
  • 若不满足递归终止条件
    • 分解问题以小于阈值从而直接求解问题
    • 合并问题答案

动态规划

线段树

线段树分治

CDQ 分治

贪心

贪心实现

排序解法

通过邻项交换法推导贪心策略。

将数组按照某顺序排序，然后按某种顺序（例如从小到大）选择。离线的，先处理再选择。

后悔解法

每次都取堆中最大/小的东西，并更新堆。在线的，边处理边选择。

离散化

  • 数据本身很大或类型不支持，无法作为数组下标，而影响最终结果的只有元素之间的相对大小关系，将原来的数据按照排名来处理问题。
  • 保证数据在离散化以后仍然保持原来的 全/偏序 关系。

$O(n\log n)$

namespace DIS{//离散化
    using ll=int;
	ll v[N];// N 为元素个数，即 add 的次数
	int tot;
	inline void init(){tot=0;}//初始化
	inline void add(ll val){v[++tot]=val;}//添加元素
	inline void work(){//离散化
		sort(v+1, v+1+tot);
		tot=unique(v+1, v+1+tot)-(v+1);
	}
	inline int id(ll val){return lower_bound(v+1, v+1+tot, val)-v;}//获取离散化结构
	inline ll getv(int id){return v[id];}//获取原值
}

权值数组

  • 序列 $a$ 的权值数组 $tot[x]$ 维护 $x$ 在 $a$ 中出现的次数，即桶信息
  • 值域过大时需要离散化
  • 普通数组基于元素个数开辟空间，节点维护与下标/序号联系的特定信息（最值、和差）
  • 权值数组基于元素值域开辟空间，节点维护值域区间内元素的个数 ，不关心下标信息

前缀和&差分

一维

一维前缀和

区间查询 $[l,r]$ 的总和，通过区间前缀和的可差分性转化为 $[0, r]-[0, l-1]$ ，只需 $O(n)$ 预处理前缀和 $$ sum_i=\sum_{j=1}^ia_j=sum_{i-1}+a_i\ sum_{l,r}=\sum_{i=l}^ra_i=sum_r-sum_{l-1} $$

一维差分

区间修改 $[l,r]$ $O(1)$ & 单点查询 $a_i$ $O(n)$ $$ \begin{align} d_1&=a_1\ d_i&=a_i-a_{i-1},i\in[2,n]\ \text{区间修改：}[a_l,a_r]\gets [a_l,a_r]+v &= d_l\gets d_l+v,d_{r+1}\gets d_{r+1}-v\ \text{单点查询：}a_i&=\sum_{j=1}^id_j \end{align} $$

二维

二维前缀和

$$ \begin{align} sum_{i,j}&=a_{i,j}+sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}\ \sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}a_{i,j}&=sum_{x_2,y_2}-sum_{x_1-1,y_2}-sum_{x_2,y_1-1}+sum_{x_1-1,y_1-1}\ \end{align} $$

二维差分

$$ \begin{align} d_{i,j}&=a_{i,j}-a_{i-1,j}-a_{i,j-1}-a_{i-1,j-1}\ \text{矩形修改：}(x_1,y_1)to(x_2,y_2)+v &= d_{x_1,y_1}+v,d_{x1,y2+1}-v,d_{x2+1,y1}-v,d_{x_2+1,y_2+1}+v\ \text{单点查询：}a_{i,j}&=\sum_{x=1}^i\sum_{y=1}^jd_{x,y}+d_{x-1,y}+d_{x,y-1}-d_{x-1,y-1}\ \end{align} $$

树上

树上前缀和

$sum_i$ 表示节点 i 到根节点的权值和：

  • 点权：$(u,v)=sum_u+sum_v-sum_{lca(u,v)}-sum_{fa(lca(u, v))}$
  • 边权：$(u,v)=sum_u+sum_v-2\times sum_{lca(u,v)}$

树上差分

  • 对树上一段路径 $(s,t)$ 进行差分
    • 对树上路径多次修改然后询问点/边的值
  • 后序遍历树统计总和
  • 点差分：$d_i是点权的差分数组$
    • $d_s\leftarrow d_s+1$
    • $d_{lca}\leftarrow d_{lca}-1$
    • $d_t\leftarrow d_t+1$
    • $d_{fa(lca)}=\leftarrow d_{fa(lca)}-1$
  • 边差分：将本应累加到边上的值向下移动到附近的点里
    • $d_s\leftarrow d_s+1$
    • $d_t\leftarrow d_t+1$
    • $d_{lca}\leftarrow d_{lca}-2$

离线算法

线段树分治

线段树分治实现

离线后在时间轴上建线段树，每个操作相当于在线段树上进行区间操作。时间可以是任意有序序列

  1. 建立线段树维护时间段，每个节点维护一个 vector 存储该时间段的信息
  2. 插入信息到线段树（区间修改）
  3. 考虑处理每个时间段的信息并
    1. 从根节点开始分治，维护当前信息并
    2. 每到一个节点就将节点所有信息进行合并
    3. 回溯时撤销这部分贡献
    4. 到达叶子节点时统计信息并即答案

更改信息复杂度为 $O(T(n))$ ，则可设置栈保留更改，以 $O(T(n))$ 撤销。整个分治流程 $O(nlogn(T(n)+M(n)))$ ，其中 $M(n)$ 为合并信息

线段树分治应用

维护只在某个时间段 $[l, r]$ 内有效的信息，允许离线下询问某一时刻的信息并集

用支持撤销的数据结构模拟删除操作

线段树分治与可撤销带权并查集

  • 时间区间[l, r]内合并信息记录在对应节点
  • 查询答案时向下分治合并节点的合并信息到叶子节点（对应时刻）统计贡献的并集
  • 返回时撤销并查集
int fa[N], sz[N];//可撤销并查集
ll sum[N];//记录节点i与1连通的时刻之和
int stk[N<<1], top;
void dsu(int n){
  for(int i=1; i<=n; ++i){
    fa[i]=i, sz[i]=1, sum[i]=0;
  }
  top=0;
}
int find(int x){return x==fa[x] ? x : find(fa[x]);}/*不能路径压缩*/
void merge(int x, int y){
  x=find(x),y=find(y);
  if(x==y) return;
  if(sz[x]<sz[y]) swap(x, y);/*按秩合并，此处秩为大小*/
  stk[++top]=y;
  sum[y]-=sum[x];//v在之前时刻不属于u，减去的部分为不属于v的部分
  fa[y]=x;
  sz[x]+=sz[y];
}
void back(int t){/*按合并逆序删除到只剩 t 条边*/
    while(top>t){
        int y=stk[top--];
        sum[y]+=sum[fa[y]];
        sz[fa[y]]-=sz[y];
        fa[y]=y;
    }
}
//线段树分治
vector<pair<int, int>> e[N<<1];//节点存储该时间段的合并信息
int ls[N<<1], rs[N<<1], tot, root;//左儿子、右儿子、开点大小、根默认0
void query(int p, int l, int r){//线段树分治统计答案
    /*记录合并前并查集边数*/
	int cnt=top;
    /*合并该时间段内有效信息*/
	for(auto& [u, v] : e[p]){
		merge(u, v);
	}
    if(l==r){/*叶子节点统计时刻答案*/
        sum[find(1)]+=l;//统计与1连通的根节点与1连通的时刻，在回溯时将答案添加给连通块内每个点
        back(cnt);/*撤销*/
        return;
    }
    int mid=l+((r-l)>>1);
    query(ls[p], l, mid);
    query(rs[p], mid+1, r);
	back(cnt);/*撤销*/
}
void update(int& p, int l, int r, int L, int R, const pair<int, int>& ee){//更新区间[L,R]
    if(!p) p=++tot;
    if(L<=l && r<=R){//当前区间被修改区间覆盖
        e[p].push_back(ee);//记录该时间段内合并信息
        return;
    }
    int mid=l+((r-l)>>1);
    if(L<=mid) update(ls[p], l, mid, L, R, ee);
    if(mid<R) update(rs[p], mid+1, r, L, R, ee);
}
update(root, 1, n, l, r, make_pair(a, b));//[l,r]时间段内合并节点(a,b)

不同属性的数据分别计算

n 点 m 边的无向图，有 k 种颜色，每条有一种颜色，对于每种颜色，判断删去该颜色的所有边后图是否连通？是否是一棵树？输出满足的连通的颜色数和是树的颜色数。

  • 对每种颜色建立一个时刻在该时刻内无该颜色的边，其他边都有，可撤销并查集维护（叶节点对应无一种颜色的边）。线段树同层节点区间相互独立，分治到叶节点时统计答案不重不漏，回溯时撤销保证互不影响
/*对颜色建立时间轴 [1, k]，每个颜色 c 的边在时刻 c 没有*/
update(root, 1, k, 1, e[i].c - 1, i);//[1, c-1]有颜色c的边 i
update(root, 1, k, e[i].c + 1, k, i);//[c+1, k]有颜色c的边 i
void query(int p, int l, int r){//线段树分治统计答案
    /*记录合并前并查集边数*/
	int cnt=top;
    /*合并该时间段内有效信息*/
	for(auto& i : eid[p]){
		merge(e[i].u, e[i].v);
	}
    if(l==r){/*叶子节点统计时刻答案*/
        ans[l]=(sz[find(1)]==n);//判断去除所有颜色 l 后 n 个点是否连通
        back(cnt);/*撤销*/
        return;
    }
    int mid=l+((r-l)>>1);
    query(ls[p], l, mid);
    query(rs[p], mid+1, r);
	back(cnt);/*撤销*/
}
ans1+=ans[i];//删去后图连通的颜色数
ans2+=(ans[i]&&(m-cnt[i])==(n-1));//删去后是树的颜色数。是树<->连通且边数为n-1（m是总边数，cnt[i]统计颜色i的边数）

CDQ分治

思想

通过分治解决多维偏序问题，只需考虑分治后左边对右边的影响，分治过程中区间的划分可以把数值的比较转化为左右区间位置的比较，节省一维比较过程。只支持离线操作。

将CDQ分治的递归树看作线段树，则CDQ分治即线段树的中序/后序遍历函数。

CDQ步骤：

  1. 递归前一半
  2. 递归后一半
  3. 判断前一半对后一半的影响

应用

解决和点对有关的问题

问题类似“长度n序列，统计有特性的点对(i,j)的数量/找到一对点(i,j)最大化函数值”

算法流程：

  1. 寻找序列中点mid
  2. 划分3类点对(i,j)
    1. $l\leq i\leq mid,l\leq j\leq mid$
    2. $l\leq i\leq mid,mid+1\leq j\leq r$
    3. $mid+1\leq i\leq r,mid+1\leq j\leq r$
  3. 将序列划分为 $(l,mid)$ 和 $(mid+1,r)$ ，此时第一、三类点对都在两个序列中
  4. 递归地处理第一、三类点对（第一、三类点对递归后转换为第二类点对降维）
  5. 设法处理第二类点对（一般是合并时）
  • 三维偏序
    • 统计满足 $a_i<a_j, b_i<b_j, c_i<c_j$ 的 $j$ 即可
  • 动态逆序对
    • 统计满足 $v_i<v_j, i>j, t_i>t_j$ 或 $v_i>v_j, i<j, t_i>t_j$ 的 $j$ 对应的 $t_j$ 即可

优化 1D/1D 动态规划的转移

1D/1D动态规划是具有一维的DP数组，转移方程类似 $dp_i=1+max_{j=1}^{i-1}dp_j[a_j<a_i][b_j<b_i]$ ，状态转移是 $O(n)$

优化转移过程：

  1. $l==r$ 说明 $dp_r$ 计算完成，直接令 $++dp_r$ 返回即可
  2. 递归 $cdq(l,mid)$
  3. 处理所有 $l\leq j\leq mid, mid+1\leq i\leq r$ 的转移关系（按中序遍历序分治以保持DP转移的有序性）
  4. 递归 $cdq(mid+1,r)$

CDQ分治将 $O(n^2)$ 优化为 $O(nlog^2n)$ ，转移过程必须满足：

  • 用于计算 $dp_i$ 的所有 $dp_j$ 都已计算完毕
  • 用于计算 $dp_i$ 的所有 $dp_j$ 都必须能更新到 $dp_i$ （不漏）

将动态问题转化为静态问题

适用于需要做xx修改然后做xx询问的数据结构题

  • 若把询问离线，所有操作会按时间自然排成序列
  • 每个修改均与之后的询问相关，修改-询问关系共 $O(n^2)$ 对

CDQ分治将时间序列折半，处理修改和询问间关系：

  • 先递归处理 $[l,mid]$ 和 $[mid+1, r]$ 之间的修改-询问关系
  • 再处理所有 $l\leq i\leq mid,mid+1\leq j\leq r$ 的修改-询问关系，其中 i 是修改，j 是询问
  • 若修改间相互独立（加减法），则无需处理 $l\leq i\leq mid$ 和 $mid+1\leq j\leq r$ 以及 $cdq(l,mid)$ 和 $cdq(mid+1,r)$ 之间的时序关系
  • 若修改间并不独立（赋值操作），修改后序列依赖于之前的序列。此时处理所有跨越 mid 的修改-询问关系的步骤必须放在 $cdq(l,mid)$ 和 $cdq(mid+1,r)$ 之间（按中序遍历序分治保证修改时序）

CDQ分治每次只处理跨越 mid 的修改-询问关系，此时只需考虑所有询问都在修改之后的静态问题，实现离线处理动态问题

代码

//动态逆序对
//三维偏序中三维分别是 vi, i, ti
void cdq(int l, int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    //对 vi 进行排序，然后进入cdq分治，降维 vi 这一维度
    cdq(l, mid);
    cdq(mid+1, r);
    //在分治合并过程中对第二维 ti 进行排序，降维 ti 这一维
    sort(a+l, a+mid+1, cmpT);
    sort(a+mid+1, a+r+1, cmpT);
    //最后通过树状数组统计在满足前两维的情况下第三维的答案
    int i=l, j=mid+1;
    while(j<=r){
        while(i<=mid && a[i].t>a[j].t){
            add(a[i].id, 1);
            ++i;
        }
        los[a[j].t]+=query(n)-query(a[j].id);
        ++j;
    }
    for(int k=l; k<i; ++k) add(a[k].id, -1);
    i=mid+1, j=l;
    while(j<=mid){
        while(i<=r && a[i].t>a[j].t){
            add(a[i].id, 1);
            ++i;
        }
        los[a[j].t]+=query(a[j].id);
        ++j;
    }
    for(int k=mid+1; k<i; ++k) add(a[k].id, -1);
}
// 优化 1D/1D 动态规划的转移
// 统计三维满足 ti<tj, hi>=hj, vi<=vj 或 ti>tj, hi<=hj, vi<=vj 的导弹点对数
// res是方案数，len是最长不上升子序列长度
// t=0/1代表以i结尾/开头的最长不上升子序列
// 第一维是时间/下标，排序降维
void cdq(int l, int r, int t){
    if(r==l){
        return;
    }
    int mid=(l+r)>>1;
    cdq(l, mid, t);
    //第二维是高度，排序降维
    sort(a[t]+l, a[t]+mid+1, cmp1);
    sort(a[t]+mid+1, a[t]+r+1, cmp1);
    int i=l, j=mid+1;
    //第三维是速度，是满足条件的关键（限制条件最后一维）
    //树状数组统计答案
    while(j<=r){
        while(i<=mid && (cmp1(a[t][i], a[t][j]) || a[t][i].h==a[t][j].h)){
            add(a[t][i].v, a[t][i].len, a[t][i].res);
            ++i;
        }
        double res=0.0;
        int len=0;
        query(a[t][j].v, len, res);
        if(a[t][j].len < len+1){
            a[t][j].len=len+1;
            a[t][j].res=res;
        }else if(a[t][j].len==len+1){
            a[t][j].res+=res;
        }
        ++j;
    }
    for(int k=l; k<i; ++k){
        dele(a[t][k].v);
    }
    sort(a[t]+mid+1, a[t]+r+1, cmp3);//还原按时间排序
    cdq(mid+1, r, t);//保证转移顺序从前往后
}

整体二分

莫队算法

如果觉得本文对您有帮助，可以支持下博主哦，感谢~
版权声明：除特殊说明外，博客文章均由 Sp1ke 原创，均采用 CC BY-SA 4.0 许可证
转载请注明文章地址及作者并附带本声明！
CDQ 分治二分倍增分治前缀和双指针差分排序整体二分权值数组构造模拟离散化线段树分治自动取模整数莫队算法贪心
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
															
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
XCPC 程序设计竞赛模板 数学

							
							

							
XCPC 程序设计竞赛模板 字符串

							
							

							
XCPC 程序设计竞赛模板 图论

							
							

							
XCPC 程序设计竞赛模板 数据结构

							
							

							
XCPC 程序设计竞赛模板 动态规划

							
							

							
XCPC 程序设计竞赛模板 搜索

							
							

							
XCPC 程序设计竞赛模板 STL