复试上机真题历年回顾-2011

单词首字母统计

模拟即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N =1e5+100;
string str;
string s[N];
int cnt;
bool cmp(string a,string b){
    for(int i=0;a[i]&&b[i];i++)
        if(a[i]<b[i]) return 1;
        else if(a[i]>b[i]) return 0;
    return a.length()<b.length();
}
signed main(){
    while(getline(cin,str)){
        int j=0;
        for(int i=0;i<str.size();i++)
            if(str[i]==' '){
                s[cnt++]=str.substr(j,i-j);
                j=i+1;
            }
        s[cnt++]=str.substr(j);
        sort(s,s+cnt,cmp);
        j=0;
        int kcnt=0;
        for(int i=0;i<cnt;i++){
            cout<<s[i]<<endl;
            if(s[i][0]==s[j][0]) ++kcnt;
            else{
                cout<<s[j][0]<<": "<<kcnt<<endl;
                j=i;
                --i;
                if(i==cnt-1) cout<<s[j][0]<<": "<<kcnt<<endl;
                kcnt=0;
            }
        }
        if(kcnt>0) cout<<s[j][0]<<": "<<kcnt<<endl;

    }
    return 0;
}

单词排序

排序即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N =1e5+100;
string str;
string s[N];
int cnt;
bool cmp(string a,string b){
    for(int i=0;a[i]&&b[i];i++)
        if(a[i]<b[i]) return 1;
        else if(a[i]>b[i]) return 0;
    return a.length()<b.length();
}
signed main(){
    while(getline(cin,str)){
        int j=0;
        for(int i=0;i<str.size();i++)
            if(str[i]==' '){
                s[cnt++]=str.substr(j,i-j);
                j=i+1;
            }
        s[cnt++]=str.substr(j);
        sort(s,s+cnt,cmp);
        for(int i=0;i<cnt;i++)
            cout<<s[i]<<endl;

    }
    return 0;
}

判断层次关系

给一个字符串(aaaa(bbbb(cccc,dddd),eeee(ffff))) 该字符串
表明的是各个人的层次关系。比如aaaa是bbbb和eeee的领导,bbbb
是cccc和dddd的领导。现输入一个名称,比如ffff,要求输出其领导关系。
输出aaaa>eeee>ffff

把所有情况都模拟一遍(×)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N =1e5+100;
map<string,int>mp1;
map<int,string>mp2;
int f[N],cnt,c;
stack<int>father;
void dfs(string q,bool flag){
    int ff =f[mp1[q]];
    if(ff == 0){
        cout<<q<<">";
        return;
    }
    string fq =mp2[ff];
    dfs(fq,1);
    if(flag)
        cout<<q<<">";
    else
        cout<<q;
}

signed main(){
    string p;
    cin>>p;
    int j=1;
    int fa=0,tmp=0;
    for(int i=1;p[i];i++){
        if(p[i]==','&&p[i-1]==')'){//碰到逗号且左边是)
            c=0;
            j=i+1;
        }
        else if(p[i]=='('||(p[i]==','&&c==0)){//括号或者第一个逗号前的字符串
            string s =p.substr(j,i-j);
            mp1[s]=++cnt;//记录字符串对应的序号
            mp2[cnt]=s;//记录序号对应的字符串
            father.push(fa);
            f[cnt]=father.top();//标记s对应的上司
            if(p[i]=='(')//是括号
                    fa=cnt;
            else {
                fa=father.top();//是第一个逗号
                ++c;//标记已不是第一个逗号
            }
            j=i+1;
        }else if(p[i]==','&&c&&p[i-1]!=')'){//是逗号,但不是第一个逗号且逗号前一个字符不为)
            string s =p.substr(j,i-j);
            mp1[s]=++cnt;
            mp2[cnt]=s;
            f[cnt]=father.top();//父亲不是上一次记录的fa,而是father.top()
            j=i+1;
        }else if(p[i]==')'&&c){//碰到右括号,且之前出现过逗号
            string s =p.substr(j,i-j);
            mp1[s]=++cnt;
            mp2[cnt]=s;
            f[cnt]=father.top();
            father.pop();
            fa=father.top();//更新fa
            j=i+1;
        }else if(p[i]==')'&&!c){//碰到右括号,且之前没出现过逗号
            string s =p.substr(j,i-j);
            mp1[s]=++cnt;
            mp2[cnt]=s;
            f[cnt]=fa;
            fa=father.top();
            j=i+1;
        }
    }
    string q;
    cin>>q;
    if(f[mp1[q]]==0) cout<<q<<endl;
    else dfs(q,0);//回溯找上司
}

群友的思路 直接找爸爸(×)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
string s;
signed main(){
    string s;
    cin>>s;
    while(true){
        string tmp;
        cin>>tmp;
        int leader=0;
        vector<string> stack1;
        int i=0;
        stack1.push_back(tmp);
        for(i=0;i<s.size();i++){
            if(tmp==s.substr(i,tmp.size())){
                break;//找到查询字符串在s中的位置
            }
        }
        for(;i>=0;i--){
            if(s[i]=='(')leader++;
            else if(s[i]==')')leader--;
            else if(s[i]!='('&&s[i]!=','&&s[i]!=')'&&leader>0){
                int j;
                for(j=i;j>=0;j--){
                    if(s[j]=='('||s[j]==','||s[j]==')'){
                        break;
                    }
                }
                stack1.push_back(s.substr(j+1,i-j));
                leader=0;
                i=j+1;
            }
        }
        for(vector<string>::iterator j=stack1.end()-1;j!=stack1.begin();j--){
            cout<<*j<<">";
        }
        cout<<stack1.front()<<endl;
    }
}