python,Java, PHP算法,普及组算法汇总

编译型语言和解释型语言编译型语言: C,C++,Pascal解释型语言: python, Java, PHP

码

原码、反码、补码：8位二进制数表示的有符号整数

反码: 原码的符号位不变，其他位取反

补码:10101011

原码:11010101

-52

反码:11001011

运算符

\(x<<y= x\times 2^y\

\(x>>y=\frac{x}{2^y}\

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

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

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

数学知识

集合论基础

1. 集合：若干个互异无序元素。集合有两种记录方法，如

\(A = \{1,2,3\},T = \{i|i为偶数\}\

2. 空集：没有函数的集合。计作：\(\emptyset\

3. 属于与不属于: 表示一个元素是否属于该集合。如 \(1 \in A, 4 \notin A\

4. 子集：如果集合A中包含集合B中的所有元素，则称B为A的子集。记作 \(B \subset A\。若A不是B的子集，记为\(A\not\subset B\。

5. 真子集：如果B是A的子集，且B与A并不相等，则称B是A的真子集。记作 \(B \subseteq A\。若A不是B的真子集，记为\(A\not\subseteq B\。

6. 并 集：字面意思为将两个集合合并后的结果。即如果元素x在集合A或集合B中，那么x在集合A与集合B的并集中。A与B的并集可以记作 $X = A \cup B $

7. 交 集：字面意思为两个集合相交的部分。即如果元素x既在集合A中，又在集合B中。那么元素x在集合A与B的交集中。A与B的交集可以记作 \(Y = A \cap B\。

1. 区间：区间是一种特殊的集合，表示一个连续的部分的所有元素。如 \([1,2]、 (4, 5、 [9, 10、 (2, +\infty\

2. 闭区间、开区间与半开半闭区间：

3. 用[]表示的是闭区间，表示区间左右两端的元素都在集合中，如\([1,2]\，1也是集合的一个元素；

4. 用(表示的是开区间，表示区间左右两端的元素都不在集合中，如\((4,5\，4和5都不在集合中；

5. 一边中括号一边小括号的是半开半闭区间，中括号那一端的元素在集合中，小括号那一端的不在集合中。

6. 带有无穷符号的区间：有\(+\infty\ 与 \(-\infty\ 。无穷符号那一端的必须是小括号，且正无穷的正号不能省略。

7. 几个重要的集合: 实数集：\(\mathbb{R}\ , 自然数集合：\(\mathbb{N}\, 整数集合: \(\mathbb{Z}\, 正整数集合: \(\mathbb{N^+}\

8. 集合与不等式的转化：如 \(1\leq x \leq 10\ 可以写成 \([1,10]\，\(x \gt 3\ 可以写成 \((3, +\infty\

概率论基础

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 \cap B\，\(P(C = P(A\cap B = P(AB\

5. 独立事件：两个事件的发生没有相关关系，则这两个事件为独立事件。如"今天下雨"与"扔硬币扔出正面"是独立事件。"今天下雨"与"今天空气湿度高于50%"不是独立事件。

6. 独立事件的概率：\(P(AB = P(A \cdot 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 \cdot P(B = P(B|A \cdot P(A\

10. 互斥事件：不可能同时发生的事件。如“扔一次骰子扔出1”与“扔一次骰子扔出2”，“扔一次硬币为正面”与“扔一次硬币为反面”。

11. 对立事件：其中至少一个会发生的互斥事件。如”扔一次骰子扔出1“与“扔一次骰子扔出2”不是对立事件，“扔一次硬币为正面”与“扔一次硬币为反面”是对立事件。事件\(A\的对立事件记为\(\bar{A}\。那么\(P(A+P(\bar{A} = 1\。

12. 全概率公式：\(P(A = P(A|B\cdot P(B + P(A|\bar{B} \cdot P(\bar{B}\

13. 数学期望：随机事件的结果。如果一个随机试验会出现多种结果（或事件）\(X_1, X_2, ...,X_i\，每种事件可以获得\(V_i\的收益。那么随机试验\(X\ 的数学期望为 \(E(X = \displaystyle \sum_{i=1}^nP(X_i\cdot V_i\。

平面直角坐标系

1. 平面直角坐标系由横轴与纵轴组成。横轴为x轴，纵轴为y轴，点的坐标由括号组成的二元组表示，如(x, y。

2. 点A对x轴作垂线到达的位置为A的横坐标，对y轴作垂线到达的位置为B的纵坐标。

三角函数

\(a, b, c(a\leq b\lt c\。则\(a^2 + b ^ 2= c^2\。

2. 角度制：一种表示角度的方法，一般写为 \(30^\circ, 75^\circ\等。

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

5. \(\pi = 180^\circ\

6. \(\sin \theta\ : 角\(\theta\对边与斜边的比值，余弦\(\cos \theta\: 角 \(\theta\ 邻边与斜边的比值，正切\(\tan\: 角 \(\theta\ 对比与邻边的比值

7. \(\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}\

\(= \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\

树

存树

双亲表示法

孩子表示法

用链表来表示每个节点的所有子节点。

孩子兄弟表示法

二叉排序(查找树(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.数组长度不要用变量

3.数组的第一个元素下标为0，即第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，可以直接使用，而且数据量大，只是慢

最短路

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

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]!=INFcout <<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(!flagprime[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(!flagprime[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<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_{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]==0break;
        }
    }
}

这样的时间复杂度为 \(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 (1\leq 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 >mreturn 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\leq 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 >mreturn false;//必须在最前面 
    if(flag[x][y]return false;
    if(a[x][y]==1return 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

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<=nb[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<=nf[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;
    }

声明：本文由用户投稿上传，本站不保证内容的真实与正确性，并且不承担相关法律责任，如有侵权请提供版权资料并联系删除！

编程笔记 » python,Java, PHP算法,普及组算法汇总