第1页 / 共173页
第2页 / 共173页
第3页 / 共173页
第4页 / 共173页
第5页 / 共173页
第6页 / 共173页
第7页 / 共173页
第8页 / 共173页
ACM巨全模板 .pdf
数据结构：
1.RMQ(区间最值)
2.二维RMQ(求区间最大值)
线段树
a) 模板为区间加法
b)线段树染色
区间最小值
4.线性基(求异或第k大)
5.主席树
a)静态求区间第k小
b)区间中小于k的数量和小于k的总和
c)区间中第一个大于或等于k的值
6.权值线段树
7.动态主席树(区间第k大带修改)
8.树上启发式合并（查询子树的优化）
9.树状数组模板
a)求区间异或和
扩展：
10.区间不重复数字的和 (树状数组)
11.求k维空间中离所给点最近的m个点,并按顺序输出(KD树)
12.LCA (两个节点的公共父节点)
动态规划：
1.LIS(最长上升子序列)
2.有依赖的背包（正解）
3.最长公共子序列(LCS)
4.树形DP
5.状压DP-斯坦纳树
6.背包
a)01背包
b)完全背包
c)多重背包
d)混合背包问题
e)二维费用背包
f)分组背包问题
g)有依赖背包问题
综合代码：
7.dp[i]=min(dp[i+1]...dp[i+k])
题目集
博弈：
1.NIM博弈(一堆每次最少取一次)
2.威佐夫博弈(两堆每次取至少一个或一起取一样的)
3.约瑟夫环
4.斐波那契博弈（取的数依赖于对手刚才取的数）
sg函数
数论：
1.素数检验
2.拉格朗日乘子法（求有等式约束条件的极值）
3.裂项（多项式分子分母拆分）
4.扩展欧几里得
5.勾股数（直角三角形三边长）
6.斯特林公式 (n越大越准确,求n!)
7.牛顿迭代法 (求一元多次方程一个解)
8.同余定理（a≡b(mod m)）
9.线性求所有逆元的方法（求1~p modp的逆元）
10.中国剩余定理(n个同余方程x≡a1(modp1))
11.二次剩余($(ax+k)^2≡n(mod p)$)
12.十进制矩阵快速幂(n很大很大的时候)
13.欧拉函数
14.费马小定理
15.二阶常系数递推关系求解方法 $(a_n=pa_{n-1}+qa_{n-2})$
16.高斯消元
16.矩阵快速幂
18.分解质因数
19.线性递推式BM(杜教)
20.线性一次方程组解的情况
求解行列式的逆矩阵，伴随矩阵，矩阵不全随机数不全
计算几何
1.点
2.三角形
2.多边形
a) . 凸多边形面积的求法：
3.三点求圆心及半径
4.扫描线
5.凸包
6.求凸多边形的直径：
7.求凸多边形的宽度：
8.求凸多边形的最小面积外接矩形：
9.半平面交
图论：
1.最短路(优先队列dijkstra)
2.判断环（tarjan算法）
3.最小生成树（Kruskal 模板）可重边
4.最小生成树（Prim）不可重边
5.Dicnic最大流(最小割)
6.无向图最小环(floyd)
7.floyd算法的动态规划
8.图中找出两点间的最长距离
9.最短路 (spfa)
10.第k短路 (spfa+A*)
11.回文树模板
12.拓扑排序模板
13.次小生成树
14.最小树形图
15.并查集
16.求两个节点的最近公共祖先 (LCA)
17.限制顶点度数的MST(k度限制生成树)
18.多源最短路
19.最短路（输出字典序最小）
20.最长路
图论题目简述:
1.从k个点出发(多源)到其他点的最短距离里面的最大值。
2.建立一棵生成树（不用路径最小，但保证路上最大权值和最小权值之差最小）
3.给定n个点m次操作，有两种操作，M a b 操作是将a b合并到一起，S a 操作是从a所在的集合中删除a点，所有的操作结束后输出集合的个数。
4.有n个城市，每个城市都受若干个或0个其他城市的保护，要攻占一个城市，首先要攻占保护这个城市的所有城市。给出一个有向图，并给出每个城市受哪些城市保护。军队在城市1，求军队攻占到城市n所用的最短时间。
5.给出n个点m条边和两对起点和终点s1,e1;s2,e2,分别求其最短路，问他们的最短路中最多有多少个点是相同的。（求两条最短路的最多公共点）
字符串：
1.字典树(多个字符串的前缀)
2.KMP(关键字搜索)
3.EXKMP(找到S中所有P的匹配)
4.马拉车(最长回文串)
5.寻找两个字符串的最长前后缀(KMP)
6.hash
1.进制hash（单哈希/自然溢出法）
2.无错hash
3.多重hash
4.双hash
7.后缀数组
两个优化：
构造最长公共前缀——Height
按字典序排字符串后缀
8.前缀循环节(KMP的fail函数)
9.AC自动机
10.后缀自动机
小技巧：
1.关于int,double强转为string
2.输入输出挂
4.一些组合数学公式
5.二维坐标的离散化
6.消除向下取整的方法
a)
7.一些常用的数据结构 (STL)
8.Devc++的使用技巧
9.封装好的一维离散化
10.Ubuntu对拍程序
11.常数
12.codeblocks 的使用技巧
13.java大数
叮嘱：
数据结构：
1.RMQ (区间最值,区间出现最大次数,求区间gcd)
2.二维RMQ求区间最大值 (二维区间极值)
3.线段树模板(模板为区间加法) (线段树染色) (区间最小值)
4.线性基 (求异或第k大)
5.主席树(静态求区间第k小) (区间中小于k的数量和小于k的总和) (区间中第一个大于或等于k的值)
6.权值线段树 (求逆序对)
7.动态主席树 (主席树+树状数组) (区间第k大带修改)
8.树上启发式合并 (查询子树的优化)
9,树状数组模板 (求区间异或和，求逆序对) 扩展
10.区间不重复数字的和 (树状数组)
11.求k维空间中离所给点最近的m个点,并按顺序输出(KD树)
12.LCA (两个节点的公共父节点)
动态规划：
1.LIS (最长上升子序列)
2.有依赖的背包 (附属关系)
3.最长公共子序列(LCS)
4.树形DP
5.状压DP-斯坦纳树
6.背包
7.dp[i]=min(dp[i+1]...dp[i+k]),multset
博弈：
1.NIM博弈 (n堆每次最少取一个)
2.威佐夫博弈(两堆每次取至少一个或一起取一样的)
3.约瑟夫环
4.斐波那契博弈 (取的数依赖于对手刚才取的数)
5.sg函数
数论：
1.数论 素数检验：普通素数判别 线性筛 二次筛法求素数 米勒拉宾素数检验
2.拉格朗日乘子法（求有等式约束条件的极值）
3.裂项（多项式分子分母拆分）
4.扩展欧几里得 (ax+by=c)
5.勾股数 (直角三角形三边长)
6.斯特林公式 (n越大越准确,求n!)
7.牛顿迭代法 (求一元多次方程一个解)
8.同余定理 (a≡b(mod m))
9.线性求所有逆元的方法求 (1~p modp的逆元)
10.中国剩余定理(n个同余方程x≡a1(modp1))
11.二次剩余($(ax+k)^2≡n(mod p)$)
12.十进制矩阵快速幂(n很大很大的时候)
13.欧拉函数
14.费马小定理
15.二阶常系数递推关系求解方法 (a_n=p*a{n-1}+q*a{n-2})
16.高斯消元
17.矩阵快速幂
18.分解质因数
19.线性递推式BM(杜教)
20.线性一次方程组解的情况
21.求解行列式的逆矩阵，伴随矩阵，矩阵不全随机数不全
组合数学：
1.循环排列 (与环有关的排列组合)
计算几何：
1.三角形 (求面积))
2.多边形
3.三点求圆心和半径
4.扫描线 (矩形覆盖求面积) (矩形覆盖求周长)
5.凸包 (平面上最远点对)
6.求凸多边形的直径
7.求凸多边形的宽度
8.求凸多边形的最小面积外接矩形
9.半平面交
图论：
基础:前向星
1.最短路(优先队列dijkstra)
2.判断环(tarjan算法)
3.最小生成树(Kruskal 模板)
4.最小生成树(Prim)
5.Dicnic最大流(最小割)
6.无向图最小环(floyd)
7.floyd算法的动态规划(通过部分指定边的最短路)
8.图中找出两点间的最长距离
9.最短路 (spfa)
10.第k短路 (spfa+A*)
11.回文树模板
12.拓扑排序 (模板)
13.次小生成树
14.最小树形图(有向最小生成树)
15.并查集 (普通并查集,带权并查集,)
16.求两个节点的最近公共祖先 (LCA)
17.限制顶点度数的MST(k度限制生成树)
18.多源最短路(spfa,floyd)
19.最短路 (输出字典序最小)
20.最长路
图论题目简述
字符串：
1.字典树(多个字符串的前缀)
2.KMP(关键字搜索)
3.EXKMP(找到S中所有P的匹配)
4.马拉车(最长回文串)
5.寻找两个字符串的最长前后缀(KMP)
6.hash(进制hash,无错hash,多重hash,双hash)
7.后缀数组 (按字典序排字符串后缀)
8.前缀循环节(KMP的fail函数)
9.AC自动机 (n个kmp)
10.后缀自动机
小技巧：
1.关于int,double强转为string
2.输入输出挂
3.低精度加减乘除
4.一些组合数学公式
5.二维坐标的离散化
6.消除向下取整的方法
7.一些常用的数据结构 (STL)
8.Devc++的使用技巧
9.封装好的一维离散化
10.Ubuntu对拍程序
11.常数
12.Codeblocks使用技巧
13.java大数
叮嘱
数据结构：
1.RMQ(区间最值)
RMQ算法，是一个快速求区间最值的离线算法，预处理时间复杂度O（n*log(n)），查询O(1)， 所以是
一个很快速的算法，当然这个问题用线段树同样能够解决。
1、求区间的最大值和最小值！
#include
using namespace std;
const int maxn=100117;
int n,query;
int num[maxn];
int F_Min[maxn][20],F_Max[maxn][20];
void init(){
for(int i=1;i<=n;i++){
F_Min[i][0]=F_Max[i][0]=num[i];
}
for(int i=1;(1<
printf("区间%d到%d的最大值为：%d\n",a,b,Query_max(a,b));
printf("区间%d到%d的最小值为：%d\n",a,b,Query_min(a,b));
printf("区间%d到%d的最大值和最小值只差为：%d\n",a,b,Query_max(a,b)-
Query_min(a,b));
}
return 0;
}
2、求区间内出现次数最多的数字出现的次数！
对上升序列如：1 1 2 2 2 3 3 4 5 5 … 统计区间出现次数最多数个数。
我们可以构造一个b[]数组，
if（a[i]==a[i-1]）b[i]=b[i-1]+1;
else b[i]=1;
这样对上述例子，b[]数组有1 2 1 2 3 1 2 1 1 2
那么对询问区间[l,r]，如果l在数与数交界处，那么直接查询l,r区间最大值。
否则要知道与a[l]相同延伸到end，那么这个区间大小end-l+1，与rmq(end+1,r)取最大值就是答案。
#include
using namespace std;
const int maxn=100017;
int num[maxn],f[maxn],MAX[maxn][20];
int n;
int max(int a,int b){
return a>b?a:b;
}
int rmq_max(int l,int r){
if(l>r)
return 0;
int k=log2((double)(r-l+1));
return max(MAX[l][k],MAX[r-(1<
}
}
init();
for(int i=1;i<=q;i++) {
scanf("%d%d",&a,&b);
int t=a;
while(t<=b&&num[t]==num[t-1]){
t++;
}
int cnt=rmq_max(t,b);
int ans=max(t-a,cnt);
printf("%d\n",ans);
}
}
return 0;
}
RMQ求区间gcd
f [ l , r ]=gcd($a_l，a_{l+1}，…，a_r$)，问f [ l , r ]的值和有多少对(L,R)使得f [ L, R ] = f [ l , r ]。
#include
using namespace std;
#define LL long long
int dp[100010][32];
int a[100010];
int n,m,g,j;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
void rmq_init(){
for(int j=1;j<=n;j++) dp[j][0]=a[j];
for(int i=1;(1<mp;
void setTable(){
mp.clear();
for(int i=1;i<=n;i++){
g=dp[i][0],j=i;
while(j<=n){
int l=j,r=n;
while(l>1;
if(rmq_qui(i,mid)==g) l=mid;
else r=mid-1;
}
mp[g]+=l-j+1; //相当于二分枚举相加
j=l+1;
g=rmq_qui(i,j);
}
}
}
int main(){
int t,l,r;
int cas=1;
scanf("%d",&t);
while(t--){
printf("Case #%d:\n",cas++);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
rmq_init();
setTable();
scanf("%d",&m);
for(int i=0;i
using namespace std;
int n,m,a[400][400];
int dp[400][400][20][20];
int p;
int r1,c1,r2,c2,k1,k2,ans;
int main(){
scanf("%d%d",&n,&m); //二维区间的范围
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
dp[i][j][0][0]=a[i][j]; //初始化
}
}
int u1=0,u2=0;
while((1<<(u1+1))<=n) u1++;
while((1<<(u2+1))<=m) u2++;
for(int i=1;i<=n;i++){
for(int k=1;k<=u2;k++)
for(int j=1;j+(1<<(k-1))<=m;j++){ //列建立RMQ
dp[i][j][0][k]=max(dp[i][j][0][k-1],dp[i][j+(1<<(k-1))][0][k-1]);
}
}
for(int i=1;i<=m;i++){
for(int k=1;k<=u1;k++){
for(int j=1;j+(1<<(k-1))<=n;j++){ //行建立RMQ
dp[j][i][k][0]=max(dp[j][i][k-1][0],dp[j+(1<<(k-1))][i][k-1][0]);
，
查
询
复
杂
度
还
有
一
种
做
法
是
把
每
一
行
当
作
一
维
区
间
，
求
最
大
值
建
表
}
}
}
for(int i=1;i<=u1;i++){
for(int j=1;j<=u2;j++){
for(int k=1;k+(1<<(i-1))<=n;k++){
for(int p=1;p+(1<<(j-1))<=m;p++){ //行列合并
dp[k][p][i][j]=max(dp[k][p][i][j],dp[k][p][i-1][j-1]);
dp[k][p][i][j]=max(dp[k][p][i][j],dp[k+(1<<(i-1))][p][i-1][j-1]);
dp[k][p][i][j]=max(dp[k][p][i][j],dp[k][p+(1<<(j-1))][i-1][j-1]);
dp[k][p][i][j]=max(dp[k][p][i][j],dp[k+(1<<(i-1))][p+(1<<(j-1))]
[i-1][j-1]);
}
}
}
}
scanf("%d",&p);
while(p--){
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);//矩形的两个对角线顶点
k1=k2=0;
while((1<<(k1+1))<=(r2-r1+1)) k1++; //等于int(log2(r2-r1+1))
while((1<<(k2+1))<=(c2-c1+1)) k2++; //等于int(log2(c2-c1+1))
ans=0;
//下面相当于分成四块矩形
ans=max(ans,dp[r1][c1][k1][k2]);//从(r1,c1)开始长度为2^k1和2^k2
ans=max(ans,dp[r2-(1<
using namespace std;
typedef long long ll;
const int maxn = 1000005;
struct TREE {
int tree[maxn * 4]; // 线段树
int lz[maxn * 4]; // 延迟标记
void init() { //初始化
memset(tree, 0, sizeof(tree));
memset(lz, 0, sizeof(lz));
}
// 创建线段树
void build(int root, int l, int r) {
if (l == r) {
scanf("%d", &tree[root]);
return;
}
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc