[TOC]
贪心
AcWing122.糖果传递[1]
有n个小朋友坐成一圈，每人有
a[i]个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。
AC代码：
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 1E6 +10 ;
int n ;
int a[N] ;
LL c[N] ;
int main()
{
cin >> n ;
LL sum = 0; // 转化成区间不等式的形式
for(int i = 1; i <= n ; i ++ ) scanf("%d",&a[i]) , sum += a[i];
LL avg = sum / n ;
for(int i = n ; i > 1 ; i -- ) c[i] = c[i+1] + avg - a[i] ;
c[1] = 0 ;
sort(c+1 , c + n + 1 ) ;
LL res = 0 ; // core code
for(int i = 1 ; i <= n ; i ++ ) res += abs(c[i] - c[(n + 1 )/2]) ;
cout << res << endl;
return 0 ;
}
绝对值不等式解题策略
化为区间不等式的形式。比较考验数学能力。
-
通过核心代码求解
for(int i = 1 ; i <= n ; i ++ ) res += abs(c[i] - c[(n + 1 )/2]);
Acwing112 .雷达设备[2]
假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
每个小岛都位于海洋一侧的某个点上。
雷达装置均位于海岸线上，且雷达的监测范围为d，当小岛与某雷达的距离不超过d时，该小岛可以被雷达覆盖。
我们使用笛卡尔坐标系，定义海岸线为x轴，海的一侧在x轴上方，陆地一侧在x轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。
#include<bits/stdc++.h>
using namespace std ;
const int N = 1010 ;
int n , d ;
struct Segment
{
double l , r ;
bool operator<(const Segment & s)const
{
return r < s.r ;
}
}seg[N] ;
int res = 0 ;
double aim = -1e20 ;
int main()
{
cin >> n >> d ;
for(int i = 0 ; i < n ; i ++ )
{
int x , y ;
cin >> x >>y ;
if(y > d)
{
puts("-1") ;
goto Exit;
}
else
{
double len = sqrt(d*d - y*y) ;
seg[i] = {x - len , x + len } ;
}
}
sort(seg , seg +n ) ;
for(int i = 0 ; i < n ; i ++ )
{
if(aim < seg[i].l)
{
res ++ ;
aim = seg[i].r ;
}
}
cout << res << endl;
Exit:
return 0 ;
}
- 关于
goto语句的使用说明：==当出现goto跳过某些变量的初始化的时候，编译器不允许通过。==务必小心。
区间贪心策略
首先把问题转化成区间贪心。（数据区间化，假设这里通过结构体存储）
将区间按照右端点排序。选取aim为0xcfcfcfcf
-
遍历每一个区间。
- 如果当前区间左端点大于aim，则
aim更新当前区间右端点，res++ - 否则，继续遍历下一区间
- 如果当前区间左端点大于aim，则
得到答案
付账问题[3]
几个人一起出去吃饭是常有的事。
但在结帐的时候，常常会出现一些争执。
现在有 n 个人出去吃饭，他们总共消费了 SS 元。
其中第
个人带了
元。
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为 SS 的前提下，最后每个人付的钱的标准差最小。
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。
你需要输出最小的标准差是多少。
p1.png
#include<bits/stdc++.h>
using namespace std ;
const int N = 5e5+10 ;
int n;
long double S ;
int a[N] ;
int main()
{
cin >>n >> S;
for(int i = 0; i < n ; i ++ )
{
scanf("%d",&a[i]) ;
}
sort(a,a+n) ;
long double avg = S/n , res = 0 ;
for(int i = 0 ; i < n ; i ++ )
{
long double cur = S/ (n -i) ;
if(cur > a[i]) cur = a[i] ;
res += (cur -avg)*(cur -avg) ;
S -= cur ;
}
printf("%.4llf" ,sqrt(res / n ) ) ;
return 0 ;
}
思路：按照==均摊==为标准。
值动态更新。
cur为当前需付金钱下，每个人应该付多少钱。如果当前人的钱a[i]不足cur，则此人的钱全部拿出，也就是a[i]；如果当前人的钱a[i]大于cur，那么此人就优先按照cur付钱。
下一轮循环cur更新。可见，如果上一个人带的钱小于上一轮的cur,那么当前轮的cur数值一定会提高。
如果上一个人带的钱大于等于cur，那么当前轮的cur还是上一轮的cur。
图论
Dijkstra
- 思想：划出两个集合，一个是存放已经更新并且不再更新的结点的集合，另一边是没有更新距离的结点的集合。每次从未更新的选出一个
最小的结点，把它放进第一个集合里去，然后对利用它对每一个未更新的结点更新，重复执行。
- 特点：使用堆进行存储pair，其中pair用来记录dist和ver
int dijkstra()
{
priority_queue<PII,vector<PII> , greater<PII>> heap ;
heap.push({0,1}) ; // 第一个是dist
while(heap.size() )
{
auto t = heap.top() ;
heap.pop() ;
int ver = t.second , d = t.first ;
if(st[ver]) continue ;
st[ver] = 1 ;
for(int i = h[ver] ; ~i ; i = ne[i] )
{
int j = e[i] ;
if(dist[j] >d + w[i])
{
dist[j] = d + w[i] ;
heap.push({dist[j],j}) ;
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1 ;
return dist[n] ;
}
SPFA
- 思想：当前结点
入队，计算其邻居的最短距离；
- 特点：使用普通队列，并且队列存储的是结点编号。
int spfa()
{
queue<int> q ;
q.push(1) ;
st[1] = 1 ;
while(q.size())
{
auto t = q.front() ;
q.pop();
st[t] = 0 ; // 和dijkstra不同的地方， st数组记录：在队列的结点编号。所以出队即可置零
for(int i = h[t] ; ~i ; i = ne[i])
{
int j = e[i] ;
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i] ;
if(!st[j]) // 不在队列里面，才加入队列
{
q.push(j) ;
st[j] = 1 ;
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1 ;
return dist[n] ;
}
搜索
偏移量不用过多思考，只是1,-1每两个单位向后顺移即可。
三维迷宫BFS
你现在被困在一个三维地牢中，需要找到最快脱离的出路！
地牢由若干个单位立方体组成，其中部分不含岩石障碍可以直接通过，部分包含岩石障碍无法通过。
向北，向南，向东，向西，向上或向下移动一个单元距离均需要一分钟。
你不能沿对角线移动，迷宫边界都是坚硬的岩石，你不能走出边界范围。
请问，你有可能逃脱吗？
如果可以，需要多长时间？
每组数据第一行包含三个整数 L,R,CL,R,C 分别表示地牢层数，以及每一层地牢的行数和列数。
接下来是 LL 个 RR 行 CC 列的字符矩阵，用来表示每一层地牢的具体状况。
每个字符用来描述一个地牢单元的具体状况。
其中, 充满岩石障碍的单元格用”#”表示，不含障碍的空单元格用”.”表示，你的起始位置用”S”表示，终点用”E”表示。
每一个字符矩阵后面都会包含一个空行。
当输入一行为”0 0 0”时，表示输入终止。
c++tuple的用法：(保险起见用struct代替)
typedef tuple<int,int,int> U3I ; // 名称重新定义 U3I tp[30] ; // tuple 数组 tp[2] = {1,2,3} ; // 赋值 cout << get<2>(tp[2])<< endl; // 元素的获取
//偏移量
int dx[] = {1,-1,0,0,0,0} ;
int dy[] = {0,0,1,-1,0,0} ;
int dz[] = {0,0,0,0,1,-1} ;
int bfs(Point sr)
{
queue<Point> q ;
q.push(sr) ;
memset(dist , -1 , sizeof dist) ;
dist[sr.x][sr.y][sr.z] = 0 ;
while(q.size())
{
auto t = q.front() ;
q.pop() ;
for(int i = 0 ; i < 6 ; i ++ )
{
int x = t.x + dx[i] ;
int y = t.y + dy[i] ;
int z = t.z + dz[i] ;
// 过滤
if(x < 0 ||x >= l || y < 0 || y >= r ||z < 0 || z >= c) continue ;
if(dist[x][y][z] != -1 ) continue ;
if(g[x][y][z] == '#') continue ;
// 距离加一
dist[x][y][z] = dist[t.x][t.y][t.z] +1 ;
if(g[x][y][z] == 'E') return dist[x][y][z] ;
//填充队列
q.push({x,y,z}) ;
}
}
return -1 ;
}
二维迷宫BFS
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×CR×C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
第一行是一个正整数 TT，表示一共有 TT 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 RR 和 CC，表示地图是一个 R×CR×C 的矩阵。
接下来的 RR 行描述了地图的具体内容，每一行包含了 CC 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
//偏移量
int dx[] = {1,-1,0,0} ；
int dy[] = {0,0,1,-1} ;
int bfs(PII st)
{
queue<PII> q ;
q.push(st) ;
memset(dist , -1 , sizeof dist ) ;
dist[st.x][st.y] = 0 ;
while(q.size())
{
auto tmp = q.front() ;
q.pop() ;
for(int i = 0 ; i < 4 ; i ++ )
{
int x = tmp.x + dx[i] , y = tmp.y + dy[i] ;
//过滤
if(x < 0 || x>= n || y < 0 || y >= m ) continue ;
if(g[x][y] == '#' ) continue ;
if(dist[x][y] != -1 ) continue ;
//距离加一
dist[x][y] = dist[tmp.x][tmp.y] + 1 ;
if( g[x][y] == 'E') return dist[x][y] ;
//填充队列
q.push({x,y}) ;
}
}
return -1 ;
}
数论
欧几里得算法
- 理论基础：
（a,b） == (a , a % b ) return b ? gcd(b,a% b):a;
更相减损术的变形
朴素的更相减损术是用来求最大公约数的，但效率是线性的，比欧几里得算法效率低很多。然而该算法经过改造变形，可以得到新的功能。
即，输入 和
，将返回
LL gcd_sub(LL a, LL b)
{
if (a < b) swap(a, b); // 保证a > b
if (b == 1) return a;
return gcd_sub(b, a / b);
}
算术基本定理
每个==大于1的自然数均可写为质数的积==，而且这些素因子按大小排列之后，写法仅有一种方式。
线性筛素数
- 见理论整理文件。 线筛.pdf
void get_prm(int n)
{
for(int i = 2 ; i <= n ; i ++ )
{
if(!st[i])
{
minp[i] = i ;
prm[cnt++] = i ;
}
for(int j = 0 ; i * prm[j] <= n ; j ++ )
{
int t = prm[j] * i ;
st[prm[j] * i ] = 1 ;
minp[t] = prm[j] ;
if(i % prm[j] == 0 ) break;
}
}
}
/*
最后可以得到
prm数组 ， 记录1-n中素数分别是多少
minp数组， minp[i] 记录i的最小质因子是多少
*/
分解质因数
- 和get_prm() 搭配使用 ， 建议直接背过。
//对x分解
int k = 0 , tol = 0 ; // k是索引，tol记录一共有多少个质因数
while(x > 1)
{
int p = minp[x] ; // 取出最小的质因数
fac[k] = p , sum[k] = 0;
while(x % p == 0 )
{
x /= p;
sum[k] ++ ; // p的质因数个数
tol ++ ;
}
k ++ ; //索引加一
}
/*
最后可以得到
fac数组，记录x有什么质因子
sum数组，记录每一个质因子有几个
tol ，一共有多少个质因子
*/
约数个数基本定理
=
, 其中
为质因子的指数。
约数之和基本定理
=
质数定理（用来大致评估时间复杂度）
见百度
裴蜀定理
若设a,b是整数，则存在整数x,y，使得，(a,b)代表最大公因数，则设a,b是不全为零的整数，则存在整数x,y，使得
有以下有用的结论：
-
==那么如果
时 ，a与b不能凑出来的最大数是
==
2.如果给出n个数字，求算凑不出来的数字是多少，就是完全背包问题了。
#include<bits/stdc++.h>
using namespace std ;
const int N = 10010 ;
int n ;
int a[110] , f[110][N] ;
int gcd(int a, int b)
{
return b ? gcd(b , a%b) : a ;
}
int main()
{
cin >> n ;
int d ;
for(int i = 1 ; i <= n ; i ++ )
{
scanf("%d",&a[i]) ;
d = gcd(d , a[i]) ;
}
if(d != 1 ) // 如果最大公因数不是1，肯定有无限个数字无法表示
{
puts("INF") ;
}
else// 如果最大公因数是1 ， 就做一遍完全背包
{
f[0][0] = 1 ;
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 0 ; j < N; j ++ )
{
f[i][j] = f[i-1][j] ;
if(j >= a[i]) f[i][j] |= f[i][j-a[i]];
}
}
int res = 0 ;
for(int i = 0 ; i < N ; i ++)
{
if(!f[n][i]) res ++ ;
}
cout << res <<endl;
}
return 0 ;
}
扩展欧几里得算法
- 用来解决裴蜀定理，求解系数
int exgcd(int a ,int b , int &x ,int &y)
{
if(!b)
{
x = 1 ;
y = 0 ;
return a ;
}
int d = exgcd(b,a%b,y,x) ;
y -= a /b * x ;
return d ;
}
组合数
组合数初级(杨辉三角)
快速递推组合数,处理2000以内没有问题
//将c数组预处理成杨辉三角
for (int i = 0; i < N; i ++ )
{
for (int j = 0; j <= i; j ++ )
{
if (!j) c[i][j] = 1;
else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
组合数中级（快速幂求逆元）
处理
级别的组合数问题
需要预处理阶乘和阶乘的逆元
#include<bits/stdc++.h>
using namespace std ;
const int N = 1E5+10 , mod = 1e9+7 ;
int fc[N] , ifc[N] ;
int qmi(int a ,int b )
{
int res = 1 % mod ;
while(b)
{
if(b&1) res = res *1ll*a % mod ;
a = a * 1ll * a % mod ;
b >>= 1 ;
}
return res ;
}
int main()
{
fc[0] = ifc[0] = 1 ;
for(int i= 1 ; i <N ; i ++ )
{
fc[i] = fc[i-1] * 1ll *i % mod ;
ifc[i] = ifc[i-1] * 1ll * qmi(i , mod -2 ) % mod ;
}
int n;
cin >> n ;
for(int i = 0 ; i < n ; i ++ )
{
int a , b ;
scanf("%d%d",&a,&b) ;
printf("%d\n",fc[a] * 1ll * ifc[b] % mod * ifc[a-b] % mod) ;
}
return 0 ;
}
组合数高级(Lucas定理)
单独命题的话，极可能是单独考察数学知识，不太可能和其他题目组合。
略
DP
AcWing1050 鸣人的影分身（线性）^ 线性Dp
在火影忍者的世界里，令敌人捉摸不透是非常关键的。
我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 M，他影分身的个数最多为 N，那么制造影分身时有多少种不同的分配方法？
注意：
- 影分身可以分配0点能量。
- 分配方案不考虑顺序，例如：M=7,N=3，那么 (2,2,3)和 (2,3,2) 被视为同一种方案。
思路: i 枚举需要的能量，j 枚举分身个数。
#include<bits/stdc++.h>
using namespace std ;
const int N = 15;
int T ;
int m , n ;
int f[N][N] ;
int main()
{
cin >>T ;
while(T--)
{
scanf("%d%d",&m,&n) ;
f[0][0] = 1 ;
for(int i = 0 ; i <= m ; i ++ )
{
for(int j = 1 ; j <= n ; j ++ )
{
f[i][j] = f[i][j - 1] ;
// 每次必定可以有一个0能量的分身，所以f[i][j] 可以从f[i][j-1] 转化来
// 如果新的分身不是0能量的 ， f[i][j] 的方案数 其实包含 f[i-j][j]
// 也就是把每个分身的能量减一 ， 把一个子集映射成已经求解的子集去
if(i >= j ) f[i][j] += f[i-j][j] ;
}
}
cout << f[m][n] <<endl;
}
return 0 ;
}
AcWing1222 密码脱落（区间）^ 区间Dp
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
思路：运用了集合覆盖思想，适用于求最值。
#include<bits/stdc++.h>
using namespace std ;
const int N = 1010 ;
string str ;
int f[N][N] ;
int main()
{
cin >> str ;
int n = str.length() ;
for(int len = 1 ; len <= n ; len ++ )
{
for(int l = 0 ; l + len - 1 < n ; l ++ )
{
int r = l + len -1 ;
if(len == 1) f[l][r] = 1 ;
else
{
if(str[l] == str[r] ) f[l][r] = f[ l +1 ][r -1 ] + 2 ;
f[l][r] = max(f[l][r] , f[l +1 ][r ]) ;
f[l][r] = max(f[l][r] , f[l ][r -1 ]) ;
}
}
}
cout << n - f[0][n-1] << endl;
return 0 ;
}
模板部分
memset(f,0,sizeof f);//初始dp数组
for(int len = 1 ; len <= n ; len ++ ){//枚举区间长度
for(int l = 0 ; l + len - 1 < n ; l ++){//枚举区间的起点
int r = l + len -1 ;//根据起点和长度得出终点
if(r>n) break;//符合条件的终点
for(int k=l;k<=r;++k)//枚举最优分割点
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+w[l][r]);//状态转移方程
}
}
Acwing 1220. 生命之树（树形）^ 树形Dp
在X森林里，上帝创建了生命之树。
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。
在这个前提下，上帝要使得 SS 中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。
经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。
但是由于 atm 不擅长计算，他不知道怎样有效的求评分。
他需要你为他写一个程序来计算一棵树的分数。
==简单来说就是求连通块的最大权值==
思路：关键是存图，递归。抓住状态转移是传递性的。
#include<bits/stdc++.h>
using namespace std ;
const int N = 1E5+ 10 , M = 2*N ;
typedef long long LL ;
int n ;
LL f[N] ;
int w[N] ,h[N], e[M] ,ne[M] , idx ;
void add(int a ,int b )
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
void dfs(int u , int a)
{
f[u] = w[u] ;
for(int i = h[u] ; ~i ; i = ne[i])
{
int j = e[i] ;
if(j != a)
{
dfs(j , u ) ;
f[u] += max(0ll, f[j]) ;
}
}
}
int main()
{
memset(h ,-1,sizeof h );
cin >> n ;
for(int i = 1 ; i <= n ; i ++ )
{
scanf("%d",&w[i]) ;
}
for(int i = 0; i < n-1 ; i ++ )
{
int a,b ;
scanf("%d%d",&a,&b) ;
add(a,b) , add(b,a) ;
}
dfs(1,-1) ;
LL res = f[1] ;
for(int i = 2 ; i <= n ; i ++ ) res = max(res , f[i]) ;
cout << res << endl;
return 0 ;
}
疑难杂题
并查集的另类用法
日期类题目
- 判断日期是否合法
int months[13] ={0,31,28,31,30,31,30,31,31,30,31,30,31} ;
bool check(int year , int month , int day )
{
if(month == 0 || month > 12 ) return 0 ;
if(day == 0 ) return 0 ;
if(month != 2 )
{
if(day > months[month]) return 0 ;
}
else
{
int leap = year % 4 == 0 && year % 100 || year %400 == 0 ;
if(day > months[month] + leap) return 0 ;
}
return 1 ;
}
int main()
{
//枚举日子
for(int date = 19600101 ; date <= 20591231 ; date ++)
{
int year = date /10000 , month = date % 10000 / 100 ,day = date % 100 ;
if(check(year , month , day))
{
//题目需要的操作/
}
}
}
-
刁钻的输入
这里重点学习
sscanf的用法#include<bits/stdc++.h> using namespace std ; int get_seconds(int h , int m , int s ) { return h * 3600 + m * 60 + s ; } int get_time() { string line ; getline(cin , line ) ; if(line.back() != ')' ) line += " (+0)" ; int h1 , m1 , s1 , h2, m2, s2 , d ; sscanf(line.c_str() , "%d:%d:%d %d:%d:%d (+%d)" , &h1,&m1,&s1 , &h2,&m2,&s2 , &d) ; return get_seconds(h2,m2,s2) - get_seconds(h1,m1,s1) + d *24*3600 ; } int main() { int n ; scanf("%d",&n) ; getchar() ; while(n--) { int time = (get_time() + get_time() ) /2 ; int hour = time / 3600 , minute = time % 3600 / 60 , second = time % 60 ; printf("%02d:%02d:%02d\n" , hour , minute , second ) ; } return 0 ; }
- 按照==月份==来枚举==星期==
十三号星期五真的很不常见吗？
每个月的十三号是星期五的频率是否比一周中的其他几天低？
请编写一个程序，计算 N 年内每个月的 1313 号是星期日，星期一，星期二，星期三，星期四，星期五和星期六的频率。
测试的时间段将会开始于
年 11 月 11 日，结束于
年 12 月 31日
输出格式：
共一行，包含七个整数，整数之间用一个空格隔开，依次表示星期六，星期日，星期一，星期二，星期三，星期四，星期五在十三号出现的次数。
#include<bits/stdc++.h>
using namespace std ;
int n ;
int months[] = {0,31,28,31,30,31,30,31,31,30,31,30,31} ;
int weekdays[7] ;
int main()
{
cin >> n ;
int day = 0 ;
for( int year = 1900 ; year < 1900 +n ; year ++ )
{
for(int month = 1 ; month < 13 ; month ++)
{
weekdays[(day + 12 )% 7] ++ ;
day += months[month] ; // 只维护day
if(month == 2)
{
day += (year % 400 == 0 || year % 100 && year % 4 == 0 ) ;
}
}
}
for(int i = 5 , j = 0 ; j < 7 ; i = (i+1) % 7 , j ++)
{
printf("%d ",weekdays[i] ) ;
}
return 0 ;
}
4.按==日子==枚举==星期==（比枚举月份慢）
题目如上
#include<bits/stdc++.h>
using namespace std ;
int n ;
int months[] = {0,31,28,31,30,31,30,31,31,30,31,30,31} ;
int weekdays[7] ;
int get(int year , int month )
{
if(month != 2)
{
return months[month] ;
}
else
{
return 28 + (year % 400 == 0 || year % 100 && year % 4 == 0 ) ;
}
}
int main()
{
cin >> n ;
int week = 0 ;
int year = 1900 , month = 1 , day = 1 ;
while(year < 1900 + n )
{
if(day == 13 ) weekdays[week] ++ ;
week = (week + 1 ) % 7 ; // 实时更新week和day
day ++ ;
if(get(year ,month) < day) day = 1 , month ++ ; // 按需更新month和day
if(month > 12) year ++ , month =1 ; // 按需更新year和month
}
for(int i = 5 , j = 0 ; j < 7 ; i = (i+1) % 7 , j ++)
{
printf("%d ",weekdays[i] ) ;
}
return 0 ;
}
基础算法
求逆序对（归并）
利用归并的思想，和归并排序的代码基本没有区别.
以下是void返回类型的代码。
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 1E5+10 ;
int q[N] ;
int tmp[N] ;
LL res ;
void merge(int q[] , int l ,int r )
{
if(l >= r ) return ;
int mid = l + r >> 1 ;
merge(q ,l,mid) , merge(q ,mid +1 ,r) ;
int i = l , j = mid + 1 , k = 0 ;
while(i <= mid && j <= r)
{
if(q[i] <= q[j] ) tmp[k++] = q[i++] ;
else
{
tmp[k++] = q[j++] ;
res += mid - i + 1 ; // 核心
}
}
while( i <= mid ) tmp[k++] = q[i++ ] ;
while( j <= r ) tmp[k++] = q[j++ ] ;
for(int i = l , j = 0 ; i <= r ; i ++ , j ++ ) q[i] = tmp[j] ;
}
int main()
{
int n ;
cin >> n ;
for(int i = 0 ; i < n ; i ++ ) scanf("%d",&q[i]) ;
merge(q,0,n-1) ;
cout << res << endl;
return 0 ;
}
总结：
前缀和的代码更好理解，只需要开个数组，背个公式，直接出来了
差分的代码需要写个函数，特地构造一下。构造思路是和前缀和反过来的。
前缀和思想是“考虑前面”，该减减，该加加。（结合一维二维原理图）
差分的思想是“考虑后面”，该减减，该加加。（结合一维二维原理图）
形成了一个如下的关系：
差分数组 <----> 原生数组 <----> 前缀和数组
一维前缀和模板
输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l, r。
对于每个询问，输出原序列中从第l个数到第r个数的和。
//s数组是a数组的前缀和
for(int i = 1 ; i <= n ; i ++ )
{
s[i] = s[i-1] + a[i] ; // 或者a[i] += a[i-1] ; 把a自己变成自己的前缀和
}
一维差分模板
输入一个长度为n的整数序列。
接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
//构造a的差分数组b
void insert(int l ,int r ,int x)
{
b[l] += x ;
b[r+1] -= x ;
}
//还原数组a，并输出数组a
for(int i= 1 ; i <= n ; i ++ )
{
a[i] = a[i-1] + b[i] ; // 这也是b的定义 a[i] = b[1] + b[2] + b[...] + b[i]
cout << a[i] << " " ;
}
------------------------------------------------------------------
//把源数组变成自己的差分
//方式1 ： 回倒法
for(int i = n ; i ; i --)
{
b[i] -= b[i-1] ;
}
//方式2 ： 封装函数
for(int i = 1 ; i <= n ; i ++ )
{
int tmp ;
cin >> tmp ;
insert(b,i,i,tmp) ;
}
//我提这两种方式的原因是想提起注意，差分的构造不可以在读取数据后直接在原数组构造，这和前缀和不一样！！！
二维前缀和
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
//s数组是a数组的前缀和
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= m ; j ++)
{
s[i][j] = s[i-1][j] + s[i][j-1] - s[i - 1][j - 1] + a[i][j] ;
}
}
二维差分模板
输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上c。
请你将进行完所有操作后的矩阵输出。
//构造a数组的差分矩阵b
void insert(int x1 , int y1 , int x2 , int y2 , int x)
{
b[x1][y1] += x ;
b[x2 +1][y1] -= x ;
b[x1][y2 + 1] -= x ;
b[x2 +1 ][y2 +1 ] += x ;
}
//还原a数组，并输出a的元素
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= m ; j ++ )
{
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j] ; // b的定义
cout << a[i][j] << " " ;
}
puts("");
}
求树的直径
树的直径：树中所有最短路径距离的最大值即为树的直径
思路： 随便找一个点，求一遍最远路，得到最远点v，从v出发再求一遍最远路，得到的就是树的直径。
//在树的背景下，从任意一点出发，计算其他点到该点的距离
//（这种路径是唯一的，所以dist也可以看成是“最短路”）
void dfs(int u , int father , int dis)
{
dist[u] = dis ;
for(int i = h[u] ; ~i ; i = ne[i])
{
int j = e[i] ;
if( j != father)
{
dfs(j,u,dist[u] + w[i]) ;
}
}
}
RMQ问题
1.ST算法 (所需时间是线段树时间的一半)
2.简单的线段树（略）
// 注意一点：初始数据的读入，下标从1开始
void st_rmq()
{
for(int j = 0 ; j < M ; j ++ )
{
for(int i = 1 ; i +(1 << j) -1 <= n ; i ++ )
{
if(!j) f[i][j] = w[i] ;
else f[i][j] = max(f[i][j -1 ] , f[i+(1 << j -1 )][j -1]) ;
}
}
}
int query(int l , int r)
{
int k = log(r - l +1) / log(2) ;
return max(f[l][k] , f[r - ( 1 << k ) +1 ][k]) ;
// f[r - ( 1 << k ) +1 ][k] 要注意一下，第一维最后加一千万别忘了
}
模拟散列表
- 开放寻址
- 拉链
//开放寻址
//返回值k有两种含义 1.若存在，就返回存放地址 2. 若不存在，就返回将要存放的地址
int find(int x)
{
int k = (x% N + N)% N ;
while(h[k] != null && h[k] != x)
{
k ++ ;
if(k == N ) k = 0 ;
}
return k ;
}
// 拉链法
//需要两个函数搭配使用，一个是添加函数， 一个是查询函数
void add(int a)
{
int k = (a % N + N) % N ;
e[idx] = a , ne[idx] = h[k] , h[k] = idx ++ ;
}
bool query(int a)
{
int k = (a % N + N) % N ;
for(int i = h[k] ; ~i ; i = ne[i])
{
int j = e[i] ;
if(j == a)
{
return 1 ;
}
}
return 0 ;
}
以上两种任选。
杨辉三角(解决2000以内的组合数问题)
快速递推组合数,用于预处理
//将c数组预处理成杨辉三角
for (int i = 0; i < N; i ++ )
{
for (int j = 0; j <= i; j ++ )
{
if (!j) c[i][j] = 1;
else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
二叉树思想解决一般递归问题
考虑一种简单的正则表达式：
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。
- ACwing 正则问题具有代表性
#include<bits/stdc++.h>
using namespace std ;
int k ;
string str ;
int dfs()
{
int res = 0 ;
while(k < str.size())
{
if(str[k] == '(')
{
k ++ ;
res += dfs() ;
k ++ ;
}
else if(str[k] == '|')
{
k ++ ;
res = max(res , dfs()) ;
}
else if(str[k] == ')' )
break;
else
{
k ++ ;
res ++ ;
}
}
return res ;
}
int main()
{
cin >> str ;
cout << dfs() << endl;
return 0 ;
}
十进制向任意进制转化
使用短除法
// n : 待转化的数字
// k : 进制基数
char get(int n )
{
if( n <= 9) return n + '0' ;
if(n>= 10) return n -10 +'A' ;
}
string base(int n , int k )
{
string num ;
while(n) num += get(n % k) , n /= k ;
reverse(num.begin() , num.end());
return num ;
}
秦九韶算法，其他进制向十进制转化
int uget(char c) // char -> int
{
if(c <= '9') return c-'0' ;
return c-'A' +10 ;
}
//秦九韶 ， 把任意k进制化成十进制
int base10(string num ,int k)
{
int res = 0 ;
for(auto c : num)
{
res = res * k + uget(c) ;
}
return res ;
}
a进制化成b进制（直接转化）
未完待续
string回文判断
string tmp = num ;
reverse(num.begin() , num.end()) ;
if( tmp == num)
{
// 是回文
}
/**
判断数字是否是回文
可以使用to_string()将其转化成string，再通过reverse判断
实数二分和整数二分的习题对比
两道题目的例题背景类似：
求解最优化问题，直接求解很困难， 可以将其转化成一个 ==判定== 问题 ， 在答案的取值范围内搜寻答案即可。
//实数二分
double l = 0 , r = 1e9 ;
while( r - l > 1e-4)
{
double mid = (r + l)/2 ;
if(check(mid)) l = mid ;
else r = mid ;
}
//整数二分
// 找左边界
int l = 1, r = 1e5;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid; // 答案在右边，把l向右推
else r = mid - 1;
}
// 找右边界
int l = 1 , r = 1e5 ;
while(l < r)
{
int mid = l + r >> 1 ;
if(check(mid)) r = mid ; // 答案在左边，把r向左推
else l = mid +1 ;
}
区间合并
区间合并不是指区间真的合并在一起，严格来讲，他只是一种比较聪明的区间枚举方式（区间满足有序）
sort(sg , sg + n) ;
int sum = 0 ;
int L = sg[0].x , R =sg[0].y ;
for(int i = 1 ; i < n ; i ++)
{
if(sg[i].x <= R) R = max(sg[i].y , R) ; // 区间有重叠，更新右端点
else
{
sum += R-L+1 ; // 区间长度累加
L= sg[i].x , R = sg[i].y ; // 新区间没重叠，全部更新
}
}
sum += R - L + 1 ; // 最后一段更新的区间在循环外更新
//sum累加不重合的区间总共长度
从对称矩阵的角度去遍历二维数组矩阵
for(int i = 1 ; i <= n ; i ++ ) // 遍历行
{
for(int j= i , k = 1 ; j <= n ; j ++ , k++ )
{
a[i][j] = k ;
a[j][i] = k ;
}
}
// 注意i，j的变化
N皇后问题
给定一个 N×NN×N 的棋盘，请你在上面放置 NN 个棋子，要求满足：
- 每行每列都恰好有一个棋子
- 每条对角线上都最多只能有一个棋子
#include<bits/stdc++.h>
using namespace std ;
const int N = 15 ;
int ans , n ;
int path[N] ;
bool col[N],dg[N*2],udg[N*2] ;
void dfs(int x)
{
if(x > n )
{
ans ++ ;
if(ans <=3) // 将前三个答案输出
{
for(int i = 1 ; i <= n ; i ++ )
{
printf("%d ",path[i]) ;
}
cout << endl;
}
}
for(int y = 1 ; y <= n ; y ++ ) // 遍历列
{
if(!col[y] && !dg[x+y] && !udg[x-y+n])
{
path[x] = y ;
col[y] = dg[x+y] = udg[x-y+n] = 1 ;
dfs(x+1) ;
path[x] = 0 ;
col[y] = dg[x+y] = udg[x-y+n] = 0 ;
}
}
}
int main()
{
cin >> n ;
dfs(1) ;
cout <<ans << endl;
return 0 ;
}
手写next_permutation()
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m;
int w[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
while (m -- ) // 从最小字典序的序列算起第m个
{
int k = n;
while (w[k - 1] > w[k]) k -- ; // 从后找到尖峰
int t = k;
while (w[t + 1] > w[k - 1]) t ++ ; // 尖峰到末尾第一个大于w[k-1]的，进行交换
swap(w[k - 1], w[t]);
reverse(w + k, w + n + 1); // 尖峰到最后逆置
}
for (int i = 1; i <= n; i ++ ) cout << w[i] << ' ';
cout << endl;
return 0;
}
/**
while (m -- ) // 从最小字典序的序列算起第m个
{
int k = n;
while (w[k - 1] > w[k]) k -- ; // 从后找到尖峰
int t = k;
while (w[t + 1] > w[k - 1]) t ++ ; // 尖峰到末尾第一个大于w[k-1]的，进行交换
swap(w[k - 1], w[t]);
reverse(w + k, w + n + 1); // 尖峰到最后逆置
}
等价于
while (m -- ) // 从最小字典序的序列算起第m个
{
next_permutation(w+1 , w+n+1) ; // w下标从1开始的
}
*/
Trie树
维护一个字符串集合，支持两种操作：
- “I x”向集合中插入一个字符串x；
- “Q x”询问一个字符串在集合中出现了多少次。
共有N个操作，输入的字符串总长度不超过
模型1：存储字符串
#include<bits/stdc++.h>
using namespace std ;
const int N = 100010 ;
int tr[N][26] ,cnt[N] , idx ;
char str[N] ;
void insert()
{
int p = 0 ;
for(int i = 0 ; str[i] ; i++ )
{
int u = str[i] - 'a' ;
if(!tr[p][u]) tr[p][u] = ++ idx ;
p = tr[p][u] ;
}
cnt[p] ++ ;
}
int query()
{
int p = 0 ;
for(int i = 0 ; str[i] ; i ++ )
{
int u = str[i] - 'a' ;
if(!tr[p][u]) return 0 ;
p = tr[p][u] ;
}
return cnt[p] ;
}
int main()
{
int n ;
cin >> n ;
while(n-- )
{
char op[2] ;
cin >> op >> str ;
if(*op == 'I') insert() ;
else cout << query() << endl;
}
return 0 ;
}
模型2 ：存储数字的二进制形式
#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5+10 , M = 21* N;
int n ;
int s[N] ;
int son[M][21] , bound[M] , idx;
void insert(int x , int l ) // insert函数是大同小异的
{
int p = 0 ;
for(int i = 20 ; i >= 0 ; i --) // 最大数字的二进制形式是20位的
{
int u = x >> i & 1 ;
if(!son[p][u]) son[p][u] = ++idx ;
p = son[p][u] ;
}
bound[p] = l ;
}
int query(int x) // query是因题而异的
{
int p = 0 ;
for(int i = 20 ; i >= 0 ; i --)
{
int u = x >> i & 1 ;
if(son[p][!u]) p =son[p][!u] ;
else p = son[p][u] ;
}
return bound[p] ;
}
int main()
{
cin >> n ;
for(int i = 1 ; i <= n ; i ++ )
{
scanf("%d",&s[i]) ;
s[i] ^= s[i-1] ;
}
insert(s[0] , 0) ;
int res = -1 , l , r ;
for(int i =1 ; i <= n ; i ++ )
{
int left = query(s[i]) ;
int t = s[i] ^ s[left] ;
if(t > res)
{
res = t ;
l = left +1 ;
r = i ;
}
insert(s[i] , i ) ;
}
printf("%d %d %d\n" , res , l,r ) ;
return 0 ;
}
快速幂模板
int qmi(int m, int k, int p)
{
int res = 1 % p;
while (k)
{
if (k&1) res = res * 1ll *m % p;
m = m *1ll*m % p; //注意：m随着循环的进行实时更新是很重要的，即使当次循环没用上
k >>= 1;
}
return res;
}
图形哈希
图形hash就是对给定图内的连通块进行hash
大致思想是：组成连通块的点坐标记录进q数组里面；然后以
的组合计数方式，计算q数组每一个pair坐标的欧几里得距离之和。和，作为这个连通块的hash值。具体参见星空之夜这种hash方法直接背过。
double get_dist(PII a , PII b ) // 欧几里得距离计算函数
{
double dx= a.x - b.x ;
double dy = a.y - b.y ;
return sqrt(dx * dx + dy * dy) ;
}
double get_sh() // hash 函数
{
double sum = 0 ;
for(int i = 0 ; i < cnt ; i ++ )
{
for(int j = i +1 ; j < cnt ; j ++ )
{
sum += get_dist(q[i],q[j]) ;
}
}
return sum ;
}
二维四连通遍历技巧
dx[] = {1,-1,0,0} ;
dy[] = {0,0,1,-1} ;
for(int i = 0 ; i < 4 ; i ++ )
{
int a = x + dx[i] ;
int b = y + dy[i] ;
/**....*/
}
八连通遍历技巧
/**
x , y 是初始的坐标
*/
for(int i = x-1 ; i <= x +1 ; i++)
{
for(int j = y -1 ; j <= j+1 ; j ++ )
{
if(i==x && j== y) continue ;
/**...*/
}
}
求逆元
单独出题本质上考察快速幂
更多是和其他条件组合出题。
注意：请返回在0∼p−1之间的逆元。a有逆元的充要条件是a与p互质
#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int qmi(int a , int k ,int p)
{
int res = 1 ;
while(k)
{
if( k&1) res = (LL)res * a % p;
a = (LL) a*a % p ;
k >>= 1 ;
}
return res ;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int a, p;
scanf("%d%d",&a,&p) ;
int res = qmi(a,p-2,p) ;
if(a%p) printf("%d\n", res );
else puts("impossible");
}
return 0;
}
语法拾遗
//结构体排序
struct st // 按照sum由大到小，ch由大到小，id由小到大排序，放在重载小于号中
{
int id , ch , mth , eg ;
int sum ;
bool operator< (const st &t) const
{
if(sum != t.sum) return sum > t.sum ;
else if( ch != t.ch) return ch > t.ch ;
else if(id != t.id) return id < t.id ;
}
}stu[N] ;
//自定义cmp(不想用)
// lambda表达式 ，c++17 ，考试恐怕用不了
sort(stu , stu + n ,[](st &a,st &t){
if(a.sum != t.sum) return a.sum > t.sum ;
else if( a.ch != t.ch) return a.ch > t.ch ;
else if(a.id != t.id) return a.id < t.id ;
}) ;
心得体会
完全背包存在一个项替代n项的时间优化问题
空间 上，和01背包一样去掉第一维，修改第二层for循环。
值得注意的是，01背包和完全背包修改for循环有不同
根据他们的状态转移方程的不同
01背包状态转移需要使用上一层的信息，动用了滚动数组，因此会从大到小循环
完全背包优化后的状态转移方程只使用当前层的信息，优化一维之后还是从小到大循环不变
2021.2.2
在有一个模数mod的计算背景下，a / b 同余mod ，相当于a * x 同余mod 。 x就是b模mod的乘法逆元（跟a的关系不大）
比如在计算十万级别的组合数可以看到逆元的应用 ：
mod的存在相当于将数轴连成了一个环。
如果模数mod足够大，那么，在参与计算的数字规模不大的情况下，计算出的结果一般就和我们一般理解的无异。
六字真言：模数mod==随便模，随时模==
一般情况下mod越大，逆元越大。事实上，某数对mod的逆元超级大。
2021.2.5
DP专题
数字三角形模型
题目特点：
描述了一个地图，从左上角通过向下和向右方走，走到右下角。途中经过地图的方格，每个方格有自己价值或者是权值。求，途径的权值之和的==最大值==。
代码如下：
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= m ; j ++ )
{
scanf("%d", &g[i][j]) ; // 读入地图的格点权值
}
}
// 核心代码
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= m ; j ++ )
{
// 上一行 左一列 当前格点权值
f[i][j] = max(f[i-1][j] , f[i][j-1]) + g[i][j] ;
}
}
简单变形：（本质区别是，求最小值）
穿过一个N×N的正方形的网格
从网格的左上角进，右下角出。
==每穿越中间1个小方格，都要花费1个单位时间。==必须在(2N-1)个单位时间穿越出去。(这是在暗示不可以走回头路)
而在经过中间的每个小方格时，都需要缴纳一定的费用。
期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）
与求最大值的区别是：需要初始化f数组
// f数组的第0列和第0行边界初始化为最大值，这样保证f的第1行和第1列只会使用合法值
for(int i = 0 ; i <= n ; i ++ )
{
f[0][i] = 0x3f3f3f3f ;
f[i][0] = 0x3f3f3f3f ;
}
f[1][1] = g[1][1] ;
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= n ; j ++ )
{
if(i != 1 || j != 1 ) // 第一个格子不需要状态转移,直接初始化就好了
{
f[i][j] = min(f[i-1][j] , f[i][j-1]) + g[i][j] ;
}
}
}
最长上升子序列模型
模型基本描述：
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。
DP做法时间复杂度是
#include<bits/stdc++.h>
using namespace std ;
const int N = 1E3+10 ;
int n ;
int s[N] , f[N] ;
int main()
{
cin >> n ;
for(int i = 0 ; i < n; i ++ )
{
scanf("%d",&s[i]) ;
}
int res = -1 ;
for(int i = 0 ; i < n ; i ++ )
{
f[i] = 1 ;
for(int j = 0 ; j < i ; j++ )
{
if(s[i]>s[j])
{
f[i] = max(f[i] , f[j] + 1) ;
res = max(res , f[i]) ;
}
}
}
cout << res << endl;
return 0 ;
}
核心代码
int res = -1 ;
for(int i = 0 ; i < n ; i ++ )
{
f[i] = 1 ;
for(int j = 0 ; j < i ; j++ )
{
if(s[i]>s[j])
{
f[i] = max(f[i] , f[j] + 1) ;
res = max(res , f[i]) ;
}
}
}
小扩展：怪盗基德的滑翔翼
求两个方向上的最长上升子序列问题，只需正向和反向都求解就max即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 110 ;
int n ;
int a[N] ;
int f[N] ;
int main()
{
int T ;
scanf("%d",&T) ;
while(T--)
{
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++ )
scanf("%d",&a[i]) ;
int res = 0 ;
for(int i = 1 ; i <= n ; i ++ )
{
f[i] = 1 ;
for(int j = 1 ; j < i ; j ++ )
{
if(a[i] > a[j])
{
f[i] = max(f[i],f[j] + 1) ;
}
}
res = max(f[i] , res ) ;
}
for(int i = n ; i ; i -- )
{
f[i] = 1 ;
for(int j = n ; j > i ; j -- )
{
if(a[i] > a[j])
{
f[i] = max(f[i],f[j] + 1) ;
}
}
res = max(f[i] , res ) ;
}
printf("%d\n",res ) ;
}
return 0 ;
}
背包模型
状态机模型
状态压缩模型
区间模型
树形模型
数位模型
单调队列优化模型
斜率优化模型
搜索专题
Flood Fill
flood fill 有宽搜和深搜两种实现方式，但是稳妥起见，我青睐宽搜的实现。因为宽搜在我看来业已成熟。
红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
char g[N][N];
bool st[N][N];
int res;
int dx[] = {1,-1, 0, 0};
int dy[] = {0, 0, 1, -1};
int bfs(PII sr)
{
queue<PII> q ;
q.push(sr) ;
st[sr.x][sr.y] = 1;
res++;
while (q.size())
{
auto t = q.front() ;
q.pop() ;
for (int i = 0; i < 4; i++)
{
int a = t.x + dx[i], b = t.y + dy[i];
// 过滤
if (a < 0 || a >= n || b < 0 || b >= m)
continue;
if (st[a][b])
continue;
if (g[a][b] == '#')
continue;
// 状态更新
res++;
st[a][b] = 1;
//填充队列
q.push({a, b});
}
}
return res;
}
最短路模型
多源广搜
最小步数模型
双端队列广搜
双向广搜
DFS连通性模型
DFS搜索顺序
DFS剪枝优化
迭代加深
//框架
type dfs(int depth , type others)
{
if(!depth) //当前允许搜索的层数为0，就立即回溯
return (type)sth ;
/**other body*/
dfs(depth -1 , other sth)
}
int main()
{
int depth = 0 ; // 全局最大搜索层数为m
while(depth < m && dfs(depth, sth)) depth ++ ;
}
双向深搜
迭代加深和估价函数结合的算法，有优异的表现。
简单例题参考 acwing1243 糖果
例题核心代码
int lowbit(int x) // 返回最低位的1 ， 这不在IDA*的框架里
{
return x & -x ;
}
int h(int state) // 估价函数
{
int res = 0 ;
for(int i = (1 <<m ) -1 - state ; i ; i -= lowbit(i))
{
int c = log_2[lowbit(i)] ;
res ++ ;
for(auto r : col[c]) i &= ~r ;
}
return res ;
}
bool dfs(int depth , int state) // 迭代加深的深搜
{
if(!depth || h(state) > depth) return state == (1<<m) -1 ;
// 找到被选择最少的一列
int t = -1 ;
for(int i = (1 <<m ) -1 - state; i ; i -= lowbit(i))
{
int c = log_2[lowbit(i)] ;
if(t == -1 || col[t].size() > col[c].size())
{
t = c ;
}
}
//枚举选哪一行
for(auto r : col[t])
{
if(dfs(depth -1 , state | r))
return 1 ;
}
return 0 ;
}
int main()
{
/**other*/
//以下是迭代加深
int depth = 0 ;
while(depth <= m && !dfs(depth,0)) depth ++ ;
/**other*/
}
图论
单源最短路建图方式
单源最短路综合应用
单源最短路扩展应用
Floyd
最小生成树
最小生成树的扩展
负环
差分约束
最近公共祖先
有向图的强连通分量
无向图的双连通分量
二分图
一个图 ==是二分图==
等价于 ==不存在奇数环==
等价于 ==染色法不存在矛盾==
染色法
bool dfs(int u ,int c)
{
clr[u] =c ;
for(int i = h[u] ;~i ; i = ne[i])
{
int j = e[i] ;
if(!clr[j])
{
if(!dfs(j , 3-c , mid) ) return 0 ;
}
else
{
if(clr[j] == c ) return 0 ;
}
}
return 1 ;
}
欧拉回路和欧拉路径
拓扑排序
数据结构专题
并查集
树状数组
线段树
线线段树 + 扫描线（无懒标记）
X星球的一批考古机器人正在一片废墟上考古。
该区域的地面坚硬如石、平整如镜。
管理人员为方便，建立了标准的直角坐标系。
每个机器人都各有特长、身怀绝技。
它们感兴趣的内容也不相同。
经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。
矩形的表示格式为 (x1,y1,x2,y2)，代表矩形的两个对角点坐标。
为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。
小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。
其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。
注意，各个矩形间可能重叠。
#include<bits/stdc++.h>
using namespace std ;
const int N = 10010 ;
int n ;
struct Segment
{
int x , y1 , y2 ;
int k ;
bool operator < (const Segment &t) const
{
return x < t.x ;
}
}seg[N *2] ;
struct node
{
int l ,r ;
int cnt , len ;
}tr[N *4 ] ;
void pushup(int u)
{
if (tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1;
else if (tr[u].l == tr[u].r) tr[u].len = 0;
else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u , int l , int r , int k )
{
if(tr[u].l >= l && tr[u].r <= r )
{
tr[u].cnt += k ;
pushup(u) ;
}
else
{
int mid = tr[u].l + tr[u].r >> 1 ;
if(l <= mid ) modify(u << 1 , l ,r , k ) ;
if(r > mid ) modify(u << 1 | 1 , l ,r , k ) ;
pushup(u) ;
}
}
int main()
{
scanf("%d",&n ) ;
int m = 0 ;
for(int i = 0 ; i < n ; i++ )
{
int x1 ,y1,x2,y2 ;
scanf("%d%d%d%d",&x1, &y1 , &x2 ,&y2) ;
seg[m++] = {x1 , y1 , y2 , 1} ;
seg[m++] = {x2 , y1 , y2 , -1} ;
}
sort(seg ,seg + m ) ;
build(1,0,10000) ;
int res = 0 ;
for(int i = 0 ; i < m ; i ++)
{
if( i > 0 ) res += tr[1].len * (seg[i].x - seg[i -1 ].x ) ;
modify( 1 ,seg[i].y1 , seg[i].y2 - 1 , seg[i].k ) ;
}
printf("%d\n" , res) ;
return 0 ;
}
