【机试】2011-2020年复旦大学考研复试机试真题

阅读量：

题型分布目录

2011-1

2014-2

2014-4

2016-1

2018-3

2019-2

2011-2

2012-2

2014-3

2019-3

三、栈或队列问题
- 【2015-3】优先队列
- 【2016-2】后缀序列求值
- 【2016-3】字符串的哈夫曼编码最短长度
四、图
- 【2013-3】图的BFS遍历
五、查找
- 【2014-1】二分查找
六、堆排序
- 【2012-1】1000名求前30%

2012-3

2013-3

八、补充2020年机试题
- A、斗牛
- B、打地鼠
- C、排队打饭
- D、二叉搜索树
- E、序列

一、DP问题

【2011-1】DP-最长公共子序列LCS

问题描述：给定三个字符串s₁、s₂和s₃，请计算这三个字符串的最大公共连续子串并输出其结果

注意事项：
建议将输入的字符数组和dp数组定义为全局变量以避免函数内部的变量泄漏。
鉴于题目要求寻找的是公共子序列而非子序列长度...因此建议将dp数组设置为存储字符串的形式。

复制代码

    #include <iostream>
    #include <string.h>
    #include <string>
    #include <algorithm>
    using namespace std;
    const int maxn=35;
    char a[maxn],b[maxn],c[maxn];
    string dp[maxn][maxn][maxn];    //易错点
    int main(){
    	cin>>(a+1)>>(b+1)>>(c+1);
    	int len1=strlen(a+1);
    	int len2=strlen(b+1);
    	int len3=strlen(c+1);
    //边界
    	for(int i=0;i<=len1;i++){
    		for(int j=0;j<=len2;j++){
    			for(int k=0;k<=len3;k++){
    			    dp[i][j][0]="";
    				dp[i][0][k]="";
    				dp[0][j][k]="";
    			}
    		}
    	}
    	//状态转移方程
    	for(int i=1;i<=len1;i++){
    		for(int j=1;j<=len2;j++){
    			for(int k=1;k<=len3;k++){
    				if(a[i]==b[j]&&a[i]==c[k]){
    				    dp[i][j][k]=dp[i-1][j-1][k-1]+a[i];
    				}else{
    					int l1=dp[i-1][j][k].length();
    					int l2=dp[i][j-1][k].length();
    					int l3=dp[i][j][k-1].length();
    					if(l1==max(l1,max(l2,l3))){
    					    dp[i][j][k]=dp[i-1][j][k];
    					}else if(l2==max(l1,max(l2,l3))){
    					    dp[i][j][k]=dp[i][j-1][k];
    					}else{
    					    dp[i][j][k]=dp[i][j][k-1];
    					}
    				}
    			}
    		}
    	}
    cout<<dp[len1][len2][len3]<<endl;
    	return 0;
    }

【2014-2】DP-字符串的编辑距离

题目描述：
把两个字符串变成相同的三个基本操作定义如下：
1.修改一个字符（如把a 变成b）
2.增加一个字符(如abed 变成abedd)
3.删除一个字符（如jackbllog 变成jackblog）
针对于jackbllog 到jackblog 只需要删除一个或增加一个l 就可以把两个字符串变为相同。
把这种操作需要的最小次数定义为两个字符串的编辑距离L。
编写程序计算指定文件中字符串的距离。输入两个长度不超过512 字节的ASCII 字符串，在
屏幕上输出字符串的编辑距离。
输入：
Hello world!
Hello word!
输出：
1

复制代码

    #include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    const int maxn=10010;
    int dp[maxn][maxn];
    string a,b;
    int main(){
    getline(cin,a);
    	getline(cin,b);
    	int len1=a.size();
    	int len2=b.size();
    //边界
    	for(int i=0;i<=len1;i++){
    	    dp[i][0]=i;
    	}
    	for(int j=0;j<=len2;j++){
    	   dp[0][j]=j;
    	}
    	//状态转移方程
    	for(int i=1;i<=len1;i++){
    		for(int j=1;j<=len2;j++){
    		    int flag=0;
    			if(a[i-1]!=b[j-1]){
    			    flag=1;
    			}
    			dp[i][j]=min(dp[i-1][j-1]+flag,min(dp[i-1][j]+1,dp[i][j-1]+1));
    		}
    	}
    	cout<<dp[len1][len2]<<endl;
    	return 0;
    }

【2014-4】DP-Hanoi 塔

问题描述

输入

输出

复制代码

    #include<iostream>
    #include<math.h>
    using namespace std;
    int acount=1,count=0;
    void hanoi(int n,char a,char b,char c){
    	if(n==1){
    		if((acount-count++)<=100){
    			cout<<count<<":"<<a<<"->"<<c<<endl;
    		}
    	}else{
    	    hanoi(n-1,a,c,b);
        if((acount-count++)<=100){
    			cout<<count<<":"<<a<<"->"<<c<<endl;
    		}
    		hanoi(n-1,b,a,c);
    	}
    }
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++){
    	    acount*=2;
    	}
    	acount--;
    	cout<<acount<<endl;
    	hanoi(n,'A','B','C');
    	return 0;
    }

【2016-1】DP-求最大连续公共字串长度

题目描述：给定两个输入字符串s1和s2，请计算这两个字符串的最大连续公共子串长度（该值小于1000）。问题分为两种情况：一种是要求计算连续最长公共子串的长度；另一种则是寻找非连续的最大公共子串长度（具体来说，则是寻找两个字符串之间连续字符序列的最大长度）。具体来说，则是寻找两个字符串之间连续字符序列的最大长度。
如下所述，则是按照寻找两个字符串之间特定模式匹配关系的方法理解。
输入：

