USTC机试_06下

2021-01-12

1.统计一个字符串当中有多少字母、数字、空格和其它字符；

#include<iostream>
#include<cstdio>

using namespace std;

int count_zimu=0,count_shuzi=0,count_space=0,count_others=0;

void Count(char c){
    if(c>='0'&&c<='9') count_shuzi++;
    else if((c>='a'&&c<='z')||(c>='A'&&c<='Z')) count_zimu++;
    else if(c==' ') count_space++;
    else count_others++;
}

int main(){
    string s;3r
    getline(cin,s);
    for(int i=0;i<s.size();i++){
        Count(s[i]);
    }
    cout<<count_zimu<<" "<<count_shuzi<<" "<<count_space<<" "<<count_others<<endl;
}

2.给你一个 10进制数，要你输出 8进制数；

#include<iostream>
#include<stack>
using namespace std;

int main(){
    int n;
    stack<int> result;
    cin>>n;
    while(n!=0){
        result.push(n%8);
        n/=8;
    }
    while(!result.empty()){
        cout<<result.top();
        result.pop();
    }
}

3.给你一个数，要求你求出这个数与其反序数的和相加多少次才可以得到回
文字

#include<iostream>

using namespace std;

int Reverse(int x){//求逆序
    int result=0;
    while(x!=0){
        result=result*10+x%10;
        x/=10;
    }
    return result;
}

bool ishuiwen(int x){//判断回文
    if(Reverse(x)==x) return true;
    else return false;
}

int main(){
    int time=0;
    int n;
    cin>>n;
    while(!ishuiwen(n)){
        n=n+Reverse(n);
        time++;
    }
    cout<<time<<endl;
}

4.给你一个数列，求出最大子序列之和

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=100;
int a[MAXN];
int dp[MAXN];
int main(){
    int n;
    cin>>n;
    int Max=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        if(i==0) dp[i]=a[i];
        else dp[i]=max(a[i],dp[i-1]+a[i]);
        if(dp[i]>Max) Max=dp[i];
    }
    cout<<Max<<endl;
}

5.给你几个整数，求出最大的组合数

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN=100;
vector<string> v;

//使用字典序可以快速解决这道题
bool compare(string x,string y){
    return x>y;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string num;
        cin>>num;
        v.push_back(num);
    }
    sort(v.begin(),v.end(),compare);
    for(int i=0;i<n;i++){
        cout<<v[i];
    }
}

6.关于图的最大连通分量

#include<bits/stdc++.h>
#define maxn 10001
using namespace std;
vector<int>G[maxn];
stack<int>s;
int n,m;
int dfn[maxn],used[maxn],vis[maxn],low[maxn],color[maxn],num[maxn],colornum=0,cnt=0,ans=0;
void paint(int x){
    s.pop();
    color[x]=colornum;
    num[colornum]++;

    vis[x]=false;
}
void tarjan(int x){
    dfn[x]=low[x]=++cnt;//依次深搜并且对dfn和low初始化
    s.push(x);
    vis[x]=used[x]=true;//置访问标记
    for(int i=0;i<G[x].size();i++){//遍历当前节点的所有边
        int q=G[x][i];
        if (!dfn[q]){//如果边没有被访问过，即没有被dfn初始化
            tarjan(q);
            low[x]=min(low[x],low[q]);
        }
        else if (vis[q]) low[x]=min(low[x],dfn[q]);//如果
    }
    if (low[x]==dfn[x]){//满足强连通分量的条件
        colornum++;
        while(s.top()!=x){
            int t=s.top();
            paint(t);
        }
        paint(x);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if (!used[i]) tarjan(i);
    }
    for(int i=1;i<=colornum;i++){
        if (num[i]>0) ans++;
    }
    cout<<ans;
    return 0;
}

7.用二叉树，给你先序和中序遍历，输出后续遍历

#include<iostream>
#include<cstring>
using namespace std;

string pre,post;

struct TreeNode{
    char c;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c):c(c){}
};

TreeNode* PreInCreat(int l1,int h1,int l2,int h2){
    TreeNode* T=new TreeNode(pre[l1]);//根结点
    int i;
    for(i=l2;post[i]!=T->c;i++) ;//根结点在中序序列中的划分
    int llen=i-l2;//左子树长度
    int rlen=h2-i;//右子树长度
    //这里的上下限画个图就清楚了
    if(llen) T->left=PreInCreat(l1+1,l1+llen,l2,l2+llen-1);
    else T->left=NULL;
    if(rlen) T->right=PreInCreat(h1-rlen+1,h1,h2-rlen+1,h2);
    else T->right=NULL;
    return T;
}

void PostOrder(TreeNode* T){
    if(T==NULL) return;
    else{
        PostOrder(T->left);
        PostOrder(T->right);
        cout<<T->c;
    }
}

int main(){
    cin>>pre>>post;
    TreeNode* root=PreInCreat(0,pre.size()-1,0,post.size()-1);
    PostOrder(root);
}