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个结点,接下来的两行,表示该树节点之间的相连情况。