输入包括两行：
- 第一行包含一个仅由数字组成的长字符串s1
- 第二行包含另一个仅由数字组成的长字符串s2
示例：
s1 = "1111hello2222"
s2 = "1133hello444"
输出：
输出结果为一个整数表示最大值
注意事项：
- 所谓"公共子串"是指两段完全相同的且在各自原位置上也完全相同的字符序列（即不仅字符相同而且顺序一致）
- 如果问题中对"不连续"的情况则需参考算法笔记上P435页的具体做法

复制代码

    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 1000;
    int dp[N][N] = {0};
    int main(){
    string A, B;
    getline(cin, A);
    getline(cin, B);
    int l1 = A.length();
    int l2 = B.length();
    int ans = 0;
    for(int i = 0; i < l1; i++){
        for(int j = 0; j < l2; j++){
            if(A[i] != B[j]){        //两个字符不同
                dp[i][j] = 0;
            }
            else if(i == 0 || j == 0){     //字符相同，而且是第一个字符
                dp[i][j] = 1;
                if(ans < 1)
                    ans = 1;
            }
            else{                          //字符相同，均不是第一个字符
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if(dp[i][j] > ans){
                    ans = dp[i][j];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
    }

【2018-3】DP-斐波那契数列

问题描述：一种规格为 $2 \times n$ 的地板需要被覆盖并采用规格为 $1 \times 2$ 和 $2 \times 1$ 的骨牌来覆盖整个地板。总共有多少种不同的铺设方式？并对结果取模数为 $999,983$ 进行计算，请确保 $n$ 的范围在整数范围 $\leq 10,000$ 之内。
输入：
6
输出：
13

复制代码

    #include<iostream>
    using namespace std;
    const int maxn=10010;
    int dp[maxn];
    int main()
    {
    	int n;
    	cin>>n;
    	dp[1]=1;
    	dp[2]=2;
    	for(int i=3;i<=n;i++){
    	    dp[i]=dp[i-2]+dp[i-1]%999983;
    	}
    	cout<<dp[n]<<endl;
    	return 0;
    }

【2019-2】DP-最大连续子序列和

给定一个数组及其长度，在区间[-106, 106]中的元素数量最大可达 $1 \times 1e^6$ 个。我们需要计算最长连续子序列的最大和，并且确保最终结果为正值。

复制代码

    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn=1000010;
    int A[maxn],dp[maxn];
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++){
    	    cin>>A[i];
    	}
    	//边界
    	dp[0]=A[0];
    	for(int i=1;i<n;i++){
    		//状态转移方程
    	    dp[i]=max(A[i],dp[i-1]+A[i]);
    	}
    	int max=0;
    	for(int i=0;i<n;i++){
    		if(dp[i]>max){
    		    max=dp[i];
    		}
    	}
    	if(max>0)
    	    cout<<max<<endl;
    	else
    		cout<<"No existence"<<endl;
    	return 0;
    }

二、二叉树问题

【2011-2】中序与后序求层次遍历

问题描述：输入树的中序和后序排列，输出树的层次遍历
输入：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出：
4 1 6 3 5 7 2

复制代码

    #include <stdio.h>
    #include <queue>
    using namespace std;
    struct node{
    int data;
    node* lchild;
    node* rchild;
    };
    int n,post[35],in[35];
    node* create(int postL,int postR,int inL,int inR){       //后序和中序构造二叉树
    	if(postL>postR){             
    	    return NULL;
    	}
    	node* root=new node;
    	root->data=post[postR];
    	int k;
    	for(k=inL;k<=inR;k++){
    	    if(in[k]==post[postR])
    			break;
    	}
    	int numleft=k-inL;
    	root->lchild=create(postL,postL+numleft-1,inL,k-1);
    	root->rchild=create(postL+numleft,postR-1,k+1,inR);
    	return root;
    }
    int num=0;
    void LayerOrder(node* root){     //层序遍历
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop();
        printf("%d",now->data);     
    		num++;
    		if(num<n)
    			printf(" ");
        if(now->lchild!=NULL){
            q.push(now->lchild);
        }
        if(now->rchild!=NULL){
            q.push(now->rchild);
        }
    }
    }
    int main(){
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    	    scanf("%d",&post[i]);
    	}
    	for(int i=0;i<n;i++){
    	    scanf("%d",&in[i]);
    	}
    node* root=create(0,n-1,0,n-1);
    	LayerOrder(root);
    	printf("\n");
    return 0;
    }

【2012-2】二叉树最大叶子间距

问题描述

复制代码

    #include <stdio.h>
    const int maxn=100;
    struct node{
    int lchild,rchild;
    }Node[maxn];
    int maxd;  //全局变量记录最大叶子间距
    //求最大叶子间距
    int maxDistance(int root,int &maxd){
    if(root==-1)
    		return -1;
    	int lefth=maxDistance(Node[root].lchild,maxd)+1;
    	int righth=maxDistance(Node[root].rchild,maxd)+1;
    	if(lefth+righth>maxd){
    	    maxd=lefth+righth;
    	}
    	return lefth>righth?lefth:righth;   //返回的是当前结点为根时的深度
    }
    int main(){
    	int n,left,right;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    	    scanf("%d %d",&left,&right);
    		Node[i].lchild=left;
    		Node[i].rchild=right;
    	}
    maxDistance(0,maxd);
    	printf("%d\n",maxd);
    return 0;
    }

【2014-3】二叉树前中后序遍历

