复旦大学研究生机试(2019)

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/50119.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【保研夏令营经验贴】2021复旦大学计算机科学技术学院

本人基本情况如下 学校&#xff1a;211 专业&#xff1a;计算机科学与技术 成绩排名&#xff1a;3/137 英语水平&#xff1a;四六级飘过 在校期间参加过一项省级创新创业项目&#xff0c;和区块链有关&#xff0c;同时也参加过数学竞赛、英语竞赛、数学建模&#xff0c;在…

复旦大学2021年计算机学院机试题解

写在前面&#xff1a;本文所收录真题解答都是本人自己所写&#xff0c;由于本人水平所限&#xff0c;部分题解可能存在错误&#xff0c;如存在错误&#xff0c;望各位指出。 更新&#xff1a;CSDN不会再更新&#xff0c;移步Pykt的博客 2021年真题 第一题 题目描述&#xff…

复旦大学2021机试

2021年真题 第一题 题目描述&#xff1a;给定一颗二叉树&#xff0c;树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点&#xff0c;那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序&#xff0c;并解释解…

复旦大学,计算机考研情况

复旦大学是位于上海的一所985大学&#xff0c;计算机学科评估B&#xff0c;软件工程学科评估B&#xff0c;在985大学中处于中游水平。但由于学校整体实力很强&#xff0c;名气也大&#xff0c;因此深受考生的欢迎。 复旦大学2021考研招生目录 计算机科学技术学院 081201&#x…

新版悬赏猫任务平台系统源码+已经去授权

正文: 完整标题: 悬赏猫任务平台去授权版&#xff0c;用户自主发布任务接免签支付&#xff0c;信用分评分机制网站源码可打包app 这个是带有用户发布任务功能的&#xff0c;还有信用分评分什么的&#xff0c;挺全面&#xff0c;具体的大家搭建出来看一下就知道。 程序: ww…

最新交易猫 闲鱼源码 带后台管理+个人码收款

带一款非常简洁好看的后台。 搭建教程&#xff1a;修改数据库账号密码直接使用。 源码码下载&#xff1a; 网盘下载地址&#xff1a;https://pan.baidu.com/s/19iOsoyK-J-Rhi2dZYqzMMg?pwdiumr 提取码:iumr

10款自媒体人必备的免费工具,快速高效运营

1、GIISO写作机器人 此款工具的slogan就是&#xff1a;AI校对&#xff0c;比人更会! 这款工具包含&#xff1a;文章校对、提纲写作、营销写作、汽车写作等功能! 比较受欢迎的是它的营销写作功能和提纲写作功能&#xff0c;营销写作功能可以一键生成营销软文。 而提纲写作功能…

这四款软件有多好用你不会还不知道吧

第一款&#xff1a;秘塔写作猫 秘塔写作猫是一款非常不错的写作软件。基于人工智能&#xff0c;可智能识别错别字、语义、标点符号、词序和语法问题。对于效率君来说&#xff0c;长期写作可以用它来检查&#xff0c;节省大量检查时间。它不仅可以改写&#xff0c;还可以翻译内…

交易猫源码完整搭建教程

源码仅供学习参考。 教程&#xff1a;修改数据库账号密码 源码下载&#xff1a;https://pan.baidu.com/s/16lN3gvRIZm7pqhvVMYYecQ?pwd6zw3

【018】秘塔写作喵-中英文文章自动审阅纠错

10月19日发布的每日网站指南007“微软Aim Writing-智能英文写作平台”&#xff0c;有读者反馈只能针对英文进行审阅&#xff0c;那今天ONETer就为大家介绍一个可以中英文文章自动审阅纠错的网站&#xff1a;秘塔写作喵 地址&#xff1a;参见文末图 写作喵网站需要注册后使用&a…

编程猫创作工具:新版Kitten新体验

