2019年复旦大学机试题

article/2025/4/28 17:08:08

机试：

一、计算机学院：

1、
在这里插入图片描述
算法笔记上有类似题，且time与time2都是输入。
而本体time是输入，time2是题目给的。
设置time与time2，为计算方便设定让time恒小于time2。
方法：从time（较早的日期）一天一天加，直到time2为止。期间设置一个int型的num来记录相差天数。

#include <cstdio>
#include <algorithm>
using namespace std;
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}};int isrunnian(int y){int flag = 0;if((y % 4 == 0 && y % 100 != 0) || y % 400 == 0){flag = 1;}return flag;
}int main(){int time, num = 0;int time2 = 20190205;scanf("%d", &time);if(time > time2){		//time恒小于time2int temp = time2;time2 = time;time = temp;}int yy = time / 10000, mm = time % 10000 / 100, dd = time % 100;int YY = time2 / 10000, MM = time2 % 10000 / 100, DD = time2 % 100;while(yy != YY || mm != MM || dd != DD){dd++;num++;if(dd > month[mm][isrunnian(yy)]){mm++;dd = 1;}if(mm > 12){yy++;mm = 1;}}printf("%d", num);return 0;}

2、
在这里插入图片描述
完全是算法笔记的原题，求最大连续子序列和，在这里使用动态规划来解。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1000010;
int A[maxn], dp[maxn];
int main(){int n;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &A[i]);}dp[0] = A[0];for(int i = 1; i < n; i++){if(dp[i - 1] + A[i] > A[i]){dp[i] = dp[i - 1] + A[i];}else{dp[i] = A[i];}}int ans = dp[0];for(int i = 1; i < n; i++){if(dp[i] > ans){ans = dp[i];}}printf("%d", ans);return 0;
}

3、
在这里插入图片描述
emmm，这题要是自己一一实现的话略微困难，而且本题适合用Java的大数来做，用C++会有案例不能通过。
通过百度得知，本题用卡特兰数（Catalan数）可以直接解决。。。

由于Java不会用。。。所以给出C++版本：

#include <cstdio>int main(){int n;scanf("%d", &n);long long num, a = 1, b = 1;for(int i = 2 * n; i > n; i--){a *= i;}for(int i = n; i > 0; i--){b *= i;}printf("%lld", a / b / (n + 1));return 0;
}

对没错，就是这么简单几行代码，不会这个公式就很难，会这个公式轻松解决。不过依旧只能处理n <= 14的情况，n > 14则会导致输出错误。

二、工研院：

1、
在这里插入图片描述
还可以挺简单，就是设数组有点累。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
char numtochar[10][5] = {{'0', '0', '0', '0', '0' }, {'0', '0', '0', '0', '0'}, {'A', 'B', 'C', '0', '0'}, {'D', 'E', 'F', '0', '0'},{'G', 'H', 'I', '0', '0'}, {'J', 'K', 'L', '0', '0'}, {'M', 'N', 'O', '0', '0'}, {'P', 'Q', 'R', 'S', '0' },{'T', 'U', 'V', '0', '0' }, {'W', 'X', 'Y', 'Z', '0'}};
int main(){string str;getline(cin, str);int num = 0;for(int i = 0; i < str.length(); i++){if(str[i] == '-') continue;if(str[i + 1] != str[i]){printf("%c", numtochar[str[i] - '0'][num]);num = 0;}else{num++;}}return 0;
}