普及组算法汇总 - shipeiqian - 博客园

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

原码:10110100

反码:11001011

补码:11001100

x<<y=x×2y

x>>y=x2y

∨:或 -> 只要有一个为真，则表达式为真

∧:且 -> 两个都是真才为真，有一个假为假

﹃（）﹃（¬）：非 -> 假为真，真为假

集合论基础

1. 集合：若干个互异无序元素。集合有两种记录方法，如 为偶数A={1,2,3},T={i|i为偶数}
2. 空集：没有函数的集合。计作：∅
3. 属于与不属于: 表示一个元素是否属于该集合。如 1∈A,4∉A
4. 子集：如果集合A中包含集合B中的所有元素，则称B为A的子集。记作 B⊂A。若A不是B的子集，记为A⊄B。
5. 真子集：如果B是A的子集，且B与A并不相等，则称B是A的真子集。记作 B⊆A。若A不是B的真子集，记为A⊈B。
6. 并 集：字面意思为将两个集合合并后的结果。即如果元素x在集合A或集合B中，那么x在集合A与集合B的并集中。A与B的并集可以记作 X=A∪B
7. 交 集：字面意思为两个集合相交的部分。即如果元素x既在集合A中，又在集合B中。那么元素x在集合A与B的交集中。A与B的交集可以记作 Y=A∩B。

---

1. 区间：区间是一种特殊的集合，表示一个连续的部分的所有元素。如 、、、[1,2]、(4,5)、[9,10)、(2,+∞)
2. 闭区间、开区间与半开半闭区间：
3. 用[]表示的是闭区间，表示区间左右两端的元素都在集合中，如[1,2]，1也是集合的一个元素；
4. 用()表示的是开区间，表示区间左右两端的元素都不在集合中，如(4,5)，4和5都不在集合中；
5. 一边中括号一边小括号的是半开半闭区间，中括号那一端的元素在集合中，小括号那一端的不在集合中。
6. 带有无穷符号的区间：有+∞ 与 −∞ 。无穷符号那一端的必须是小括号，且正无穷的正号不能省略。
7. 几个重要的集合: 实数集：R , 自然数集合：N, 整数集合: Z, 正整数集合: N+
8. 集合与不等式的转化：如 1≤x≤10 可以写成 [1,10]，x>3 可以写成 (3,+∞)

概率论基础

1. 事件：一个不受主观意念控制的事情。如“天要下雨”，"彩票中一千万", "CSP初赛全部靠蒙考满分", "明天太阳照常升起"是事件，"我今天吃肯德基", "CSP凭实力0分", "我晚上通宵写代码"不是事件。在概率论中，我们常用一个字母表示一个事件，如事件A为天要下雨。
2. 概率：事件发生的可能性。一般用P表示，事件A发生的概率记为P(A) 。
3. 频数与频率。在计算一个事件发生的概率时，需要进行多次随机试验。事件发生的次数就是频次，事件发生频次的比例就是频率。如事件A为扔硬币扔出正面。我扔了10次硬币，9次正面，则频次为9，频率为90%。
4. 积事件：若事件C为事件A与事件B同时发生，那么事件C就是事件A与事件B的积事件。记为C=A∩B，P(C)=P(A∩B)=P(AB)
5. 独立事件：两个事件的发生没有相关关系，则这两个事件为独立事件。如"今天下雨"与"扔硬币扔出正面"是独立事件。"今天下雨"与"今天空气湿度高于50%"不是独立事件。
6. 独立事件的概率：P(AB)=P(A)⋅P(B) 。注意只有事件A与B独立该式才成立。
7. 和事件的概率：P(A+B)=P(A)+P(B)−P(AB) 。和事件为两个事件至少发生一个的概率。
8. 条件概率：P(A|B) 表示在B事件发生的条件下，A事件发生的概率。即“如果今天下雨，门口路上堵车的概率。”、“扔一次骰子扔出的数字是偶数，那么扔出的数字是2的概率”。
9. 贝叶斯公式：P(AB)=P(A|B)⋅P(B)=P(B|A)⋅P(A)
10. 互斥事件：不可能同时发生的事件。如“扔一次骰子扔出1”与“扔一次骰子扔出2”，“扔一次硬币为正面”与“扔一次硬币为反面”。
11. 对立事件：其中至少一个会发生的互斥事件。如”扔一次骰子扔出1“与“扔一次骰子扔出2”不是对立事件，“扔一次硬币为正面”与“扔一次硬币为反面”是对立事件。事件A的对立事件记为A¯。那么P(A)+P(A¯)=1。
12. 全概率公式：P(A)=P(A|B)⋅P(B)+P(A|B¯)⋅P(B¯)
13. 数学期望：随机事件的结果。如果一个随机试验会出现多种结果（或事件）X1,X2,...,Xi，每种事件可以获得Vi的收益。那么随机试验X 的数学期望为 E(X)=∑i=1nP(Xi)⋅Vi。

