复旦大学研究生机试（2019）

article/2025/4/28 12:48:32

1. 计算机学院

今年的题目可以说是挺难的，第一题虽然像是送分题，实际上也不是很简单。第二题第三题是动态规划问题，而且复旦据说会卡大数，今年150人考生据说只有一个AC，大部分人只做出第一题，个别零分。

1.1 相隔天数

题目：

输入日期格式：YYYYMMDD，求与20190205相隔的天数。
例：
输入：
20190208
输出：
3

解题：

这道题是《王道上机指南》原题。
这道题反正对于我这种完全不知道闰年定义的人来说是很难的，毕竟计算日期，闰年二月是有28天和29天的区分的。
*闰年：*当年数不能被100整除时，但若能被4整除则为闰年，或者其能被400整除也是闰年。
除了闰年的定义以外，我们可以顺序统一到同一年，同一月，同一天。
这样分步解决问题。

#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
using namespace std;bool isrun(int year){if((year%100!=0&&year%4==0)||(year%400==0))return true;elsereturn false;
}int main()
{string str;int year, month, day,countday = 0;scanf("%4d%2d%2d",&year,&month,&day);int mdays[]={31,28,31,30,31,30,31,31,30,31,30,31};//统一到同一年while(year>2019){year--;if(isrun(year))countday+=366;elsecountday+=365;}while(year<2019){if(isrun(year))countday-=366;elsecountday-=365;year++;}//统一到同一月while(month>2){month--;if(month!=2){countday += mdays[month-1];}else if(isrun(year)){countday+=29;}else{countday+=28;}}while(month<2){if(month!=2){countday -= mdays[month-1];}else if(isrun(year)){countday-=29;}else{countday-=28;}month++;}//计算同一月的日期差countday+=day-5;cout<<countday<<endl;return 0;
}

1.2 最大连续子序列

题目：

给定一个数字序列A1,A2…An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大和。
例：
输入：
6
-2 11 -4 13 -5 -2
输出：
20

解题：

这是一道动态规划题，一般有两种思路。
第一种解法比较朴素，时间复杂度是O(n^2)，其实也是暴力枚举，把所有结果都算出来取最大值；也大概是我能在考场上想出的最优解了（伤心）。

#include <iostream>
#include <stdio.h>
#include <vector>
#include <limits.h>
using namespace std;int main()
{int N;scanf("%d",&N);vector<int> vec;while(N-->0){int temp;scanf("%d",&temp);vec.push_back(temp);}int maxa = INT_MIN;for(int i =0;i<vec.size();i++){int currSum = 0;for(int j = i;j<vec.size();j++){currSum+=vec[j];if(currSum>maxa)maxa = currSum;}}cout<<maxa<<endl;return 0;
}

第二种解法，动态规划解法，时间复杂度O(n)，没有什么第二种思路了，我完全没有思路，只能看看大佬博客维持生活这样子了：
https://www.cnblogs.com/conw/p/5896155.html

1.3 有向树形态

题目：

求N个结点能够组成的二叉树的个数。
例：
输入：
3
输出：
5

求解：

这道题，我是说不清楚难不难，我是没什么想法，不过有个卡特兰数在我初试的时候接触过，原理是：卡特兰数原理
所以，我就这样用通项公式就可以吧。
由上诉大神博客可知，通项公式为：
在这里插入图片描述
因此代码为（据说数字很刁钻，需要特特别大的数字，我也没什么办法，用long long可能只能过一部分用例）：

#include <iostream>
using namespace std;long long Cmn(long long n) {long long fengzi = 1, fengmu = 1;for (int i = 2 * n; i > n; i--) {fengzi *= i;}for (int i = n; i > 1; i--) {fengmu *= i;}return fengzi / fengmu;
}int main() {long long N;cin >> N;cout << Cmn(N) / (N + 1) << endl;return 0;
}

事实上，经过测试，使用C++long long只能通过N=14；
下面尝试使用Java来解决（只能说Java太强了，解决这道题完全没有压力，可以ak）：

import java.math.BigInteger;
import java.util.Scanner;
public class Main {public static BigInteger Cmn(int n){BigInteger fengzi = new BigInteger("1"),fengmu = new BigInteger("1");for (int i = 2 * n; i > n; i--) {fengzi = fengzi.multiply(new BigInteger(Integer.toString(i)));}for (int i = n; i > 1; i--) {fengmu = fengmu.multiply(new BigInteger(Integer.toString(i)));}return fengzi.divide(fengmu);}public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int N = sc.nextInt();System.out.println(Cmn(N).divide(new BigInteger(Integer.toString(N+1))).toString());}
}

也可以在危险的边缘试探一下Python：

def Cmn(n):fengzi=int(1)fengmu=int(1)for i in range(n+1,2*n+1):fengzi *= ifor i in range(2, n+1):fengmu *= ireturn fengzi / fengmuN = int(input())
print(int(Cmn(N)/(N+1)))

有点慢的，但可以计算比较大的数字，500左右(3s)。

2. 工研院

现场做了，就懒得再码代码一便了。
感觉和计算机学院的题目难度相差不大，每道题最后几个数据都很大，复旦今年都是卡大数。

2.1 手机按键

题目：

模拟老式手机输入，九宫格布局如下：

[ 1 ] [ 2ABC ] [ 3DEF  ]
[ 4GHI  ] [ 5JKL ] [ 6MNO  ]
[ 7PQRS ] [ 8TUV ] [ 9WXYZ ][ 0空  ]

题目输入为数字或者’-’，其中‘-’代表手机输入时等待的时间间隔，数字表示点击某个按键的次数。比如点击两次2，则输出为B，四次2，则输出为A。
例：
输入：
255
输出：
AK
输入（等待间隔‘-’可以无限长，也可以没有）：
2222------55
输出：
AK

2.2 服务器维护

题目：

假设有编号从1-N的服务器，首先给出服务器个数，再给出一组服务器状态。
然后给出一次数字，表示修改状态次数，接下来输入为i，j，x，意思是使用x修改从i到j的服务器。
最后输出所有服务器状态
例：
输入：
5
1 2 2 3 1
2
1 2 5
2 5 -1
输出：
6 6 1 2 0

2.3 计算通讯代价

题目：

给出一个树，计算每个节点到其他节点的通讯代价的总和，假如树为

1————2————3

则结点1，2，3通讯代价分别为：3，2，3
例：
输入：
3
1 2
2 3
输出：
3 2 3
输入说明： 3，表示共有3个结点，接下来的两行，表示该树节点之间的相连情况。