题目描述：
输入一棵二叉树，输出树的前、中、后序遍历结果。
输入一个整数N（N<= 10000)，表示树中有N个结点（编号0~N-1）。
接下来N行，依次为结点0~结点N-1的左右孩子情况。
每行3个整数，F,L,R。L,R为F的左右孩子。L,R如果为-1表示该位置上没有孩子。
分三行分别输出树的前中后序遍历。
同一行中的数字，用一个空格间隔。
输入：
5
0 3 1
1 2 -1
2 -1 4
3 -1 -1
4 -1 -1
输出：
0 3 1 2 4
3 0 2 4 1
3 4 2 1 0

复制代码

    #include <stdio.h>
    const int maxn=10010;
    struct node{
    int lchild,rchild;
    }Node[maxn];
    int n,num=0;
    bool flag[maxn]={false};
    void print(int id){
    printf("%d",id);
    	num++;
    	if(num<n)
    		printf(" ");
    	else
    		printf("\n");
    }
    void preOrder(int root){
    if(root==-1)
    		return;
    	print(root);
    	preOrder(Node[root].lchild);
    	preOrder(Node[root].rchild);
    }
    void inOrder(int root){
    if(root==-1)
    		return;
    	inOrder(Node[root].lchild);
    	print(root);
    	inOrder(Node[root].rchild);
    }
    void postOrder(int root){
    if(root==-1)
    		return;
    	postOrder(Node[root].lchild);
    	postOrder(Node[root].rchild);
    	print(root);
    }
    int main(){
    	int x,left,right;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    	    scanf("%d%d%d",&x,&left,&right);
    		Node[x].lchild=left;
    		Node[x].rchild=right;
    		flag[left]=true;
    		flag[right]=true;
    	}
    	int root;
    	for(int i=0;i<n;i++){
    		if(flag[i]==false){
    		    root=i;
    		}
    	}
    	preOrder(root);
    	num=0;
    	inOrder(root);
    	num=0;
    	postOrder(root);
    return 0;
    }

【2019-3】二叉树的形态数

题目描述：给定二叉树的节点总数 n，输出二叉树形态总数，n<= 1000
输入：
3
输出：
5

复制代码

    #include <stdio.h>
    long long function(int n){    //防止阶乘的结果溢出，使用long long型
    	long long res;
    	if(n==0)
        res=0;
    	else if(n==1)
    		res=1;
    	else{
    		res=n;
    	    while(n>1){
    	        res=res*(n-1);
    			n--;
    	    }
    	}
    	return res;
    }
    int main(){
    	int n;
    	long long result;
    	scanf("%d",&n);
    	result=function(2*n)/function(n)/function(n+1);
    	printf("%lld\n",result);
    return 0;
    }

三、栈或队列问题

【2015-3】优先队列

题目描述：给出优先队列的实现，实现4个操作

• 当前优先级队列中存在插入操作：往队列里放入一个id为N、具有优先等级P的任务
• 下一个操作：获取当前优先级队列中最高的优先等级值对应的最小id；若当前无任务存在则返回-1
• 删除操作：从队列中删除具有指定id N的任务
• 队列规模查询：获取当前队列中任务总数

复制代码

    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <string>
    using namespace std;
    struct node{ 
    int id;  
    	int p;   //优先级
    };
    struct cmp{
    	bool operator()(node a,node b){
    		if(a.p!=b.p)
    		   return a.p<b.p;
    		else
           return a.id>b.id;
    	}
    };
    priority_queue<node,vector<node>,cmp> q;
    priority_queue<node,vector<node>,cmp> temp;  //临时优先队列
    void add(int id,int p){
    node a;
    	a.id=id;
    	a.p=p;
    	q.push(a);
    }
    void next(){
    node a;
    	a=q.top();
    	cout<<a.id<<" "<<a.p;
    }
    void remove(int id){
    	node a=q.top();
    	while(a.id!=id){
    	    node b=a;
    		q.pop();
    		temp.push(b);
    	}
    }
    int main(){
    	int id,p;
    	string str;
    cin>>str;
    	while(1){
    		if(str=='ADD'){
            scanf("%d%d",&id,&p);
    		    add(id,p);
    		}else if(str=='NEXT'){
    		    next();
    		}else if(str=='REMOVE'){
    		    scanf("%d",&id);
    			remove(id);
    		}else if(str=='COUNT'){
    			int num=q.size();
    			cout<<num<<endl;
    		}else 
    			break;
    	}
    return 0;
    }

【2016-2】后缀序列求值

题目描述：
给定一个后缀序列，要求求值，只有加减
输入：
123++4-
输出：
2

复制代码

    #include <iostream>
    #include <stack>
    #include <string>
    using namespace std;
    stack<int> s;
    int main(){
    	string str;
    	cin>>str;
    	int k;
    	for(int i=0;i<str.size();i++){
    		if(str[i]>='0'&&str[i]<='9'){
    		   int temp=str[i]-'0';
    		   s.push(temp);
    		}else if(str[i]=='+'){
    			int a=s.top();
    			s.pop();
    			int b=s.top();
    			s.pop();
            k=b+a;
    			s.push(k);
    		}else if(str[i]=='-'){
    		    int a=s.top();
    			s.pop();
    			int b=s.top();
    			s.pop();
            k=b-a;
    			s.push(k);
    		}
    	}
    	cout<<s.top()<<endl;
    return 0;
    }

【2016-3】字符串的哈夫曼编码最短长度

给定一个字符串（长度为100以内），计算其哈夫曼编码的最短总码长。
测试案例一：
abbcccdddd
结果为：19
测试案例二：
单词序列 'we', 'will', 'we', 'will', 'r', 'u'
结果为：50
主要思想：
基于优先级队列的数据结构配合频率统计与栈操作的组合方法

