天天看點
傳回

2019 中南大學研究所學生招生夏令營機試題（1110~1114）

目錄：

A：地磚問題 簡單bfs

B：最小花費 dfs+dijkstra

C：回文串 動态規劃

D：有序合并 數組排序

E：十六進制轉換 字元串問題

A：地磚問題

http://39.106.164.46/problem.php?id=1110

題意：

求可以走過最多的黑磚個數。

思路：

簡單的bfs。

AC代碼：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 30
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,m;//n行，m列
char ch[MAX][MAX];
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}},visit[MAX][MAX];

struct node{
    int x,y;
    node(int xx,int yy){
        x=xx;
        y=yy;
    }
};

bool judge(int x,int y){
    if(x<0||x>n-1||y<0||y>m-1) return false;
    return true;
}

int bfs(int x,int y){
    int sum=0;
    queue<node> q;
    node t(x,y);
    q.push(t);
    visit[x][y]=1;
    while(!q.empty()){
        node top=q.front();
        q.pop();
        int x=top.x;
        int y=top.y;
        if(ch[x][y]=='@'||ch[x][y]=='.') sum++;
        for(int i=0;i<4;i++){
            int xx=x+dir[i][0];
            int yy=y+dir[i][1];
            if(judge(xx,yy)&&visit[xx][yy]==0&&ch[xx][yy]=='.'){
                node tmp(xx,yy);
                visit[xx][yy]=1;
                q.push(tmp);
            }
        }
    }
    return sum;
}

int main(){
    while(scanf("%d %d",&m,&n)!=EOF){
        if(n==0&&m==0) return 0;
        memset(visit,0,sizeof(visit));
        for(int i=0;i<n;i++){
            scanf("%s",&ch[i]);
        }
        int x,y;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(ch[i][j]=='@'){
                    x=i,y=j;
                }
            }
        }
        int res=bfs(x,y);
        printf("%d\n",res);
    }
    return 0;
}

B：最小花費

http://39.106.164.46/problem.php?id=1111

題意：

Dijkstra + DFS模闆題。

題目的意思其實是隻能沿着一條路徑轉賬，那麼從A到B，我們可以找出所有的最短路徑，一次dijkstra即可，在路徑花費最小的情況下，可以再用一次dfs找出路徑數量最多的那一條路徑，這樣就能保證損失的錢最少，那麼A轉給B的錢也就是最少的。

AC代碼：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 2005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,m;
int mp[MAX][MAX],dis[MAX],vis[MAX];
vector<int> pre[MAX];
vector<int> path,tmppath;
int start,goal,ans=-1;

