2022年《数据结构试验》上机考试一（计科2103,2105班+数据2101,2102班）题解

 这个波一OJ我真是***

一直给我交之前的main.cpp，我新换上去一直交不上去，一直wa

2208: 该谁发球了？

这是个小思维

大于10以后看的是%2结果

小于10看的是%4的结果

#include
#define int long long
#define pb push_back
using namespace std;
const int N=1e6+10;
signed main(){
    int n,m;
    while(cin>>n>>m){
        if(abs(n-m)==2&&max(n,m)>=11){
            cout<<"Game Over\n";
        }
        else if(n>=10&&m>=10){
            if((n+m)&1==0){
                cout<<"A\n";
            }
            else{
                cout<<"B\n";
            }
        }
        else{
            if((n+m)%4>=2){
                cout<<"B\n";
            }
            else{
                cout<<"A\n";
            }
        }
    }
}

2375: 判断三角形的形状

模拟即可

#include
#define int long long
#define pb push_back
using namespace std;
const int N=1e6+10;
signed main(){
    int a,b,c;
    while(cin>>a>>b>>c){
        if(a==b&&b==c){
            cout<<"DB\n";
        }
        else if(a+b
            cout<<"ERROR\n";
        }
        else if(a==b || b==c || a==c){
            cout<<"DY\n";
        }
        else if(a*a+b*b==c*c || a*a+c*c==b*b || b*b+c*c==a*a){
            cout<<"ZJ\n";
        }
        else{
            cout<<"PT\n";
        }
    }
}

5873: 3.5.2 悲剧文本

虽然也是模拟

但这题用list写会好写很多

因为list可以指定插入，通过begin和end调整位置

#include
#define int long long
#define pb push_back
using namespace std;
const int N=1e6+10;
signed main(){
    string s;
    while(cin>>s){
        list<int> li;
        auto it=li.begin();
        for(auto t:s){
            if(t==']'){
                it=li.end();
            }
            else if(t=='['){
                it=li.begin();
            }
            else{
                li.insert(it,t);
            }
        }
        for(auto t:li){
            cout<<(char)t;
        }
        cout<<'\n';
    }
}

5867: 4.4.3 矩阵连乘

这道题是之前四则运算的一个简化版本

用栈存括号来辅助计算

#include
#define int long long
#define pb push_back
using namespace std;
#define pll pair
const int N=1e6+10;
pll q[N];
int n,m;
signed main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        char x;
        cin>>x;
        cin>>q[x].first>>q[x].second;
    }
    string s;
    while(cin>>s){
        int f=0;
        int res=0;
        stack stk;
        for(auto i:s){
            if(isalpha(i)) stk.push(q[i]);
            else if(i==')'){
                auto k2=stk.top();
                stk.pop();
                auto k1=stk.top();
                stk.pop();
                if(k1.second!=k2.first){
                    f=1;
                    break;
                }
                res+=k1.first*k1.second*k2.second;
                stk.push({k1.first,k2.second});
 
            }
        }
        if(f) cout<<"error\n";
        else cout<'\n';
    }
}

5874: 4.4.4 打印队列

第i次被打印的一定是第i大的数

排序之后用队列模拟

是直接输出，不是就pop

#include
#define int long long
#define pb push_back
using namespace std;
#define pll pair
const int N=1e6+10;
pll q[N];
int n,m;
void solve(){
    queue<int> q;
    vector<int> a,b;
    int k=0;
    cin>>n>>m;
    for(int j=0;j
        int x;
        cin>>x;
        a.push_back(x);
        b.push_back(x);
        q.push(j);
    }
    sort(b.begin(),b.end(),greater<int>());
    int w=0;
    int max=0;
    while(q.size()){
        max=b[w];
        int t=q.front();
        if(a[t]
            q.pop();
            q.push(t);
 
        }
        else{
            if(t==m){
                cout<<++k<<'\n';
                break;
            }
            else{
                q.pop();
                k+=1;
                w+=1;
            }
        }
    }
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
     
}

5907: 5.3.5.3 树

几乎是作业原题了

通过中序和前序建树

（不懂这个可以搜一下，很多教程）

然后dfs

#include
#define int long long
#define pb push_back
using namespace std;
#define pll pair
const int N=1e6+10;
int n,lc[N],rc[N];
int minsum,minv;
int ino[N],pos[N];
int create(int L,int R,int m){
    if(m<=0) return 0;
    int root=pos[R+m-1];
    int len=0;
    while(ino[L+len]!=root){
        len+=1;
    }
    lc[root]=create(L,R,len);
    rc[root]=create(L+len+1,R+len,m-len-1);
    return root;
}
bool readline(int *a){
    string line;
    if(!getline(cin,line))
        return false;
    stringstream s(line);
    n=0;
    int x;
    while(s>>x){
        a[n++]=x;
    }
    return n>0;
}
void dfs(int v,int sum){
    sum+=v;
    if(lc[v]==0&&rc[v]==0){
        if(sum
            minv=v;
            minsum=sum;
        }
    }
    if(lc[v]){
        dfs(lc[v],sum);
 
    }
    if(rc[v]){
        dfs(rc[v],sum);
    }
}
void work(){
        create(0,0,n);
        minsum=1000000000+7;
        dfs(pos[n-1],0);
        cout<'\n';
}
signed main(){
    while(readline(ino)){
        readline(pos);
        work();
    }
     
}

5917: 5.4.2 信息熵

题面花里胡哨的

这题哈夫曼树板子题

每次取两个最小的，合并在塞回去

直到剩下一个

#include
#define int long long
#define pb push_back
using namespace std;
#define pll pair
const int N=1e6+10;
int a[100];
string s;
void work(){
    priority_queue<int,vector<int>,greater<int> > q;
        if(s=="END") exit(0);
        for(int i=0;i<=99;++i) a[i]=0;
        for(int i=0;i<=s.size()-1;++i){
            if(s[i]=='_'){
                a[26]+=1;
            }
            else{
                a[s[i]-'A']++;
            }
        }
            for(int i=0;i<27;++i){
                if(a[i]!=0){
                    q.push(a[i]);
                }
            }
            int sum=0;
            while(q.size()>=2){
                int x1=q.top();
                q.pop();
                int x2=q.top();
                q.pop();
                q.push(x1+x2);
                sum+=(x1+x2);
            }
            if(!sum) sum=s.size();
            cout<size()*8<<" "<" ";
            cout<setprecision(1)<<(double)(s.size()*8)/(double)sum<<'\n';
}
signed main(){
    while(cin>>s){
        work();
    }
     
}