复制代码

    #include <iostream>
    #include <map>
    #include <vector>
    #include <queue>
    #include <string>
    using namespace std;
    map<char,int> mp;
    priority_queue<int,vector<int>,greater<int>> q;
    string str;
    int main(){
    	getline(cin,str);
    	int len=str.length();
    	for(int i=0;i<len;i++){
    		if(mp.find(str[i])==mp.end()){
    		    mp[str[i]]=1;
    		}else
    			mp[str[i]]++;
    	}
    	for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++){
    		q.push(it->second);
    	}
    	int ans=0;
    	while(q.size()!=1){
    		int temp;
    	    int a=q.top();
    		q.pop();
    		int b=q.top();
    		q.pop();
    		temp=b+a;
    		ans+=temp;
    		q.push(temp);
    	}
    	cout<<ans<<endl;
    return 0;
    }

四、图

【2013-3】图的BFS遍历

题目要求：创建一个表格，请计算指定起点与终点之间无法经过质数行的最短路径长度。
输入：
3
1 4
9 32
10 12
输出结果：
Case 1: 距离为 $distance$ 单位
Case 2: 最短路径长度为7单位
Case 3: 没有可行路径

复制代码

    #include <iostream>
    #include <string>
    #include <cstring>
    #include <cctype>
    #include <cstdio>
    #include <map>
    #include <stack>
    #include <cmath>
    #include <queue>
    #include <algorithm>
    #define UP 0
    #define DOWN 1
    #define LEFT 2
    #define RIGHT 3
    using namespace std;
    const int maxn=410;
    int g[maxn][maxn];
    int vis[maxn][maxn];
    const int mov[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
    bool isPrime(int v)
    {
    int ed=sqrt(v);
    for(int i=2; i<=ed; ++i)
        if(v%i==0) return false;
    return true;
    }
    int nextDir(int d)
    {
    if(d==RIGHT) return UP;
    else if(d==UP) return LEFT;
    else if(d==LEFT) return DOWN;
    else if(d==DOWN) return RIGHT;
    }
    pair<int,int> pos[10005];
    void init()
    {
     
    int val=0;
    int x=200,y=200;
    g[x][y]=++val;
    pos[val]=make_pair(x,y);
    int d=RIGHT;
    int len=2;
    while(len<=105)
    {
        for(int i=1; i<len; ++i)
        {
            x=x+mov[d][0];
            y=y+mov[d][1];
            ++val;
            if(isPrime(val)) g[x][y]=0;
            else
            {
                g[x][y]=val;
                if(val<=10000)
                    pos[val]=make_pair(x,y);
                }
        }
        d=nextDir(d);
        for(int i=1; i<len; ++i)
        {
            x=x+mov[d][0];
            y=y+mov[d][1];
            ++val;
            if(isPrime(val)) g[x][y]=0;
            else
            {
                g[x][y]=val;
                if(val<=10000)
                    pos[val]=make_pair(x,y);
                }
     
        }
        d=nextDir(d);
        ++len;
    }
     
    }
     
    int bfs(int st,int ed)
    {
     
    memset(vis,0,sizeof(vis));
    queue<pair<int,int> > que;
    que.push(pos[st]);
    while(!que.empty())
    {
        pair<int,int> p=que.front();
        que.pop();
        for(int i=0; i<4; ++i)
        {
            int nx=p.first+mov[i][0],ny=p.second+mov[i][1];
            if(vis[nx][ny]||g[nx][ny]==0) continue;
            vis[nx][ny]=vis[p.first][p.second]+1;
            if(g[nx][ny]==ed) return vis[nx][ny];
            que.push(make_pair(nx,ny));
        }
    }
    return -1;
    }
    int main()
    {
    init();
    int x,y,kase=0;
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        printf("Case %d: ",++kase);
        if(x==y) printf("0\n");
        else
        {
            int ans=bfs(x,y);
            if(ans==-1) puts("impossible");
            else printf("%d\n",ans);
        }
    }
    return 0;
    }

五、查找

【2014-1】二分查找

题目描述

复制代码

    #include<iostream>
    #include<stdio.h>
    using namespace std;
    int count=0,input[10001];
    void search(int s,int e,int key)
    {
    count++;
    	int mid=(s+e)/2;
    	if(input[mid]==key) return;
    	else if(input[mid]>key) search(s,mid,key);
    	else search(mid,e,key);
    }
    int main()
    {
    	freopen("p1.in","r",stdin);
    	freopen("p1.out","w",stdout);
    	int N,key;
    	cin>>N;
    	for(int i=0;i<N;i++) cin>>input[i];
    	cin>>key;
    	search(0,N-1,key);
    	cout<<count<<endl;
    	fclose(stdin);
    	fclose(stdout);
    return 0;
    }

六、堆排序

【2012-1】1000名求前30%

为了解决排序问题，在面对1000个成绩时需要输出前30%。在处理十组数据时需要筛选出前三名。具体思路基于堆排序的方法进行设计与实现。