平面直角坐标系

1. 平面直角坐标系由横轴与纵轴组成。横轴为x轴，纵轴为y轴，点的坐标由括号组成的二元组表示，如(x, y)。
2. 点A对x轴作垂线到达的位置为A的横坐标，对y轴作垂线到达的位置为B的纵坐标。

1. 勾股定理：在直角三角形中，假设三条边长度为 a,b,c(a≤b<c)。则a2+b2=c2。

2. "小角对小边"：在直角三角形中，角度较小的角所对的边较短

3. 角度制：一种表示角度的方法，一般写为 30∘,75∘等。

4. 单位圆：圆心在原点，半径为1的圆。

5. 弧度制：高中的数学表示方法。角对应的单位圆上弧的长度

6. π=180∘

7. 正弦sin⁡θ : 角θ对边与斜边的比值， 余弦cos⁡θ: 角 θ 邻边与斜边的比值，正切tan: 角 θ 对比与邻边的比值

8. 反三角函数: 反正弦函数 arcsin⁡x : 反余弦函数 arccos⁡x: 反正切函数 arctan⁡x 。

排列：Anm=n!(n−m)!（顺序有关）

组合：Cnm=n!m!(n−m)!（顺序无关）

Cnm=(Cn÷pm÷p)(Cnmodpmmodp)

h(n)=h(0)×h(n−1)+h(1)×h(n−2)+……+h(n−1)×h(0)

=∑h(i)×h(n−i−1)

h(n)=C2nn−C2nn+1

h(n)=C2nnn+1

圆排列：Anm=n!(n−m)!÷m

错排序：D(n)=n!((−1)22!+(−1)33!+…+(−1)nn!)=n!∑k=2n(−1)kk!=[n!e+12]

双亲表示法

记录某个节点的父节点。（根表示为-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<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;//第三个

#include <set>
set<int> s;//定义集合
s.insert(1);//插入
if(s.find(2)!=s.end())//查找2是否在s中

#include <map>//map是映射的意思
map<int,int> mp;//一个数据对应一个数据
    mp[2]=3;
    mp[-1]=2;
    mp[114514]++;//map默认为0，可以直接使用，而且数据量大，只是慢

P3366 【模板】最小生成树

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;
}

#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 来判断。

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(n2)。

2.普通筛法的优化

学过奥数的朋友们可能会发现，在判断素数的时候，不一定需要枚举到 i−1 只需要枚举到 n 就可以判断出来了。

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(nn)。

3.埃氏筛

我们发现，上面两种筛法会筛到许多没有意义的数，所以我们必须换一种思想方式。

埃氏筛，就是先将 prime 数组全部赋值为 1。(记得将 primei 赋值为 0 )。仍然是要从 1 枚举到 n 。我们先假设当前枚举到了 i。

如果 primei=1也就是 i 为质数，则我们可以知道 i 的倍数均为合数，所以我们就将 primei×k(2≤k<n) 赋值为 0。

最终筛完之后，如果 primei=1, i 就是质数。

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 分别筛了一次）。 所以在欧拉筛中，我们就是在这个问题上面做了优化，使得所有合数只被筛了一次。

首先，我们定义 sti 数组表示 i 是否为质数，primesi 储存已经找到的所有质数，cnt 储存当前一共找到了多少质数。

如果当前已经枚举到了 i。如果 sti=1 ，也就是 i 为素数。则 primescnt+1=i。

然后我们每一次枚举都要做这个循环: 枚举 j 从 1 到 cnt。stprimesj×i=0（因为 primesj 为素数，i 就表示这个素数的多少倍，要把他筛掉。

注意，接下来是重点！如果 imodprimesj=0，跳出第二层循环。(因为欧拉筛默认每一个合数只能由他的最小质因数筛去，而满足以上条件之后，primesj 就不是这个数字的最小质因数了，所以我们跳出第二层循环)。 因此，有了这一层优化之后，每一个合数就只能被筛掉一次了。

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)

输入两个整数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(1≤n,m≤10) 为矩阵的行数和列数，然后输入n行，每行m个数字，每个数字−1000≤ai,j≤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(1≤n,m≤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;
}

• 有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×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

p3374

    #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

p3368

    #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;
    }

__EOF__