First Contact
题意
给定一个图,图中的点只有男的点或者女的点。给定两个不同的点AB,问他们第一个点通过两个不同的点找到第二个点,并且A找到的点和A同性,B连接的点跟B同性,这样的点对有多少对。
题解
暴力枚举即可,找到所有相邻的同性点,之后同性点之间有连接就是一对点对。
- wa点 前导零输出,-0000输入
- 中间的点不能是两边的点,必须是不同的四个点
ac代码
1 |
|
给定一个图,图中的点只有男的点或者女的点。给定两个不同的点AB,问他们第一个点通过两个不同的点找到第二个点,并且A找到的点和A同性,B连接的点跟B同性,这样的点对有多少对。
暴力枚举即可,找到所有相邻的同性点,之后同性点之间有连接就是一对点对。
1 |
|
以此记录我人生中的第一次面试
因为在报名夏令营的时候,一个公众号将上海科技大学加入列表中,我才知道有上海科技大学这所大学。之后查了以后发现上科大是一所2013年建成的精致的大学。查了以后发现上科大的师资力量和学校经济实力十分得强大,所以就报名了上科大的信息学院夏令营并通过了初审。
我选择的是第一批次,之后在生产实习的时候请假来到上海,来到上科大的第一感觉就是这个学校很精致,很有设计感。里面的每一栋建筑明显都是有设计过的痕迹,并且没有一座建筑是长得一样的!
之后入住了上科大的研究生宿舍,2人一间,宿舍是酒店标间的设计。
上一届上科大夏令营是3个老师来面试每一个人。这一届上科大选择了老师同学双向选择面试,你可以面试很多老师,只要你去找这个老师即可。我一开始的目标老师是tkw老师,但是这位老师一直没有回我邮件。所以我就去给hxm老师和yjy老师发了邮件。之后他们都有回复。第一天上午是参观学校并介绍学校的毕业生去向。下午自由活动,由于给hxm老师发邮件的人实在是太多,所以老师选择先让我们笔试。笔试的内容大概就是计算机专业课+机器学习中的线性代数和概率论+程序设计算法思维题。我由于计算机网络还没有复习完,并且专业课的内容学得也没有那么扎实,所以第二天没有能够和hxm老师面试,惨遭淘汰。之后第二天上午,我去了yjy老师,yjy老师有两次面试,一次是让他的博士生来面试,主要的内容就是简历中他们感兴趣的内容,之后我程序竞赛还算是比较认真的。通过了一面,来到了二面,二面中,老师会先让你自我介绍,之后会让你提一些你感兴趣的问题。但是作为一个死读书的,我哪里来那么多问题。如果在给我一次机会的话,我会问:博士毕业后创业,我看先前有学姐介绍有一个人就是通过他自己研究生的课题发展成为一家公司,并且我在乔布斯访谈中也了解到,乔布斯当时在车库中创业是因为他们组装的电脑收到了很大的欢迎,那么老师,如果您推荐创业,您的课题中有哪一些课题是比较适合落地并且创业的呢?二面我感觉蛮糟糕的。之后我去了zr老师的面试,老师是比较偏硬件的,但是人面试的时候十分好,hin温柔。之后老师问我有没有问题,我当时有点紧张,所以就没有问老师。。如果再给我一个机会的话,我会问:老师由于我大一到现在基本上都在程序设计竞赛,没有完整地参加过一次科研活动,我就想问一下您,您觉得一次科研的过程大概是怎样的。之后科研在现在到底是会对这个社会产生怎样的影响。因为我看现在的公司工业界感觉创造的成就比学术界更加强力并且落地的程度更加完善。您觉得工业界和学术界各有什么优劣势吗?
食堂不咋地,但是住宿很舒服,环境很好,并且听说研究生的补助很高,大概每个人2000+每个月是肯定的。觉得有点遗憾的就是,没有面试足够多的老师,本来我就是来积累面试经验的,结果就面试了两个老师,有点亏。。
自我介绍,还是需要整理一下的,必须要让老师有亮眼的地方!
语言:js+html
框架:echarts+impress
一开始我就在寻找有什么能够跟ppt一样,展示出我们的数据分析图表的框架,之后我就搜索到了impress.js这个框架。他的效果很酷炫,非常适合拿来展示自己的作品甚至代替ppt来使用。
官方demo:https://impress.js.org/#/bored
半小时因为impress.js的版本不对,搞了半天。应该直接去github下载就行了。
之后遇到了一个坑点,jsp嵌入html5的时候,载入js脚本的时候,必须声明是javascript,否则可能会出错。
并且jsp声明html5的格式为
1 | <!DOCTYPE HTML> |
百度出品的良心可视化数据js库。
1 | <%-- |
为了拿PAT的50元代金券,刷一刷牛客网上的PAT真题。
求一百个分数的和。
大整数秒了。
其实我想用python,现在acm区域赛都让用python了
给定一个数字,用中文拼音输出他。
模拟。
1 |
|
给定最多100个人,给他们排序,输出指定成绩区间内的人名和ID。
模拟,sort
1 |
|
用栈表示一个树的先根遍历,求这颗二叉树的后跟遍历。
dfs模拟一下即可。
1 |
|
给定$m$个指定串,寻找长度为$n$的不含指定串的字符串。
AC自动机+dp+矩阵快速幂。
如果要不含病毒串,那么我们相当于在每个状态中不能指向那个病毒终点串。对于每个状态来说,可以选择的就是4个字母去掉下一个状态是病毒的字母。
$dp[i] += dp[j] (j是非病毒终点)$
初始化$dp[i]$为可以选择的字母。相当于$i$状态加上状态$j$乘上字母数。可以构造一个矩阵mx。$mx[i][j]$表示$i$到$j$的字母数,矩阵的$n$次方之后就是经过$n$个状态转化后的值。
举个例子,比如我们是AC,AT,AG,AA这四个病毒串,那么root = 0,A是1,C=2,T=3,A=4。有五个状态。
当我们状态为0的时候,有两种选择。我们到状态0的选择字母可以选3个’C’’T’’G’。到状态1可以选1个’A’。之后到状态1没有选择了,因为全是病毒串。所以我们的矩阵是
3 1
0 0
之后矩阵乘就完事了。
我感觉讲得有点不清楚。。。
+2 TLE因为矩阵的大小是有build的trie树决定的,所以越小越好用ac.tot来表示矩阵的大小,也就是状态的大小。
+10 矩阵的大小其实是状态的大小,状态的大小是 输入的病毒串长度*病毒串的次数。最大tot为这么大。
+1 因为转移的状态只有四种,所以maxson为4就好了,大了的话创造矩阵的时候会出现问题。
###ac代码
1 |
|
给定一个有向无环图DAG,之后问从点$1$走到点$n$中,在一定的费用要求下,最多能经过多少个点。并给出经过的点。
$n \leq 5000$
我们可以考虑一下二维dp,定义一个dp数组
之后利用dfs进行更新。因为是深度优先,所以经过的点不用在遍历一遍。
对于记录经过的点,可以用一个二维数组代表,第$j$个点的时候下一个点是什么。
定义两个数组,一个记录已知这个点到达$n$最少耗-费的时间,一个记录已知这个点到达$n$最多的点数。之后利用这两个数组进行剪枝,但是已知wa14的点,我也不知道为什么。可能是dfs的顺序有关。
1 |
|