---恢复内容开始---

L3-001 凑零钱 

链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805054207279104

思路;

数据很小直接 dfs

代码：

#include
      
       using namespace std;const int M = 1e5 + 10;int vis[M],a[M],n,m,cnt,sum,flag,mp[M];void dfs(int x){    if(sum > m) return ;    if(sum == m) {         for(int i = 1;i < cnt;i ++)            cout<
       
        <<" ";         cout<
        
         <
         
          <= n;i ++){        if(flag == 1) continue;        sum += a[i];        vis[++cnt] = a[i];        dfs(i+1);        sum-=a[i];        vis[cnt--] = 0;    }}int main(){    int k = 0;    cin>>n>>m;    for(int i = 1;i <= n;i ++){        cin>>a[i];        k += a[i];    }    sort(a+1,a+1+n);    if(k < m) cout<<"No Solution"<
         
        
       
      

 

L3-002 特殊堆栈

链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805053695574016

思路; 线段树维护下，避免超时

实现代码：

#include
      
       using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define mid int m = (l + r) >> 1;const int M = 1e5+10;int a[M],cnt,sum[M<<2];void update(int p,int c,int l,int r,int rt){    if(l == r){        sum[rt]+=c;        return ;    }    mid;    if(p <= m) update(p,c,lson);    else update(p,c,rson);    sum[rt] = sum[rt<<1] + sum[rt<<1|1];}int query(int p,int l,int r,int rt){    if(l == r){        return l;    }    mid;    if(sum[rt<<1] >= p) return query(p,lson);    else return query(p-sum[rt<<1],rson);}int main(){    ios::sync_with_stdio(0);    cin.tie(0); cout.tie(0);    int n,x;    string s;    cin>>n;    for(int i = 1;i <= n;i ++){        cin>>s;        if(s[1] == 'o'){            if(cnt == 0) cout<<"Invalid"<
       
        >x;            a[cnt] = x; cnt++;            update(x,1,1,M,1);        }        else{            if(cnt == 0) cout<<"Invalid"<
       
      

 

L3-003 社交集群

链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805053141925888

思路：给所有人建边，建完跑并查集就好了

用了getchar()， 不要加cin的同步流。。。

实现代码:

#include
      
       using namespace std;const int M = 1e3+10;int f[M],siz[M];vector
       
        v[M],ans;bool cmp(int x,int y){    return x > y;}int Find(int x){    if(x == f[x]) return f[x];    return f[x] = Find(f[x]);}void Union(int x,int y){    int fx = Find(x),fy = Find(y);    if(fx != fy){        f[fx] = fy;        siz[fy] += siz[fx];    }}int main(){    int n,x,y;    cin>>n;    for(int i = 1;i <= n;i ++){        cin>>x;        getchar();        for(int j = 1;j <= x;j ++){            cin>>y;            v[y].push_back(i);        }    }    for(int i = 0;i <= n;i ++) f[i] = i,siz[i] = 1;    for(int i = 1;i <= 1000;i ++){        if(v[i].size()==0) continue;        int len = v[i].size();            for(int k = 1;k < len;k ++){                //cout<
        
         <<" "<
         
          <
          
           <= n;i ++){        if(f[i] == i){           ans.push_back(siz[i]);        }    }    sort(ans.begin(),ans.end(),cmp);    cout<
           
            <
            
             < len-1;i ++){ cout<
             
              <<" "; } cout<
              
               <
              
             
            
           
          
         
        
       
      

 

 L3-004 肿瘤诊断

链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805052626026496

思路：直接三维bfs就好了，用dfs会爆栈

实现代码:

#include
      
       using namespace std;int dx[6][3] = {
    {
    1,0,0},{-1,0,0},{
    0,1,0},{
    0,-1,0},{
    0,0,1},{
    0,0,-1}};int a[61][1300][150],ans;int n,m,l,t;struct node{    int x,y,z;};bool check(int x,int y,int z){    if(x < 1||x > l||y < 1||y > n||z < 1||z > m) return 0;    return 1;}void bfs(int x,int y,int z){    queue
       
        q;    node now;    now.x = x; now.y = y; now.z = z;    a[x][y][z] = 0;    q.push(now);    int sum = 1;    while(!q.empty()){        node old = q.front();        q.pop();        for(int i = 0;i < 6;i ++){            node now = old;            now.x += dx[i][0];            now.y += dx[i][1];            now.z += dx[i][2];            //cout<
        
         <<" "<
         
          <<" "<
          
           <
           
            = t) ans += sum;}int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>l>>t; for(int i = 1;i <= l;i ++){ for(int j = 1;j <= n;j ++){ for(int k = 1;k <= m;k ++){ cin>>a[i][j][k]; } } } for(int i = 1;i <= l;i ++){ for(int j = 1;j <= n;j ++){ for(int k = 1;k <= m;k ++){ if(a[i][j][k]){ bfs(i,j,k); } } } } cout<
            
             <
            
           
          
         
        
       
      

 

L3-008 喊山

链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805050709229568

思路：建边跑bfs，不能跑dfs，题目是要一层一层的跑，比如有三条边  1-2，1-3，2-3，如果dfs会跑出 1-2-3，bfs会跑出1-2,1-3。这个才是题目需要的跑法

实现代码：

#include
      
       using namespace std;vector
       
        g[11000];int vis[11000];int ans,mx;struct node{    int x,step;};void bfs(int x,int step){    queue
        
         q;    node now;    now.x = x;now.step = step;    q.push(now);    vis[x] = 1;    while(!q.empty()){        node old = q.front();        q.pop();        if(old.step > mx){            mx = old.step;            ans = old.x;        }        else if(old.step == mx){            ans = min(old.x,ans);        }        for(int i = 0;i < g[old.x].size();i ++){            int v = g[old.x][i];            if(vis[v]) continue;            node now;            now.x = v;now.step=old.step+1;            q.push(now);            vis[now.x] = 1;        }    }}int main(){    int n,m,k,x,y;    cin>>n>>m>>k;    for(int i = 1;i <= m;i ++){        cin>>x>>y;        g[x].push_back(y);        g[y].push_back(x);    }    for(int i = 1;i <= k;i ++){        cin>>x;        memset(vis,0,sizeof(vis));        mx = 0; ans = 0;        bfs(x,1);        if(ans == x) ans = 0;        cout<
         
          <
         
        
       
      

 

               

L3-010 是否完全二叉搜索树 

链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805049870368768

思路：按二叉树性质直接dfs建树就好了，如果是完全二叉树的话，遍历起来下标是连续的。

实现代码:

#include
      
       using namespace std;const int M = 110;int a[M];void build(int x,int rt){    if(!a[rt]){        a[rt] = x;        return ;    }    if(x > a[rt]) build(x,rt*2);    else build(x,rt*2+1);}int main(){    int n,x;    cin>>n;    for(int i = 1;i <= n;i ++){        cin>>x;        build(x,1);    }    int ans = 0,fg = 0;    for(int i = 1;i <= n*2;i ++){        if(a[i]){            ans++;cout<