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