在少儿编程图形化工具方面&#xff0c;Scratch是老牌的创作工具&#xff0c;最为流行&#xff0c;用的人也最多。但是Scratch界面不友好、本地化功能欠缺、网络访问慢等问题也日渐显著。编程猫自主研发的图形化编程创作工具&#xff1a;源码编辑器应运而生。Kitten以更丰富的素…

【编程题】【Scratch三级】2019.06 猫咪抓老鼠游戏

猫咪抓老鼠游戏 1. 准备工作 &#xff08;1&#xff09;保留小猫角色&#xff0c;添加“Mouse1”&#xff1b; &#xff08;2&#xff09;默认白色背景。 2. 功能实现 &#xff08;1&#xff09;键盘上下左右键控制小猫上下左右移动&#xff1b; &#xff08;2&#xff09…

AI智能润色改写,伪原创写作工具,毕业论文必备工具

小伙伴们注意&#xff1a;公众号的推送机制不再按照时间前后推送了&#xff0c;微信公众号信息流乱序。君哥建议大家把科技毒瘤君公众号置顶&#xff08;设为星标⭐&#xff09;&#xff0c;以便第一时间看到推送&#xff0c;非常感谢~&#xff0c;方法如下图&#xff1a; 推荐…

你不能错过的文章撰写软件

关注“心仪脑”查看更多脑科学知识的分享。 关键词&#xff1a;资源推荐、写文软件 抛开我们常用的WPS和OFFICE不说&#xff0c;现在的写作工具是越来越人性化了&#xff0c;就差实现人工智能。当我们辛辛苦苦做完实验&#xff0c;终于轮到我们报告的时候&#xff0c;却发现我…

怎么用秘塔写作猫写小红书种草文案?

在一些自媒体平台发布一些产品时&#xff0c;为吸引更多人的眼球&#xff0c;很多自媒体发声者会费尽心思写一些种草文案&#xff0c;但是自己绞尽脑汁写的种草文案&#xff0c;却没有取得较好的效果&#xff0c;反而借助一些AI工具帮助大家写的种草文案&#xff0c;更广泛地被…

怎么用秘塔写作猫写短视频文案?

短视频文案通常需要在短短的几秒钟传递一些比较重要的信息和情感&#xff0c;让关注更好的了解视频的主题和内容&#xff0c;写一份好的短视频文案可以吸引较多观众的注意力&#xff0c;能够让他们更好的理解视频内容&#xff0c;同时在观看视频时还可以给大家留下比较深刻的印…

「转」好用的写作辅助工具 - 秘塔写作猫

关注我很久的读者&#xff0c;应该都知道&#xff0c;我特别喜欢写作&#xff0c;每天不写点东西心里总是痒痒的。而且我写公众号文章有时候经常会有错别字&#xff0c;细心的读者能够帮我指正&#xff0c;其实挺感谢大家的指正的。 不知道大家发现了没有&#xff0c;我最近写…

秘塔写作猫(网页端)

首先&#xff0c;秘塔写作猫是利用智能AI写作功能帮大家完成各种写作&#xff0c;集AI写作&#xff0c;多人协作&#xff0c;文本校对&#xff0c;改写润色&#xff0c;自动配图等功能为一体AI Native的内容创作平台&#xff0c;这绝对是一个写作神器。 最开始不会使用的小伙伴…

秘塔写作猫

秘塔写作猫是集AI智能写作、多人协作、改写润色、文本校对等功能为一体的AI原生创作平台&#xff0c;可以帮助不同群体大幅提升写作效率和生产力。 接下来小编就带大家了解一下该软件具体的一些功能&#xff0c;不论你是学生、上班族还是自媒体从业者等&#xff0c;该工具绝对可…

python几行代码实现微信自动发消息

直接上代码 from wxauto import WeChat# 获取当前微信客户端 wx WeChat()# 获取会话列表 wx.GetSessionList()with open("C:\\Users\\mmm\\Desktop\\test.txt","r",encoding"gbk")as f: #这个.txt里写要发送的文字for line in f.readlines():…