2021年團體程式設計天梯賽賽前模擬賽1 補題

1.正整數A+B

分析： 簡單模擬，注意邊界情況三個數帶兩個空格，

代碼：

#include<bits/stdc++.h>
using namespace std;
string s,a,b;
int flag1,flag2,x1,x2,pos;
int main(){
    getline(cin,s);
    for(pos=0;s[pos];pos++){
        if(s[pos]!=' ') a+=s[pos];
        else break;
    }
    for(int i=pos+1;s[i];i++) b+=s[i];
    for(int i=0;a[i];i++){
        if(a[i]<'0'||a[i]>'9'){
            flag1=1;
            break;
        }
    }
    for(int i=0;b[i];i++){
        if(b[i]<'0'||b[i]>'9'){
            flag2=1;
            break;
        }
    }
    if(flag1) cout<<"?";
    else{
        x1=stoi(a);
        if(x1>1000||x1==0) flag1=1,cout<<"?";
        else cout<<a;
    }
    cout<<" + ";
    if(flag2) cout<<"?";
    else{
        x2=stoi(b);
        if(x2>1000||x2==0) flag2=1,cout<<"?";
        else cout<<b;
    }
    cout<<" = ";
    if(!flag1&&!flag2) cout<<x1+x2<<endl;
    else cout<<"?"<<endl;
}

9.紅色警報

分析： 并查集，
先初始化并查集，統計連通分量的個數，每次刪完點都把之前的合法操作進行一遍，再次統計連通分量的個數，如果連通分量個數不變或者減少一個，那么就不會對整個國家的連通性造成影響；否則就會造成影響，

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=5050,M=505;
int n,m,k,u[N],v[N],p[M],id,cnt;
bool st[M];
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void init(){
    for(int i=0;i<n;i++) p[i]=i;
}
int count(){
    int res=0;
    for(int i=0;i<n;i++){
        if(p[i]==i&&!st[i]) res++;
    }
    return res;
}
int main(){
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        cin>>u[i]>>v[i];
        p[find(u[i])]=find(v[i]);
    }
    cnt=count();
    cin>>k;
    for(int i=0;i<k;i++){
        init();
        int res=0;
        cin>>id;
        st[id]=1;
        for(int j=0;j<m;j++){
            if(!st[v[j]]&&!st[u[j]]) p[find(u[j])]=find(v[j]);
        }
        res=count();
        if(res==cnt||res==cnt-1) printf("City %d is lost.\n",id);
        else printf("Red Alert: City %d is lost!\n",id);
        cnt=res;
    }
    if(k==n) cout<<"Game Over."<<endl;
}
        cin>>u[i]>>v[i];
        p[find(u[i])]=find(v[i]);
    }
    cnt=count();
    cin>>k;
    for(int i=0;i<k;i++){
        init();
        int res=0;
        cin>>id;
        st[id]=1;
        for(int j=0;j<m;j++){
            if(!st[v[j]]&&!st[u[j]]) p[find(u[j])]=find(v[j]);
        }
        res=count();
        if(res==cnt||res==cnt+1) printf("City %d is lost.\n",id);
        else printf("Red Alert: City %d is lost!\n",id);
        cnt=res;
    }
    if(k==n) cout<<"Game Over."<<endl;
}

13.是否完全二叉搜索樹

分析： 二叉樹板子，注意怎么判斷完全二叉樹，

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef struct node* tree;
struct node{
    int data;
    tree l,r;
};
int n,a,flag,bj;
void add(tree &root,int x){
    if(root==NULL){
        root=(tree)malloc(sizeof(tree));
        root->data=x;
        root->l=root->r=NULL;
    }
    else{
        if(x>root->data) add(root->l,x);
        else add(root->r,x);
    }
}
void ceng(tree root){
    if(root==NULL) return ;
    queue<tree> q;
    q.push(root);
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        flag==0?printf("%d",t->data),flag++:printf(" %d",t->data);
        if(t->l) q.push(t->l);
        if(t->r) q.push(t->r);
    }
}
void pd(tree root){
    int res=0;
    if(root==NULL) return ;
    queue<tree> q;
    q.push(root);
    tree t;
    while((t=q.front())!=NULL){
        q.push(t->l);
        q.push(t->r);
        q.pop();
        res++;
    }
    if(res!=n) bj=1;
}
int main(){
    tree root=NULL;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        add(root,a);
    }
    ceng(root);
    cout<<endl;
    pd(root);
    if(bj) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}