复制代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
     //给定十个元素输出最大的前三个，元素从下标1开始存储
    int heap[11] = {0, 3, 1, 2, 6, 5, 4, 9, 8, 7, 10};
    int n = 10;      //元素个数
     
    //对heqap数组在loe和high范围内进行调整
    //low为父节点，high一般为堆的最后一个元素下标
    void downAdjust(int low, int high){
    int i = low, j = i * 2;     //i为调整节点，j为左孩子
    while(j <= high){           //如果存在左孩子
        if(j + 1 <= high && heap[j + 1] > heap[j]){     //如果右孩子存在，且值大于左孩子
            j = j + 1;          //j来存储右孩子下标
        }
        //孩子中最大的权值大于要调整的节点
        if(heap[j] > heap[i]){
            swap(heap[j], heap[i]);
            i = j;          //继续调整以j为父节点的子树
            j = i * 2;
        }
        else
            break;
    }
    } 
    //建树
    void createHeap(){
    for(int i = n / 2; i >= 1; i--){        //i从第一个非叶节点开始，直到根结点
        downAdjust(i, n);
    }
    } 
    void heapSort(){
    createHeap();   //建堆
    printf("%d", heap[1]);    //输出第一个最大值
    for(int i = n; i > 8; i--){     //倒着枚举，直到输出符合题目要求的数量
        swap(heap[i], heap[1]);     //交换heap[i]与堆顶
        downAdjust(1, i - 1);       //调整堆顶
        printf(" %d", heap[1]);     //调整过后，堆顶元素为最大值，输出
    }
    printf("\n");
    }
     
    int main(){
    heapSort();
    return 0;
    }

七、基础题（水题）

【2012-3】字符串的重复输出

对于一个字符串例如ABC再给定一个整数例如3输出AAA、BBB和CCC即可

复制代码

    #include <string>
    #include <iostream>
    #include <cstdio>
    using namespace std;
     
    int main(){
    string str;
    getline(cin, str);
    int n;
    cin >> n;
    for(int i = 0; i < str.size(); i++){
        for(int j = 0; j < n; j++){
            printf("%c", str[i]);
        }
    }
    printf("\n");
    return 0;
    }

【2013-1】字符串匹配

题目描述：给定主串M和模式串P，请计算P在M中各子串起始字符的位置，并记录这些起始位置在P中的索引值。特别地，在模式串P中第一个字符所在的位置定义为0号位置。输入部分包含若干测试用例：

第一行是一个整数N（具体数值由输入决定），表示后续将要给出N个测试用例。
接下来的N行分别给出主串M和对应的模式串P。
其他可能的情况则由后续的具体数值来确定。
输出部分：
每个测试用例的结果占一行。
结果包括多个整数（以空格分隔），表示各个结果对应的索引值。
其中第一行的数字表示测试用例的数量。
输入：
2
ababababa
ababa
aaa
aa
输出：
0 2 4
0 1
（相邻位置之间用一个空格隔开）

复制代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    char str1[100],str2[100];
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	while(n--){
    		memset(str1,0,sizeof(str1));
    		memset(str2,0,sizeof(str2));
    		scanf("%s",str1);
    		scanf("%s",str2);
    		int len1=strlen(str1);
    		int len2=strlen(str2);
    		int idx;
    		for(int i=0;i<len1;i++){
    			if(str1[i]!=str2[0])
    			  continue;
    			idx=i;
    			if(len1-i<len2)break;
    			for(int j=0;j<len2;j++){
    				if(str1[i]!=str2[j])
    					break;
    				i++;
    				if(j=len2-1)
    					printf("%d ",idx);
    			}
    			i=idx;
    		}
    	}
    	system("pause");
    	return 0;
    }

【2013-2】A Famous ICPC Team

题目描述：提供四个立方体箱的尺寸，请计算能够容纳这四立方体箱的大立方体的最小边长是多少（答案需为整数）。
输入：
数量为1个
给出一组四数值作为各个立方体箱的尺寸参数
输出：
4

复制代码

    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    int main()
    {
    int a[4],cas = 1;
    int x,y,ans;
    while(~scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3]))
    {
        sort(a,a+4);
        printf("Case %d: %d\n",cas++,a[2]+a[3]);
    }
    return 0;
    }

【2015-1】长方形中的正方形

题目描述

程序运行结果

复制代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
     
    int main(){
    int a, b;   //a 长 , b 宽
    scanf("%d%d", &a, &b);
    int ans = 0;
    while(a != b){
        ans++;
        if(a < b){
            swap(a, b);
        }
        a = a - b;
    }
    printf("%d", ans + 1);
    return 0;
    }

【2015-2】a与b得到c

输入：

复制代码

    #include <cstdio>
    int main(){
    long long a, b, c;
    scanf("%lld%lld%lld", &a, &b, &c);
    if(a + b == c || a * b == c){
        printf("YES\n");
    }
    else if(a - b == c || b - a == c){
        printf("YES\n");
    }
    else if(a / b == c  || b / a == c){
        printf("YES\n");
    }
    else{
        printf("NO\n");
    }
    return 0;
    }

【2016-1】求最大公共字串长度

题目描述

