名词
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<<y= xtimes 2^y)
(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<<y= xtimes 2^y) |
| >> | 二进制右移运算符。将一个数的各二进制位全部右移若干位，正数左补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的子集，记为(Anotsubset B)。
- 真子集：如果B是A的子集，且B与A并不相等，则称B是A的真子集。记作 (B subseteq A)。若A不是B的真子集，记为(Anotsubseteq 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^+})
- 集合与不等式的转化：如 (1leq 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(Acap 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(aleq blt 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^{mdiv p} _{ndiv p})(C^{mmod p}_{nmod 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!sumlimits^n_{k=2}frac{(-1)^k}{k!}=lbrackfrac{n!}{e}+frac{1}{2}rbrack)
树
存树
双亲表示法
记录某个节点的父节点。（根表示为-1）
孩子表示法
用链表来表示每个节点的所有子节点。
孩子兄弟表示法
存储每个节点的子节点和兄弟节点。
二叉排序(查找)树(binary search tree)
对于二叉树的任意一个节点，左子树的所有结点都比他小，右子树所有节点都比他大。
- 其中序遍历是严格递增的。
平衡 bst
深度为 (log n) 的二叉树，查找一个点的时间复杂度为 (O(log n))。
欧拉道路
度数为奇数的点为 (0) 或 (2)。
欧拉回路
度数为奇数的点为 (0)。
保留小数
#include <iomanip> cout <<fixed <<setprecision(2) <<a; printf("%.2f",a); 数组(array)
int/double …… a[1005]; //设置数组a，类型为int/double……（变量类型 数组名[数组长度]） a[n]=n //将数组a的第n个赋值为n cout <<a[n]; //输出数组a的第n个 arr[100]={0}; //将数组arr全设为0 arr[100]={n1,n2,n3}; //将数组arr的第0个赋值为n1，第1个赋值为n2,第2个赋值为n3 1.数组长度不要用变量
2.数组长度可以多几个
3.数组的第一个元素下标为0，即第0个
4.*[n]={n};时，第0个设为n,其他位都为0
排序
#include <algorithm> //头文件，导入排序的库 sort(*+0,*+n+1,……) //按比较器排序（默认从小到大排序）sort(变量名+开始排序的下标，变量名+结束排序的下标+1，比较器) greater<int/double ……>()//从大到小排序 格式化数组
#include <cstring> 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 *; //设置变量*，类型为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 <cmath> //头文件 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 <<num; } name(int num,double num2):num(_num),num2(_num2){ }//构造函数初始化 name(){ num1=114514; num2=1919.810;//初始化 } name(): ......//用冒号初始化 name operator+(name num){//重载运算符 return node(y+num.x,y+num.y); } }; /、结尾有； name a; //定义一个类型为name的变量a a.num=114514; //变量a的num值为114514 a.num2=1919.810 //变量a的num2值为1919.810 a.print();//使用成员方法 a=(1,1.1);//初始化 name b; a=a+b;//重载后的运算符进行运算 class(类)
class a{ int x,y;//x和y是私有的 public: void print(){ cout <<x;//print()是公有的 } } 链表
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 <<p->val <<" "; } return 0; } STL模板库
优先队列
priority_queue<int> q;//优先队列 priority_queue<int,vector<int>,greater<int>> q;//从小到大 q.push();//推入 q.top();//队顶 pair
pair<int,int> x;//定义两个数据在x中 x={1,2};//初始化，形同数组 x.first=1;//第一个 x.second=2;//第二个 pair<int,pair<int,int>> x;//套娃 x.first;//第一个 x.second.first;//第二个 x.second.second;//第三个 set
#include <set> set<int> s;//定义集合 s.insert(1);//插入 if(s.find(2)!=s.end())//查找2是否在s中 map
#include <map>//map是映射的意思 map<int,int> mp;//一个数据对应一个数据 mp[2]=3; mp[-1]=2; mp[114514]++;//map默认为0，可以直接使用，而且数据量大，只是慢 最短路
Kruskal
#include <iostream> #include <vector> #include <queue> using namespace std; int n,m,ans=0,x=1; bool vi[200005]; typedef pair<int,int> node; priority_queue <node,vector<node>,greater<node> > q; vector<node> 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<e[x].size();i++){ q.push(e[x][i]); } while(!q.empty() && vi[q.top().second]){ q.pop(); } if(q.empty()){ cout <<"orz"; return 0; } ans+=q.top().first; x=q.top().second; vi[x]=true; } cout <<ans; return 0; } SPFA
#include <iostream> #include <queue> #include <vector> #include <cstring> using namespace std; struct node{ int v,l; }; queue<int> q; vector<node> 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;i<e[now].size();i++){ int len=e[now][i].l; int nxt=e[now][i].v; if(dis[nxt]>dis[now]+len){ q.push(nxt); dis[nxt]=dis[now]+len; } } } if(dis[x]!=INF)cout <<dis[x]; else cout <<-1; return 0; } 关于SPFA,它死了
Dijkstra
#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; typedef long long ll; struct node{ int v, len; }; ll dis[100005]; vector<node> e[100005]; typedef pair<int,int> 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<PII, vector<PII>, greater<PII> > 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<i;++j){//枚举2到i if(i%j==0){//如果i%j=0,也就是i已经不为素数了 flg=1;//打上标记 break;//跳出循环，不用再枚举了 } } if(!flag)prime[i]=1;//如果没有被打上标记,标记这个数是素数。 } 这样的时间复杂度为 (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(nsqrt{n}))。
3.埃氏筛
我们发现，上面两种筛法会筛到许多没有意义的数，所以我们必须换一种思想方式。
埃氏筛，就是先将 (prime) 数组全部赋值为 (1)。(记得将 (prime_i) 赋值为 (0) )。仍然是要从 (1) 枚举到 (n) 。我们先假设当前枚举到了 (i)。
如果 (prime_i=1)也就是 (i) 为质数，则我们可以知道 (i) 的倍数均为合数，所以我们就将 (prime_{itimes k (2leq k<n)}) 赋值为 (0)。
最终筛完之后，如果 (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_{primesjtimes i}=0)（因为 (primes_j) 为素数，(i) 就表示这个素数的多少倍，要把他筛掉。
注意，接下来是重点！如果 (imod 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 <iostream> 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 <<ans; return 0; } - 若方案A与方案B选择的所有数字都相同，我们就认为两种方案相同。此时方案数是多少？
#include <iostream> #include <algorithm> 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 <<ans; } 给定一个(n * m)的矩阵，输入两个整数(n,m (1leq n,m leq 10)) 为矩阵的行数和列数，然后输入n行，每行m个数字，每个数字(-1000 leq a_{i,j} leq 1000)。
- 求从((1, 1))走到((n, m))的所有路径中，路径上所有数字之和最大可以是多少。
#include <iostream> 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 <<ans; return 0; } 给定一个(n * m)的01矩阵，输入两个整数(n,m (1leq n,m leq 1000)) 为矩阵的行数和列数，然后输入n行，每行m个数字，每个数字为0或1.其中0表示通路，1表示墙壁。
- 输入四个整数(x1, y1, x2, y2)， 问从 ((x1, y1)) 能否走到 $ (x2, y2)$。可以，则输出YES；否则输出NO
#include <iostream> 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 <iostream> #include <vector> #include <queue> using namespace std; vector<int> e[100005]; int du[100005]; vector<int> 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<int> 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 <iostream> #include <queue> 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<node> 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 <iostream> #include <queue> #include <vector> using namespace std; vector<int> 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<int> q; q.push(1); flag[1]=true; while(!q.empty()){ int now=q.front(); q.pop(); cout <<now <<" "; for(int i=0;i<e[now].size();i++){ int nxt=e[now][i]; if(flag[nxt])continue; q.push(nxt); flag[nxt]=true; } } return 0; } 树状数组1
#include <iostream> 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 <<fi(y)-fi(x-1) <<endl; } } return 0; } 树状数组2
#include <iostream> 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 <<fi(x)+b[x] <<endl; } } return 0; } 
