算法备赛模板（临时）（二）

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100][100];//存储杨辉三角每一行的内容
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){//控制行
    for(int j=1;j<=i;j++){
      if(i==j||j==1) a[i][j]=1;//根据观察得出的
      else a[i][j]=a[i-1][j]+a[i-1][j-1]; //根据观察易得
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
      cout<<a[i][j]<<" ";
    }
    cout<<"\n";
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10];
bool b[10];
int dfs(int x){
    if(x==n){
        for(int i=0;i<n;i++) cout<<a[i]<<" ";
        cout<<"\n";
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(!b[i]){
            a[x]=i;
            b[i]=true;
            dfs(x+1);
            b[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[10],b[10];
int n;
void dfs(int x,int st){
    if(x>=3){
        for(int i=0;i<3;i++) cout<<a[i];
        cout<<"\n";
        return ;
    }
    for(int i=st;i<=n;i++){
        if(!b[i]){
            a[x]=i;
            b[i]=true;
            dfs(x+1,st+1);
            b[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0,1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef pair<int,int> PII; //用来存点，用pair方便点点
const int N=110; //数据范围
int g[N][N],d[N][N];// g数组装整个图，  d数组表示某点到原点的距离
int bfs(){
    queue<PII> q;
    q.push({0,0});//首先起点入队
    memset(d,-1,sizeof d);//将最开始的所有点到起点的距离都设置为-1
    d[0][0]=0;//起点到起点的距离设置为0,
    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; /*方向数组，随便向那个方向扩展都得行，
    我的是上(x不变，y会加1)右（x会加1，y不变）下（x不变，y会减1）左（x会减1，y不变）*/
    while(!q.empty()){
        auto t = q.front();//取出队首元素
        q.pop();//队首出队
        for(int i=0;i<4;i++){//向4个方向扩展
            // x,y 为扩展后的， t装的是拓展前的坐标
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            //满足边界条件，拓展的点的位置没有障碍，在之前没有被访问过（距离为-1就表示没访问过）
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){
                d[x][y]=d[t.first][t.second]+1;//更新距离
                q.push({x,y});//将成功扩展的点入队
            }
        }
    }
    return d[n-1][m-1];//最终 d[n-1][m-1] 就是右下角到左上角的需要移动的最短距离
}
int main(){
    cin>>n>>m;
    //读入图的信息
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    cout<<bfs()<<"\n";//输出结果
}

#include<bits/stdc++.h>
using namespace std;
// const int n=1000010;
int m,n;
int p[1000010];//存储节点的父亲
int findX(int x){//采用了路径压缩
    if(x!=p[x]) p[x]=findX(p[x]);
    return p[x];
}
int main(){
//    cin.tie(0);
//    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--){
        string x;
        int a,b;
        cin>>x>>a>>b;
        if(x=="M") p[findX(a)] = findX(b);
        else{
            if(findX(a)==findX(b)) cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
int n,m;
//dist表示某点到起点的距离  
//st表示某个点是否加入队列 true表示没加入,反之则加入 
int dist[maxn],st[maxn];  
// h:头结点  w:权重  e:边  ne:下一个点   idx就表示节点 
int h[maxn],w[maxn],e[maxn],ne[maxn],idx;
void add(int a,int b,int c){//邻接表  模板，背到就可以   
  e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){
  memset(dist,0x3f,sizeof(dist));//将初始距离设为很大的数 
  queue<int> q;
  dist[1]=0;// 初始化第一个点到第一个点的距离为 0 ,方便后面的计算 
  q.push(1);// 先将第一个点加入队列 
  st[1]=true;//第一个点加入了队列，所以 st[1] = true 
  while(!q.empty()){//广搜的模板 
    int t = q.front();//取出第一个节点 
    q.pop();//取出了后，就要出队列 
    st[t]=false;//取出后，没在队列了，设置为 false 
    for(int i=h[t];i!=-1;i=ne[i]){//更新t的出边 
      int j = e[i];//获得和t相连的点
      if(dist[j]>dist[t]+w[i]){//如果可以距离变得更短，则更新距离
        dist[j]=dist[t]+w[i];
        if(!st[j]){//如果没在队列中,可以入队 
          q.push(j);
          st[j]=true;//入队了，设置为false 
        } 
      }
    }
  }
  return dist[n]==0x3f3f3f3f?-2:dist[n];
}
int main(){
  cin>>n>>m;
  memset(h,-1,sizeof(h));//这一步不能忘记 
  while(m--){
    int x,y,z;  cin>>x>>y>>z;
    add(x,y,z);
  }
  int ans=spfa();
  if(ans!=-2) cout<<dist[n];
  else cout<<"impossible"; 
  return 0;
}

#include<bits/stdc++.h>
#define ll long long 
using namespace std; 
#define maxn 10010
int N,V;// N件物品，V为背包体积 
int v[maxn],w[maxn];// v数组装物品的体积 , w数组装物品的价值 
int dp[10010];
int main(){
  cin>>N>>V;
  for(int i=1;i<=N;i++) cin>>v[i]>>w[i];
  for(int i=1;i<=N;i++){
    for(int j=V;j>=v[i];j--){//dp[j]为 容量为j的背包所背的最大价值 
      dp[j]=max(dp[j],dp[j-v[i]]+w[i]); 
    }
  } 
  cout<<dp[V]; 
  return 0; 
}

#include<bits/stdc++.h>
#define ll long long 
using namespace std; 
#define maxn 10010
int N,V;// N件物品，V为背包体积 
int v[maxn],w[maxn];// v数组装物品的体积 , w数组装物品的价值 
int dp[10010];
int main(){
  cin>>N>>V;
  for(int i=1;i<=N;i++) cin>>v[i]>>w[i];
  for(int i=1;i<=N;i++){
    for(int j=v[i];j<=V;j++){//dp[j]为 容量为j的背包所背的最大价值 
      dp[j]=max(dp[j],dp[j-v[i]]+w[i]); 
    }
  } 
  cout<<dp[V]; 
  return 0; 
}

#include<bits/stdc++.h>
#define ll long long 
using namespace std; 
#define maxn 100010
int N,V;// N件物品，V为背包体积 
int v[maxn],w[maxn];// v数组装物品的体积 , w数组装物品的价值 
int dp[10010];
int len=0;//用来记录 v 与 w 数组的长度 
int main(){
  cin>>N>>V;
  for(int i=1;i<=N;i++){
    int vi,wi,s;  cin>>vi>>wi>>s;
    while(s--){//拆成 01 背包来做
      v[++len]=vi;
      w[len]=wi; 
    } 
  } 
  for(int i=1;i<=len;i++){//这里就是有 len 个物品了
    for(int j=V;j>=v[i];j--){//dp[j]为 容量为j的背包所背的最大价值 
      dp[j]=max(dp[j],dp[j-v[i]]+w[i]); 
    }
  } 
  cout<<dp[V]; 
  return 0; 
}

#include<bits/stdc++.h>
#define ll long long 
using namespace std; 
#define maxn 150
int N,V;// N件物品，V为背包体积 
int v[maxn][maxn],w[maxn][maxn],s[maxn];// v数组装物品的体积 ,w数组装物品的价值 ,s数组表示第每组物品的个数 
int dp[10010];
int len=0;//用来记录 v 与 w 数组的长度 
int main(){
  cin>>N>>V;
  for(int i=1;i<=N;i++){
    cin>>s[i];
    for(int j=0;j<s[i];j++){
      cin>>v[i][j]>>w[i][j];
    }
  } 
  for(int i=1;i<=N;i++){// n组 
    for(int j=V;j>=0;j--){
      for(int k=0;k<s[i];k++){
        if(v[i][k]<=j) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
      }
    }
  } 
  cout<<dp[V]; 
  return 0; 
}