复制代码

    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N = 1000;
    int dp[N][N] = {0};
     
    int main(){
    string A, B;
    getline(cin, A);
    getline(cin, B);
    int l1 = A.length();
    int l2 = B.length();
    int ans = 0;
    for(int i = 0; i < l1; i++){
        for(int j = 0; j < l2; j++){
            if(A[i] != B[j]){        //两个字符不同
                dp[i][j] = 0;
            }
            else if(i == 0 || j == 0){     //字符相同，而且是第一个字符
                dp[i][j] = 1;
                if(ans < 1)
                    ans = 1;
            }
            else{                          //字符相同，均不是第一个字符
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if(dp[i][j] > ans){
                    ans = dp[i][j];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
    }

【2017-1】中位数

题目描述：给定一个整数序列，求中位数。如果序列个数为奇数，中位数为升序的中间位置，如果是偶数，这位升序的中间两个数的平均值。
输入
输入包含多组测试数据，每一组第一行为n(n<104)表示这个序列的个数，接下来有n个整数k(0<k<231-1)
输出
输出这个序列的中位数
输入1：
5
2 1 4 3 5
输出1：
3
输入2：
4
1 4 3 2
输出2：
3

复制代码

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int N = 10010;
    int num[N];
     
    int main(){
    int n;
    scanf("%d", &n);
    for(int i =  0; i < n; i++){
        scanf("%d", &num[i]);
    }
    sort(num, num + n);
    if(n % 2 == 0){     //n为偶数
        if((num[n / 2] + num[n / 2 - 1]) % 2 == 0){     //中间两位平均值为整数
            printf("%d\n", (num[n / 2] + num[n / 2 - 1]) / 2);
        }
        else{
            printf("%.lf\n", (num[n / 2] + num[n / 2 - 1]) / 2.0);
        }
    }
    else{       //n为奇数
        printf("%d\n", num[n / 2]);
    }
    return 0;
    }

【2017-2】9位ISBN，求其校验位

题目描述：给定一个由9位数字组成的ISBN号码，请计算其校验码。ISBN格式为如下的分组形式：X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z-A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
输入：
2-02-033598
输出：
2-02-033598-0

复制代码

    #include <cstdio>
    #include <cstring>
    char str[15];
    int a[10];
     
    int main(){
    scanf("%s", str);
    int count = 0;
    for(int i = 0; i < 11; i++){
        if(str[i] != '-'){
            a[count++] = str[i] - '0';
        }
    }
    int s = 0;
    int d = 10;
    for(int i = 0; i < 9; i++){
        s += a[i] * d;
        --d;
    }
    int m = s % 11;
    int t = 11 - m;
    if(t < 10){
        printf("%s-%d\n", str, t);
    }
    else if(t == 10){
        printf("%s-X\n", str);
    }
    else{
        printf("%s-0\n", str);
    }
    return 0;
    }

【2018-1】求众数

题目描述：
众数即为一个序列中出现频率最高的数值。若存在多个众数，则选择其中较小的一个作为结果。
样例输入：
第一行为整数N（满足1≤n≤10^5），第二行为包含N个整数的序列。
具体示例如下：
测试用例的数量为8。
具体数据如下：
[10,3,8,8,3,2,2,2]
输出结果：
对于测试用例中的数据集[...], 输出相应的众数或最小众数值.
例如，在第一个测试用例中得到的结果是...

复制代码

    #include <cstdio>
    #include <map>
    #include <algorithm>
    using namespace std;
    map<int, int> mp;
     
    int main(){
    int n, x;
    int maxn = 0;
    int maxp;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        if(mp.find(x) != mp.end()){     //这个数已经出现过
            mp[x]++;
        }
        else{
            mp[x] = 1;
        }
    }
    for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
        if(it->second > maxn){      //已经从小到大排好序，取>即可
            maxn = it->second;      //众数出现的次数
            maxp = it->first;       //众数的值
        }
    }
    printf("%d", maxp);

【2018-2】解一元一次方程

题目要求：编写程序实现一元一次方程求解功能。具体要求如下：

输入为一个由字符组成的字符串
当存在解时进行计算并返回结果
结果格式为" x = 数字 "（不带引号）
当有无限多解时返回信息" infinite solutions"
当无解时返回信息" no solution"
输入字符串长度必须小于等于 256 字符
示例输入：" 2x +4 -3x = x - 2 "
示例输出：" x = 2 "

复制代码

    #include <cstdio>
    #include <iostream>
    #include <string>
    using namespace std;
    string str;
     
    int main(){
    cin >> str;
    int a = 0, b = 0;   //系数、常数
    int sym = 1, flag = 1;      //sym表示数字之前的符号，flag表示等号的左右（初始值为1，表示在左面）
    int i = 0;          //访问字符串的下标
    while(i < str.size()){
        if(str[i] == '='){
            sym = 1;
            flag = -1;
        }
        else if(str[i] == '+'){
            sym = 1;
        }
        else if(str[i] == '-'){
            sym = -1;
        }
        else{       //遇到数字或者x
            int t = 0;      //暂存遇到的数字值
            while(i < str.size() && str[i] >= '0' && str[i] <= '9'){    //遇到数字，计算数值
                t = 10 * t + (str[i] - '0');
                ++i;
            }
            //当表达式最后一位是数字时，比如2x+4-3x=x-2,上面while的循环会使i >= str.size()成立
            if(i >= str.size()){                
                b -= t * sym;
                break;
            }
            if(str[i] == 'x' && t == 0){        //如果x之前的系数为正负1时，要单独判断，因为此时t=0
                a += sym * flag;
            }
            else if(str[i] == 'x'){     //处理系数
                a += t * sym * flag;
            }
            else{                       //处理常数
                b += t * sym * flag;
                continue;               //直接进行下一次循环是因为：上面while循环中处理数字之后已经++i
            }
        }
        i++;
    }
    if(a == 0 && b == 0){
        printf("infinite solutions\n");
    }
    else if(a != 0 && b % a == 0){
        printf("x=%d\n", -b/a);
    }
    else{
        printf("no solution\n");
    }
    return 0;
    }

【2019-1】日期处理

题目描述：输入日期格式:YYYYMMDD，求与20190205的相隔的天数。
输入：20190208
输出：3

复制代码

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
     
    //month[2][0]平年， month[2][1]闰年
    int month[13][2] = {{0,0}, {31, 31}, {28,29}, {31,31}, {30,30}, {31, 31}, {30,30},{31, 31}, {31, 31}, {30,30}, {31, 31},{30,30},{31, 31}} ;
     
    bool isLeapYear(int year){
    if(year % 400 == 0 || (year % 4 == 0  && year % 100 != 0)){
        return true;
    }
    return false;
    }
     
    int main(){
    int time1, time2 = 20190205;
    scanf("%d", &time1);
    if(time1 > time2){
        swap(time1, time2);
    }
    int y1, m1, d1, y2, m2, d2;
    y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
    y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
    int num = 0;
    while(y1 < y2 || m1 < m2 || d1 < d2){
        d1++;
        num++;
        if(d1 == month[m1][isLeapYear(y1)] + 1){
            m1++;
            d1 = 1;
        }
        if(m1 == 13){
            y1++;
            m1 = 1;
        }
    }
    cout << num << endl;
    return 0;
    }

八、补充2020年机试题

A、斗牛

题目描述

输入格式

输出格式

输入输出样例

代码样例

复制代码

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    //回溯法得到其中三数之和，若没有10的倍数，返回-1
    int judge(int sum,vector<int>& visited,vector<int>D,int num) {
    	if (num > 3)	return -1;
    	if (num == 3 && sum % 10 == 0)	return sum;
    	for (int i = 0; i < D.size(); i++) {
    		if (visited[i] == 0) {
    			visited[i] = 1;
    			int f = judge(sum + D[i], visited, D, num + 1);
    			if (f != -1)	return f;
    			visited[i] = 0;
    		}
    	}
    	return -1;
    }
    
    int main()
    {
    	int T;
    	cin >> T;
    	int N = 5;
    	vector<vector<int>>data(T, vector<int>(N));
    	for (int i = 0; i < T; i++) {
    		for (int j = 0; j < N; j++) {
    			cin >> data[i][j];
    		}
    	}
    	vector<int>result;
    	vector<int> visited(N, 0);	//记录已被访问过的数
    	for (int i = 0; i < T; i++) {
    		int sum = 0, num = 0;
    		fill(visited.begin(), visited.end(), 0);
    		int flag = judge(sum, visited, data[i], num);
    		if (flag != -1) {	//存在三数之和为10的倍数
    			int S = 0;
    			for (int j = 0; j < N; j++)	S += data[i][j];
    			result.push_back((S - flag) % 10);	//总和减去三数之和就是剩余两数之和
    		}
    		else  result.push_back(flag);
    	}
    	for (int i = 0; i < result.size(); i++)	cout << result[i] << endl;
    }

B、打地鼠

题目描述

输入格式

输出格式

复制代码

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int main()
    {
    	int n, d;
    	cin >> n >> d;
    	vector<int>data(n);
    	for (int i = 0; i < data.size(); i++)	cin >> data[i];
    	sort(data.begin(), data.end());	//从小到大排序
    	int num = 0;
    	if (n < 2) {	//只有一个整数
    		cout << num << endl;
    		return 0;
    	}
    
    	for (int i = 0, j = 1; j < data.size();) {
    		if (data[j] - data[i] >= d) {
    			num++;
    			i = j;
    			j++;
    		}
    		else j++;
    	}
    	if (num == 0)	cout << num << endl;	//没有符合条件的数
    	else  cout << num + 1 << endl;	//由于每次只将较小的数加入结果集，因此最后还需将最后的大数加入结果集
    	return 0;
    }

C、排队打饭

题意说明

复制代码

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int main()
    {
    	int n;
    	cin >> n;
    	vector<vector<long long int>>data(n, vector<long long int>(3));
    	for (int i = 0; i < data.size(); i++){
    		for (int j = 0; j < data[i].size(); j++) {
    			cin >> data[i][j];
    		}
    	}
    	long long int endtime = 0;	//记录上一个学生打饭结束的时间
    	vector<long long int>result;
    	for (int i = 0; i < data.size(); i++) {
    		if (data[i][0] >= endtime) {	//第i位学生达到时无人打饭，可以直接开始打饭
    			result.push_back(data[i][0]);
    			endtime = data[i][0] + data[i][1];
    		}
    		else {	//第i位学生正好有人打饭,那么第i位学生的等待时间=上一位学生的结束时间-第i位学生的开始时间
    			if (endtime - data[i][0] > data[i][2])	result.push_back(-1);	
    			else {
    				result.push_back(endtime);
    				endtime = endtime + data[i][1];
    			}
    		}
    	}
    	for (int i = 0; i < result.size(); i++)	cout << result[i] << ' ';
    	return 0;
    }

D、二叉搜索树

输⼊格式

输出格式

样例输⼊

样例輸出

复制代码

    #include <iostream>
    #include <vector>
    #include <map>
    #include <algorithm>
    using namespace std;
    int main(){
    int n;
    	cin >> n;
    	vector<int>father(n + 1);
    	map<int, int>dict;
    	dict[0] = 0;
    	int maxn = 0;
    	for (int i = 0; i < n; i++) {
    		int t;
    		cin >> t;
    		if (t > maxn) {
    			father[t] = maxn;
    			dict[t] = dict[maxn] + 1;
    			maxn = t;
    		}
    		else {
    			map<int, int>::iterator small = dict.upper_bound(t);
    			map<int, int>::iterator big = small--;
    			if (big->second > small->second) {
    				father[t] = big->first;
    				dict[t] = big->second + 1;
    			}
    			else {
    				father[t] = small->first;
    				dict[t] = small->second + 1;
    			}
    		}
    	}
    	for (int i = 1; i < father.size(); i++)	cout << father[i] << ' ';
    }

E、序列

输⼊

复制代码

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <climits>
    #include <math.h>
    using namespace std;
    
    #define N 10
    
    int main() {
    	int n;
    	cin >> n;
    	vector<int>A(n);
    	for (int i = 0; i < A.size(); i++)	cin >> A[i];
    	vector<vector<int>>dp(n, vector<int>(N, INT_MAX));
    	for (int i = 0; i < N; i++)	dp[0][i] = abs(i - A[0]);
    	for (int i = 1; i < A.size(); i++) {
    		for (int j = 0; j < N; j++) {
    			for (int k = 0; k < N; k++) {
    				dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(A[i] - j) + (j - k)*(j - k));
    			}
    		}
    	}
    	int result = INT_MAX;
    	for (int i = 0; i < N; i++)	result = min(result, dp[n - 1][i]);
    	cout << result;
    	return 0;
    }

温馨提示：资源整理不易，看到最后，记得一键三连奥，笔芯！！！

全部评论 (0)

还没有任何评论哟~

【机试】2011-2020年复旦大学考研复试机试真题

题型分布目录一、DP问题【20111】DP最长公共子序列LCS 【20142】DP字符串的编辑距离【20144】DPHanoi塔【20161】DP求最大连续公共字串长度【20183】DP斐波...

2020复旦大学计算机考研机试题详解

写在前面复旦巨喜欢考动规，建议好好准备 A、斗牛给定五个09范围内的整数a1,a2,a3,a4,a5。如果能从五个整数中选出三个并且这三个整数的和为10的倍数（包括0），那么这五个整数的权值即为剩...

北航研究生复试机试真题-2011年

2011年北航机试真题 1、字符串扩展题目描述：从键盘上输入包含“”的字符串，将其扩展为等价的完整字符，例如将ad扩展为abcd，并输出扩展后的字符串。

复旦大学2020考研机试题-编程能力摸底试题（A-E）

A.斗牛给定五个09范围内的整数a1,a2,a3,a4,a5。如果能从五个整数中选出三个并且这三个整数的和为10的倍数（包括0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对10取余的结果...

13-19年复旦大学计算机学院研究生复试机试题

（不保证代码完全正确，自己敲的可能存在不完善的地方，请各位大佬发现后指出，谢谢！）暂时结束。试题列表 2019上机题 2018上机题 2017上机题 2016上机题 2015上机题 2014上机题...

清华大学历年考研复试机试真题 -图

题目描述 TimeLimit:1000ms MemoryLimit:256mb 给定一个有n个点，m条边的有向图。图中第i个点的价值是vi，每条边有一个代价z，不同的边代价可能不一样。

复旦18考研机试真题(3)--骨牌

题目：有2n的地板，用12和21的骨牌进行铺地板。问共有多少种情况。结果对999983取余。1<=n<=10000。样例：输入： 6 输出： 13 分析：这是一道简单的DP问题。

复旦20考研机试真题(A)--斗牛

给定5个09范围内的整数a1,a2,a3,a4,a5。如果能从五个整数中选出三个并且这三个整数的和为10的倍数（包括0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对10取余的结果，显然如果...

复旦研究生历年机试试题

2014计算两个字符串的编辑距离问题定义把两个字符串变成相同的三个基本操作定义如下： 1.修改一个字符（如把a变成b） 2.增加一个字符如abed变成abedd 3.删除一个字符（如jackbll...

2020复旦计算机专硕考研复试经验

写在前面本人在复试前也上网搜过复旦计算机的复试经验，但是发现实在是太少了。所以在这里写下自身的考研复试经验分享，希望可以给后来人带来一点作用。献丑，献丑！！！ 2020情况比较特殊，所以复试也有所不...

是否确定退出登录?

【机试】2011-2020年复旦大学考研复试机试真题

题型分布目录

一、DP问题

【2011-1】DP-最长公共子序列LCS

【2014-2】DP-字符串的编辑距离

【2014-4】DP-Hanoi 塔

【2016-1】DP-求最大连续公共字串长度

【2018-3】DP-斐波那契数列

【2019-2】DP-最大连续子序列和

二、二叉树问题

【2011-2】中序与后序求层次遍历

【2012-2】二叉树最大叶子间距

【2014-3】二叉树前中后序遍历

【2019-3】二叉树的形态数

三、栈或队列问题

【2015-3】优先队列

【2016-2】后缀序列求值

【2016-3】字符串的哈夫曼编码最短长度

四、图

【2013-3】图的BFS遍历

五、查找

【2014-1】二分查找

六、堆排序

【2012-1】1000名求前30%

七、基础题（水题）

【2012-3】字符串的重复输出

【2013-1】字符串匹配

【2013-2】A Famous ICPC Team

【2015-1】长方形中的正方形

【2015-2】a与b得到c

【2016-1】求最大公共字串长度

【2017-1】中位数

【2017-2】9位ISBN，求其校验位

【2018-1】求众数

【2018-2】解一元一次方程

【2019-1】日期处理

八、补充2020年机试题

A、斗牛

B、打地鼠

C、排队打饭

D、二叉搜索树

E、序列

全部评论 (0)

相关文章推荐

【机试】2011-2020年复旦大学考研复试机试真题

2020复旦大学计算机考研机试题详解

北航研究生复试机试真题-2011年

复旦大学2020考研机试题-编程能力摸底试题（A-E）

13-19年复旦大学计算机学院研究生复试机试题

清华大学历年考研复试机试真题 -图

复旦18考研机试真题(3)--骨牌

复旦20考研机试真题(A)--斗牛

复旦研究生历年机试试题

2020复旦计算机专硕考研复试经验