void dijkstra(int s){
    for(int i=0;i<=n;i++){
        vis[i]=0;
        dis[i]=INF;
    }
    dis[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,minl=INF;
        for(int j=1;j<=n;j++){
            if(dis[j]<minl&&vis[j]==0){
                minl=dis[j];
                u=j;
            }
        }
        if(u==-1) break;
        vis[u]=1;
        for(int v=1;v<=n;v++){
            if(vis[v]==0&&mp[u][v]!=INF){
                if(dis[v]>dis[u]+mp[u][v]){
                    dis[v]=dis[u]+mp[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v]==dis[u]+mp[u][v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}

void dfs(int v){
    tmppath.push_back(v);
    if(v==start){//當最短距離相同時，選擇路徑最多的一條
        int tmp=tmppath.size();
        if(ans<tmp){
            ans=tmp;
            path=tmppath;
        }
        tmppath.pop_back();
        return;
    }

    for(int i=0;i<pre[v].size();i++){
        dfs(pre[v][i]);
    }
    tmppath.pop_back();
}


int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i=0;i<MAX;i++){//初始化
            for(int j=0;j<MAX;j++){
                mp[i][j]=INF;
            }
        }
        int a,b,len;
        for(int i=0;i<m;i++){
            scanf("%d %d %d",&a,&b,&len);
            mp[a][b]=mp[b][a]=len;
        }
        scanf("%d %d",&start,&goal);
        dijkstra(start);
        ans=-1;
        dfs(goal);
        double res=100.0;
        int now=path[0];
        for(int i=1;i<path.size();i++){
            int rate=mp[now][path[i]];
            double r=(double)rate/100;
            res=res/(1.0-r);
            now=path[i];
        }
        printf("%.8lf\n",res);

    }
    return 0;
}

C： 回文串

http://39.106.164.46/problem.php?id=1112

思路：

其實就是簡單的動态規劃。枚舉子串的長度即可。

AC代碼1：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 5005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

string s;
int dp[MAX][MAX];

int main(){
    while(cin>>s){
        memset(dp,0,sizeof(dp));//初始化
        int len=s.length(),ans=0;//ans記錄總的連續回文子串個數
        for(int i=0;i<len;i++){
            dp[i][i]=1;
            ans++;
            if(i<len-1){
                if(s[i]==s[i+1]){
                    ans++;
                    dp[i][i+1]=1;
                }
            }
        }
        //狀态轉移方程
        for(int l=3;l<=len;l++){//枚舉子串的長度
            for(int i=0;i+l-1<len;i++){
                int j=i+l-1;
                if(s[i]==s[j]&&dp[i+1][j-1]==1){
                    ans++;
                    dp[i][j]=1;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

AC代碼2：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define MAX 5005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

string s;
int dp[MAX][MAX];

int main(){
    while(cin>>s){
        memset(dp,0,sizeof(dp));
        int len=s.length(),ans=0;
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(s[i]==s[j]){
                    if(dp[i+1][j-1]==1||j-i<3){
                        dp[i][j]=1;
                        ans++;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

D： 有序合并

http://39.106.164.46/problem.php?id=1113

思路：

注意讀數的方式，用一個數組存儲讀進來的兩行數，然後排序輸出即可。

AC代碼：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 5005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,m;
vector<int> vec;
int num,cnt=0;

int main(){
    while(scanf("%d",&n)!=EOF){
        cnt++;
        for(int i=0;i<n;i++){
            scanf("%d",&num);
            vec.push_back(num);
        }
        if(cnt==2){
            sort(vec.begin(),vec.end());
            for(int i=0;i<vec.size();i++){
                printf("%s%d",i==0?"":" ",vec[i]);
            }
            cout<<endl;
            vec.clear();
            cnt=0;
        }
    }
    return 0;
}

E： 十六進制轉換

http://39.106.164.46/problem.php?id=1114

思路：

将一個不超過100000位的十六進制數，轉換成八進制數。使用map，首先可以将十六進制數轉化為二進制數，然後補充前導0至長度為3的倍數，然後将這個二進制數轉化為八進制數，最後不輸出前導0即可。

AC代碼：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 5005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

string s;
map<char,string> mp1;
map<string,char> mp2;

int main(){
    mp1['0']="0000";mp1['1']="0001";mp1['2']="0010";mp1['3']="0011";
    mp1['4']="0100";mp1['5']="0101";mp1['6']="0110";mp1['7']="0111";
    mp1['8']="1000";mp1['9']="1001";mp1['A']="1010";mp1['B']="1011";
    mp1['C']="1100";mp1['D']="1101";mp1['E']="1110";mp1['F']="1111";

    mp2["000"]='0';mp2["001"]='1';mp2["010"]='2';mp2["011"]='3';
    mp2["100"]='4';mp2["101"]='5';mp2["110"]='6';mp2["111"]='7';
    while(cin>>s){
        string res="",tmp="";
        int len=s.length();
        for(int i=0;i<len;i++){
            tmp+=mp1[s[i]];
        }
        if(tmp.size()%3==1){//若餘1，這說明差2位，前面補2個0，補成3的倍數
            tmp="00"+tmp;
        }else if(tmp.size()%3==2){//若餘2，這說明差1位，前面補1個0
            tmp="0"+tmp;
        }
        for(int i=0;i<tmp.size();i+=3){
            res=res+mp2[tmp.substr(i,3)];
        }
        int flag=0;
        for(int i=0;i<res.size();i++){
            if(res[i]=='0'&&flag==0) continue;
            flag=1;
            cout<<res[i];
        }
        cout<<endl;
    }
    return 0;
}
機試 算法
上一篇: 什麼是vue.js？（概念很清楚）Vue.js新手入門指南
下一篇: ResultSetMetaData

繼續閱讀