普及组算法汇总
名词
OI: olympiad in informatics 信息学奥林匹克竞赛
IOI: international olympiad in informatics 国际信息学奥林匹克竞赛
NOI: national olympiad in informatics 全国信息学奥林匹克竞赛
NOIP: national olympiad in informatics in province 全国信息学奥林匹克竞赛省赛
CSP: 非专业计算机能力认证 -J, -S。
J: junior: 低级的
S: senior: 高级的
进入提高组复赛，且得分非0的选手可以参加NOIP
CCF: China computer fundation 中国计算机协会
SMTP: 简单邮件传输协议(simple mail transport protocol)
POP3: 邮局协议版本3(Post Office Protocol - Version 3)
IMAP: 交互邮件访问协议（Internet Message Access Protocol)
小知识
面向过程: 只有C语言面向对象: 除了C语言的所有语言(C++, python, Java)
编译型语言和解释型语言编译型语言: C,C++,Pascal解释型语言: python, Java, PHP
计算机系统windows系统类unix系统: 除了windows系统以外的所有系统: android, ios, macOS, linux...
码
原码、反码、补码：8位二进制数表示的有符号整数
最左边一位是符号位(1:负数,0:正数)
反码: 原码的符号位不变，其他位取反
补码: 反码+1
补码:10101011
反码:10101010
原码:11010101
==> -85
-52
原码:10110100
反码:11001011
补码:11001100
运算符
\(x<
\(x>>y=\frac{x}{2^y}\)
| & | 按位与操作，按二进制位进行"与"运算。运算规则： 0&0=0; 0&1=0; 1&0=0; 1&1=1; | (A & B) 将得到 12，即为 0000 1100 |
|---|---|---|
| | | 按位或运算符，按二进制位进行"或"运算。运算规则： 0|0=0; 0|1=1; 1|0=1; 1|1=1; | (A | B) 将得到 61，即为 0011 1101 |
| ^ | 异或运算符，按二进制位进行"异或"运算。运算规则： 0^0=0; 0^1=1; 1^0=1; 1^1=0; | (A ^ B) 将得到 49，即为 0011 0001 |
| ~ | 取反运算符，按二进制位进行"取反"运算。运算规则： ~1=-2; ~0=-1; | (~A ) 将得到 -61，即为 1100 0011，一个有符号二进制数的补码形式。 |
| << | 二进制左移运算符。将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。 | A << 2 将得到 240，即为 1111 0000\(x< |
| >> | 二进制右移运算符。将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。 | A >> 2 将得到 15，即为 0000 1111\(x>>y=\frac{x}{2^y}\) |
\(∨\):或 -> 只要有一个为真，则表达式为真
\(∧\):且 -> 两个都是真才为真，有一个假为假
\(﹃（?）\)：非 -> 假为真，真为假
| 名称（按优先级从高到低） | 符号 | 顺序 |
|---|---|---|
| 后缀 | () [] -> . ++ - - | 从左到右 |
| 一元 | + - ! ~ ++ - - (type)* & sizeof | 从右到左 |
| 乘除 | * / % | 从左到右 |
| 加减 | + - | 从左到右 |
| 移位 | << >> | 从左到右 |
| 关系 | < <= > >= | 从左到右 |
| 相等 | == != | 从左到右 |
| 位与 AND | & | 从左到右 |
| 位异或 XOR | ^ | 从左到右 |
| 位或 OR | | | 从左到右 |
| 逻辑与 AND | && | 从左到右 |
| 逻辑或 OR | || | 从左到右 |
| 条件 | ?: | 从右到左 |
| 赋值 | = += -= *= /= %=>>= <<= &= ^= |= | 从右到左 |
| 逗号 | , | 从左到右 |
数学知识
集合论基础
- 集合：若干个互异无序元素。集合有两种记录方法，如 \(A = \{1,2,3\},T = \{i|i为偶数\}\)
- 空集：没有函数的集合。计作：\(\emptyset\)
- 属于与不属于: 表示一个元素是否属于该集合。如 \(1 \in A, 4 \notin A\)
- 子集：如果集合A中包含集合B中的所有元素，则称B为A的子集。记作 \(B \subset A\)。若A不是B的子集，记为\(A\not\subset B\)。
- 真子集：如果B是A的子集，且B与A并不相等，则称B是A的真子集。记作 \(B \subseteq A\)。若A不是B的真子集，记为\(A\not\subseteq B\)。
- 并 集：字面意思为将两个集合合并后的结果。即如果元素x在集合A或集合B中，那么x在集合A与集合B的并集中。A与B的并集可以记作 $X = A \cup B $
- 交 集：字面意思为两个集合相交的部分。即如果元素x既在集合A中，又在集合B中。那么元素x在集合A与B的交集中。A与B的交集可以记作 \(Y = A \cap B\)。
- 区间：区间是一种特殊的集合，表示一个连续的部分的所有元素。如 \([1,2]、 (4, 5)、 [9, 10)、 (2, +\infty)\)
- 闭区间、开区间与半开半闭区间：
- 用[]表示的是闭区间，表示区间左右两端的元素都在集合中，如\([1,2]\)，1也是集合的一个元素；
- 用()表示的是开区间，表示区间左右两端的元素都不在集合中，如\((4,5)\)，4和5都不在集合中；
- 一边中括号一边小括号的是半开半闭区间，中括号那一端的元素在集合中，小括号那一端的不在集合中。
- 带有无穷符号的区间：有\(+\infty\) 与 \(-\infty\) 。无穷符号那一端的必须是小括号，且正无穷的正号不能省略。
- 几个重要的集合: 实数集：\(\mathbb{R}\) , 自然数集合：\(\mathbb{N}\), 整数集合: \(\mathbb{Z}\), 正整数集合: \(\mathbb{N^+}\)
- 集合与不等式的转化：如 \(1\leq x \leq 10\) 可以写成 \([1,10]\)，\(x \gt 3\) 可以写成 \((3, +\infty)\)
概率论基础
- 事件：一个不受主观意念控制的事情。如“天要下雨”，"彩票中一千万", "CSP初赛全部靠蒙考满分", "明天太阳照常升起"是事件，"我今天吃肯德基", "CSP凭实力0分", "我晚上通宵写代码"不是事件。在概率论中，我们常用一个字母表示一个事件，如事件A为天要下雨。
- 概率：事件发生的可能性。一般用P表示，事件A发生的概率记为P(A) 。
- 频数与频率。在计算一个事件发生的概率时，需要进行多次随机试验。事件发生的次数就是频次，事件发生频次的比例就是频率。如事件A为扔硬币扔出正面。我扔了10次硬币，9次正面，则频次为9，频率为90%。
- 积事件：若事件C为事件A与事件B同时发生，那么事件C就是事件A与事件B的积事件。记为\(C = A \cap B\)，\(P(C) = P(A\cap B) = P(AB)\)
- 独立事件：两个事件的发生没有相关关系，则这两个事件为独立事件。如"今天下雨"与"扔硬币扔出正面"是独立事件。"今天下雨"与"今天空气湿度高于50%"不是独立事件。
- 独立事件的概率：\(P(AB) = P(A) \cdot P(B)\) 。注意只有事件A与B独立该式才成立。
- 和事件的概率：\(P(A+B) = P(A) + P(B) - P(AB)\) 。和事件为两个事件至少发生一个的概率。
- 条件概率：\(P(A|B)\) 表示在B事件发生的条件下，A事件发生的概率。即“如果今天下雨，门口路上堵车的概率。”、“扔一次骰子扔出的数字是偶数，那么扔出的数字是2的概率”。
- 贝叶斯公式：\(P(AB) = P(A|B) \cdot P(B) = P(B|A) \cdot P(A)\)
- 互斥事件：不可能同时发生的事件。如“扔一次骰子扔出1”与“扔一次骰子扔出2”，“扔一次硬币为正面”与“扔一次硬币为反面”。
- 对立事件：其中至少一个会发生的互斥事件。如”扔一次骰子扔出1“与“扔一次骰子扔出2”不是对立事件，“扔一次硬币为正面”与“扔一次硬币为反面”是对立事件。事件\(A\)的对立事件记为\(\bar{A}\)。那么\(P(A)+P(\bar{A}) = 1\)。
- 全概率公式：\(P(A) = P(A|B)\cdot P(B) + P(A|\bar{B}) \cdot P(\bar{B})\)
- 数学期望：随机事件的结果。如果一个随机试验会出现多种结果（或事件）\(X_1, X_2, ...,X_i\)，每种事件可以获得\(V_i\)的收益。那么随机试验\(X\) 的数学期望为 \(E(X) = \displaystyle \sum_{i=1}^nP(X_i)\cdot V_i\)。
平面直角坐标系
- 平面直角坐标系由横轴与纵轴组成。横轴为x轴，纵轴为y轴，点的坐标由括号组成的二元组表示，如(x, y)。
- 点A对x轴作垂线到达的位置为A的横坐标，对y轴作垂线到达的位置为B的纵坐标。
三角函数
-
勾股定理：在直角三角形中，假设三条边长度为 \(a, b, c(a\leq b\lt c)\)。则\(a^2 + b ^ 2= c^2\)。
-
"小角对小边"：在直角三角形中，角度较小的角所对的边较短
-
角度制：一种表示角度的方法，一般写为 \(30^\circ, 75^\circ\)等。
-
单位圆：圆心在原点，半径为1的圆。
-
弧度制：高中的数学表示方法。角对应的单位圆上弧的长度
-
\(\pi = 180^\circ\)
-
正弦\(\sin \theta\) : 角\(\theta\)对边与斜边的比值， 余弦\(\cos \theta\): 角 \(\theta\) 邻边与斜边的比值，正切\(\tan\): 角 \(\theta\) 对比与邻边的比值
-
反三角函数: 反正弦函数 \(\arcsin x\) : 反余弦函数 \(\arccos x\): 反正切函数 \(\arctan x\) 。
组合数学
排列：\(A_n^m=\frac{n!}{(n-m)!}\)（顺序有关）
组合：\(C_n^m=\frac{n!}{m!(n-m)!}\)（顺序无关）
\(C_n^m=(C^{m\div p} _{n\div p})(C^{m\mod p}_{n\mod p})\)
$ h(n)=h(0) \times h(n-1) + h(1) \times h(n-2)+……+h(n-1)\times h(0)$
\(= \sum h(i)\times h(n-i-1)\)
\(h(n)=C^n_{2n}-C^{n+1}_{2n}\)
\(h(n)=\frac{C_{2n}^n}{n+1}\)
圆排列：\(A^m_n=\frac{n!}{(n-m)!}\div m\)
错排序：\(D(n)=n!(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+…+\frac{(-1)^n}{n!})=n!\sum\limits^n_{k=2}\frac{(-1)^k}{k!}=\lbrack\frac{n!}{e}+\frac{1}{2}\rbrack\)
树
存树
双亲表示法
记录某个节点的父节点。（根表示为-1）
孩子表示法
用链表来表示每个节点的所有子节点。
孩子兄弟表示法
存储每个节点的子节点和兄弟节点。
二叉排序(查找)树(binary search tree)
对于二叉树的任意一个节点，左子树的所有结点都比他小，右子树所有节点都比他大。
- 其中序遍历是严格递增的。
平衡 bst
深度为 \(\log n\) 的二叉树，查找一个点的时间复杂度为 \(O(\log n)\)。
欧拉道路
度数为奇数的点为 \(0\) 或 \(2\)。
欧拉回路
度数为奇数的点为 \(0\)。
保留小数
#include
cout < 数组(array)
int/double …… a[1005]; //设置数组a，类型为int/double……（变量类型 数组名[数组长度]）
a[n]=n //将数组a的第n个赋值为n
cout <1.数组长度不要用变量
2.数组长度可以多几个
3.数组的第一个元素下标为0，即第0个
4.*[n]={n};时，第0个设为n,其他位都为0
排序
#include //头文件，导入排序的库
sort(*+0,*+n+1,……) //按比较器排序（默认从小到大排序）sort(变量名+开始排序的下标，变量名+结束排序的下标+1，比较器)
greater()//从大到小排序
格式化数组
#include
memset(*,n,sizeof(*)) //把数组的每个值变成同一个值
定义比较器
bool cmp(int x,int,y){ //布尔类型函数，名为cmp
if(x>y){
return true; //如果x大于y，返回true
}
else{
return false; //否则返回false
}
}
字符串（string）
#include //头文件，导入字符串
string *; //设置变量*，类型为string
cout <<*; //输出变量*
getline(cin,*); //输入一行忽略空格
*.size() //求字符串*的长度
*.find(s) //字符串*中第一个字符串s的位置,如果没有，返回string::npos
*.insert(index,s) //在字符串*下标为index的位置插入字符串s
*.replace(index,length,s) //在字符串*下标为index的位置选取长度为length的部分替换为s
*.substr(index,length) //返回字符串*从下标为index的位置开始，长度为length的部分
substring //子字符串（必须连续）
subsequence //子序列（可以不连续）
数学函数
#include //头文件
pow(a,b) //a的b次方，参数类型double，返回值类型double
max(a,b) //a与b的最大值，参数类型相同
min(a,b) //a与b的最小值，参数类型相同
ceil(x) //向上取整，参数类型double
floor(x) //向下取整，参数类型double
round(x) //四舍五入，参数类型double
sqrt(x) //开根，参数类型double，返回值类型double
__gcd(x,y) //求x与y的最大公因数
x*y/__gcd(x,y) //求x与y的最小公倍数
定义函数
int/double …… *(int/double …… *, ……){ //函数类型 函数名称（参数类型 参数名，……）
…… //函数执行的事
}
当出现两个相同的变量时，按就近原则使用
函数内可以调用别的函数，也可以调用自己，即递归
struct(结构体)
//定义一种新的类型
struct name{ //定义一个名为name的类型
int num; //一个整数类型num
double num2; //一个实数类型num2
...... //内含的其他变量（最后不用return）
void print(){//成员方法
cout <class(类)
class a{
int x,y;//x和y是私有的
public:
void print(){
cout <链表
struct node{
int val;
node *nxt;//自引用
};
int main(){
node *head,*tail,*p;
int x;
cin >>x;
//输入任意个整数，
//在链表的末尾添加一个值为该整数的节点，
//输入-1时结束。
head=new node;
tail=head;
while(x!=-1){
p=new node;
//p->val <==> (*p).val;
p->val=x;
p->nxt=NULL;
tail->nxt=p;
tail=p;
cin >>x;
}
//输出链表
p=head;
while(p->nxt!=NULL){
p=p->nxt;
cout <val <<" ";
}
return 0;
}
STL模板库
优先队列
priority_queue q;//优先队列
priority_queue,greater> q;//从小到大
q.push();//推入
q.top();//队顶
pair
pair x;//定义两个数据在x中
x={1,2};//初始化，形同数组
x.first=1;//第一个
x.second=2;//第二个
pair> x;//套娃
x.first;//第一个
x.second.first;//第二个
x.second.second;//第三个
set
#include
set s;//定义集合
s.insert(1);//插入
if(s.find(2)!=s.end())//查找2是否在s中
map
#include 最短路
P3366 【模板】最小生成树
Kruskal
#include
#include
#include
using namespace std;
int n,m,ans=0,x=1;
bool vi[200005];
typedef pair node;
priority_queue ,greater > q;
vector e[200005];
node a[200005];
int main(){
cin >>n >>m;
for(int i=1;i<=m;i++){
int u,v,l;
cin >>u >>v >>l;
e[u].push_back({l,v});
e[v].push_back({l,u});
}
for(int i=1;i<=n;i++){
vi[i]=false;
}
vi[1]=true;
for(int t=1;t<=n-1;t++){
for(int i=0;i SPFA
#include
#include
#include
#include
using namespace std;
struct node{
int v,l;
};
queue q;
vector e[100005];
int n,m,dis[100005];
int main(){
memset(dis,0x3f,sizeof(dis));
int n,m,x;
cin >>n >>m >>x;
for(int i=1;i<=n;i++){
int u,v,l;
cin >>u >>v >>l;
node temp;
temp.v=v,temp.l=l;
e[u].push_back(temp);
}
int INF=dis[1];
q.push(1);
dis[1]=0;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=0;idis[now]+len){
q.push(nxt);
dis[nxt]=dis[now]+len;
}
}
}
if(dis[x]!=INF)cout < 关于SPFA,它死了
Dijkstra
#include
#include
#include
#include
using namespace std;
typedef long long ll;
struct node{
int v, len;
};
ll dis[100005];
vector e[100005];
typedef pair PII;
int main(){
int n, m, x;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, len;
cin >> u >> v >> len;
node temp;
temp.v = v;
temp.len = len;
e[u].push_back(temp);
}
priority_queue, greater > q;
q.push({0,1});
memset(dis, 0x3f, sizeof(dis));
long long INF = dis[0];
dis[1] = 0;
while (!q.empty()) {
while (!q.empty() && q.top().first > dis[q.top().second]) q.pop();
if (q.empty()) break;
int now = q.top().second;
q.pop();
for (int i = 0; i < e[now].size(); i++) {
int nxt = e[now][i].v;
int len = e[now][i].len;
if (dis[nxt] > dis[now] + len) {
q.push({dis[now]+len, nxt});
dis[nxt] = dis[now] + len;
}
}
}
for (int i = 1; i <= n; i++) {
if (dis[i] != INF) cout << dis[i] << ' ';
else cout << -1 << ' ';
}
return 0;
}
Floyd
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=min(f[i][k],f[i][j]+f[k][j;
}
}
}
传递闭包
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]|=f[i][j]&f[k][j;
}
}
}
质数筛
1.普通筛法
最普通的筛法，也就是将前 \(n\) 个正整数一个一个来判断是否为素数，并且在判断素数的时候要从 \(2\) 枚举到 \(n-1\) 来判断。
CODE
for(int i=1;i<=n;++i){//枚举1到n
bool flag=false;
for(int j=2;j这样的时间复杂度为 \(O(n^2)\)。
2.普通筛法的优化
学过奥数的朋友们可能会发现，在判断素数的时候，不一定需要枚举到 \(i-1\) 只需要枚举到 \(\sqrt{n}\) 就可以判断出来了。
CODE
for(int i=1;i<=n;i++){//枚举1到n
bool flag=false;
for(int j=2;j*j<=i;j++){//枚举2到i
if(i%j==0){//如果i%j=0,也就是i已经不为素数了
flag=true;//打上标记
break;//跳出循环，不用再枚举了
}
}
if(!flag)prime[i]=1;//如果没有被打上标记,标记这个数是为素数。
}
这样的时间复杂度为 \(O(n\sqrt{n})\)。
3.埃氏筛
我们发现，上面两种筛法会筛到许多没有意义的数，所以我们必须换一种思想方式。
埃氏筛，就是先将 \(prime\) 数组全部赋值为 \(1\)。(记得将 \(prime_i\) 赋值为 \(0\) )。仍然是要从 \(1\) 枚举到 \(n\) 。我们先假设当前枚举到了 \(i\)。
如果 \(prime_i=1\)也就是 \(i\) 为质数，则我们可以知道 \(i\) 的倍数均为合数，所以我们就将 \(prime_{i\times k (2\leq k
最终筛完之后，如果 \(prime_i=1\), \(i\) 就是质数。
CODE
memset(prime,1,sizeof(prime));
priem[1]=0;
for(int i=1;i<=n;++i){
if(prime[i]){
for(int j=2;j*i<=n;++j){
prime[i*j]=0;
}
}
}
这样的时间复杂度为 \(O(nlogn)\)
4.欧拉筛(线性筛)
我们发现，埃氏筛已经很快了，但是还是有所不足。
因为在埃氏筛中，有很多数有可能被筛到很多次（例如 \(6\),他就被 \(2\) 和 \(3\) 分别筛了一次）。 所以在欧拉筛中，我们就是在这个问题上面做了优化，使得所有合数只被筛了一次。
首先，我们定义 \(st_i\) 数组表示 \(i\) 是否为质数，\(primes_i\) 储存已经找到的所有质数，\(cnt\) 储存当前一共找到了多少质数。
如果当前已经枚举到了 \(i\)。如果 \(st_i=1\) ，也就是 \(i\) 为素数。则 \(primes_{cnt+1}=i\)。
然后我们每一次枚举都要做这个循环: 枚举 \(j\) 从 \(1\) 到 \(cnt\)。\(st_{primesj\times i}=0\)（因为 \(primes_j\) 为素数，\(i\) 就表示这个素数的多少倍，要把他筛掉。
注意，接下来是重点！如果 \(i\mod primes_j=0\)，跳出第二层循环。(因为欧拉筛默认每一个合数只能由他的最小质因数筛去，而满足以上条件之后，\(primes_j\) 就不是这个数字的最小质因数了，所以我们跳出第二层循环)。 因此，有了这一层优化之后，每一个合数就只能被筛掉一次了。
CODE
memset(st,0,sizeof(st));
st[1]=0;
for(i=2;i<=n;i++){
if(st[i]){
primes[cnt++]=i;
for(j=0;primes[j]*i<=n&&j<=cnt;j++){
st[primes[j]*i]=0;
if(i%primes[j]==0)break;
}
}
}
这样的时间复杂度为 \(O(n)\)
DFS
输入两个整数\(n, m\) ，然后输入\(n\)个整数 ，你可以从中选择一些数字，问有多少种方案可以让选择的数字和为\(m\)。
- 若方案A与方案B选择的数字中，有一个位置上的数字A选择了，但B没有选择，我们就认为两种方案不同，此时方案数是多少？
#include
using namespace std;
int a[105],n,ans,m;
void f(int now,int sum){
if(now==n+1){
if(sum==m){
ans++;
}
return ;
}
f(now+1,sum+a[now]);
f(now+1,sum);
}
int main(){
cin >>n >>m;
for(int i=1;i<=n;i++){
cin >>a[i];
}
f(1,0);
cout < - 若方案A与方案B选择的所有数字都相同，我们就认为两种方案相同。此时方案数是多少？
#include
#include
using namespace std;
int a[105],n,ans,m;
bool flag;
void f(int now,int sum,bool flag){
if(now==n+1){
if(sum==m){
ans++;
}
return ;
}
if(a[now-1]!=a[now] || flag){
f(now+1,sum+a[now],flag=true);
}
f(now+1,sum,flag=false);
}
int main(){
cin >>n >>m;
for(int i=1;i<=n;i++){
cin >>a[i];
}
sort(a+1,a+n+1);
f(1,0,true);
cout < 给定一个\(n * m\)的矩阵，输入两个整数\(n,m (1\leq n,m \leq 10)\) 为矩阵的行数和列数，然后输入n行，每行m个数字，每个数字\(-1000 \leq a_{i,j} \leq 1000\)。
- 求从\((1, 1)\)走到\((n, m)\)的所有路径中，路径上所有数字之和最大可以是多少。
#include
using namespace std;
int a[1005][1005],n,m,x1,y1,x2,y2,de_x[2]={1,0},de_y[2]={0,1},ans=-1e9;
bool found=false,flag[1005][1005];
bool c(int x,int y){
if(x<=0 || x>n || y<=0 ||y >m)return false;//必须在最前面
if(flag[x][y])return false;
return true;
}
void f(int x,int y,int nows){
if(x==n && y==m){
ans=max(ans,nows);
return ;
}
flag[x][y]=true;
for(int i=0;i<4;i++){
int nx=x+de_x[i];
int ny=y+de_y[i];
if(c(nx,ny)){
f(nx,ny,nows+a[nx][ny]);
}
}
flag[x][y]=false;
}
int main(){
cin >>n >>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >>a[i][j];
}
}
f(1,1,a[1][1]);
cout < 给定一个\(n * m\)的01矩阵，输入两个整数\(n,m (1\leq n,m \leq 1000)\) 为矩阵的行数和列数，然后输入n行，每行m个数字，每个数字为0或1.其中0表示通路，1表示墙壁。
- 输入四个整数\(x1, y1, x2, y2\)， 问从 \((x1, y1)\) 能否走到 $ (x2, y2)$。可以，则输出YES；否则输出NO
#include
using namespace std;
int a[1005][1005],n,m,x1,y1,x2,y2,de_x[4]={-1,1,0,0},de_y[4]={0,0,-1,1};
bool found=false,flag[1005][1005];
bool c(int x,int y){
if(x<=0 || x>n || y<=0 ||y >m)return false;//必须在最前面
if(flag[x][y])return false;
if(a[x][y]==1)return false;
return true;
}
void f(int x,int y){
if(x==x2 && y==y2){
found=true;
return ;
}
flag[x][y]=true;
for(int i=0;i<4;i++){
int nx=x+de_x[i];
int ny=y+de_y[i];
if(c(nx,ny)){
f(nx,ny);
}
}
}
int main(){
cin >>n >>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >>a[i][j];
}
}
cin >>x1 >>y1 >>x2 >>y2;
f(x1,y1);
cout <<(found?"yes":"no");
return 0;
}
BFS
拓扑排序
- 有\(n\)课\(,m\)个前置条件。每个前置条件为两个数字\(u,v\)表示上了第\(u\)个课才能上第\(v\)个课，请问能不能上完所有的课？输出任意一个上课方案
#include
#include
#include
using namespace std;
vector e[100005];
int du[100005];
vector ans;
int main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
du[v]++;
}
queue q;
for (int i = 1; i <= n; i++) {
if (du[i] == 0){
q.push(i);
}
}
while (!q.empty()){
// 2. 找队首
int now = q.front();
q.pop();
ans.push_back(now);
// 3. 找相邻点
for (int i = 0; i < e[now].size(); i++) {
int nxt = e[now][i];
du[nxt]--;
if (du[nxt] == 0) {
q.push(nxt);
}
}
}
if (ans.size() != n) cout << -1;
else {
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << ' ';
}
}
return 0;
}
给定一个\(n \times m\)的矩阵，\(1\)表示墙，\(0\)表示路，你要从\((1,1)\)走到\((n,m)\)，需要多少步?
#include
#include
using namespace std;
struct node {
int x, y;
};
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
// dis[x][y]: (1,1)到(x,y)的距离
int dis[105][105], a[105][105];
bool visited[105][105];
int n, m;
bool check(int x, int y) {
if (x <= 0 || y <= 0 || x > n || y > m) return false;
if (a[x][y] == 1) return false;
if (visited[x][y]) return false;
return true;
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
queue q;
// 1. 放入起始点
node start;
start.x = 1, start.y = 1;
q.push(start);
visited[1][1] = true;
// 只要队列非空，继续循环
while (!q.empty()) {
// 2. 弹出队首
node now = q.front();
q.pop();
// 3. 找到当前点所有相邻的点，入队,把相邻点设为已访问过
for (int i = 0; i < 4; i++) {
node nxt;
nxt.x = now.x + dx[i];
nxt.y = now.y + dy[i];
if (check(nxt.x, nxt.y)) {
q.push(nxt);
// plan2
visited[nxt.x][nxt.y] = true;
dis[x][y]: (1,1)到(x,y)的最短距离
dis[nxt.x][nxt.y] = dis[now.x][now.y] + 1;
}
}
}
if (visited[n][m]) cout << dis[n][m];
else cout << -1;
}
层序输出树
#include
#include
#include
using namespace std;
vector e[10005];
bool flag[10005];
int main(){
int n;
cin >>n;
for(int i=1;i<=n-1;i++){
int u,v;
cin >>u >>v;
e[v].push_back(u);
e[u].push_back(v);
}
queue q;
q.push(1);
flag[1]=true;
while(!q.empty()){
int now=q.front();
q.pop();
cout < 树状数组1
p3374
#include
using namespace std;
int n,m,a[500005],b[500005];
int lowbit(int x){
return x & -x;
}
void init(){
for(int i=1;i<=n;i++){
b[i]+=a[i];
if(i+lowbit(i)<=n)b[i+lowbit(i)]+=b[i];
}
}
void add(int pos,int x){
while(pos<=n){
b[pos]+=x;
pos=pos+lowbit(pos);
}
}
int fi(int pos){
int ans=0;
while(pos>=1){
ans+=b[pos];
pos-=lowbit(pos);
}
return ans;
}
int main(){
cin >>n >>m;
for(int i=1;i<=n;i++){
cin >>a[i];
}
init();
while(m--){
int q,x,y;
cin >>q >>x >>y;
if(q==1){
add(x,y);
}
else{
cout < 树状数组2
p3368
#include
using namespace std;
typedef long long ll;
ll n,m,a[500005],b[500005],f[500005];
ll lowbit(int x){
return x & -x;
}
void init(){
for(int i=1;i<=n;i++){
f[i]+=a[i];
if(i+lowbit(i)<=n)f[i+lowbit(i)]+=f[i];
}
}
void add(int pos,int x){
while(pos<=n){
f[pos]+=x;
pos=pos+lowbit(pos);
}
}
ll fi(int pos){
int ans=0;
while(pos){
ans+=f[pos];
pos-=lowbit(pos);
}
return ans;
}
int main(){
cin >>n >>m;
for(int i=1;i<=n;i++){
cin >>b[i];
}
init();
while(m--){
ll q;
cin >>q;
if(q==1){
ll x,y,k;
cin >>x >>y >>k;
add(x,k);
add(y+1,-k);
}
else{
ll x;
cin >>x;
cout <