在南大转专业到计算机科学与技术系

前言

本文为记录在南京大学转专业到计算机科学与技术系的历程,以及给在南大同样想转专业到计算机科学与技术专业的学弟学妹们分享经验。

本人由于提前批的原因,只能在大二转专业,但转专业考核都是和大一一起的,没什么区别。

前期准备

计算机科学与技术系可谓十分热门,每年基本都是爆满状态,即使报名人数少于分配名额,也会秉持“宁缺毋滥”的原则进行淘汰。并且,转专业考试的难度可以用困难来形容。

因此,如果想要转专业到计算机科学与技术系,要做好充足的前期准备,才能考好这场转专业考试。

首先,是自身的前提条件。如果是零基础的话,我不建议转专业,计科的课程的难度比较大,零基础学习[……]

继续阅读

Flappy Paimon

初学一周不到的Unity处女作。

暑假想着学者做点游戏吧!于是开始了Unity的学习。

Unity还挺好用的,有一堆轮子,可惜国内网上的资源太少了,真要搜还得Google一下。

灵感来源于原神拜年纪的开场动画,就把它复刻了下来。

素材来源:

https://www.bilibili.com/video/BV15v411e7ne

https://www.bilibili.com/video/BV1F54y1n7KR

下载地址:

https://github.com/BakaSea/FlappyPaimon/releases/tag/0.1[……]

继续阅读

2020牛客多校第二场H-Happy Triangle

\(对查询的边x,分为两种情况 \)

\(第一种,x为最大边,只需要找离x最近且比x小的两条边判断a+b>x就够了,此处可用multiset \)

\(第二种,x不是最大边,那么需要找到一个b,使得b \geq x,b-a<x \)

\(可用平衡树或线段树进行维护,此处用动态开点线段树来解决 \)

\(区间[l, r]权值为min_{x_i \in [l, r]}\{x_i-x_{i-1}\} \)

 

2020牛客多校第二场C-Cover the Tree

\(很明显,记叶子节点数为s,则k=\left \lceil \frac{s}{2} \right \rceil \)

\(那么如何匹配呢?首先要选取一个非叶子节点作为根,然后对其进行dfs得到dfs序\)

\(按照dfs序大小排序得到叶子节点u_1, u_2, …, u_s \)

\(于是u_i跟u_{i+\frac{s}{2}}进行匹配,若s为奇数,则最后一个点跟根节点进行匹配 \)

 

2020牛客多校第二场A-All with Pairs

\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较,相同的次数记为res_{i,j},此处可以用哈希进行比较 \)

\(因为要取最大前缀,所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j},注意一下下标的偏移 \)

\(答案就是\Sigma_{i=1}^n\Sigma_{j=1}^{len_i}j^2res_{i,j} \)

 

2020牛客多校第一场A-B-Suffix Array

\(令c_i=min_{1\leq i < j, t_j=t_i}\{j-i\} \)

\(B数组其实就是c_1 c_2 c_3 … c_n的后缀数组 \)

\(要注意若没有t_j=t_i,则c_i = n,同时c_{n+1} = n+1 \)

\(答案就是后缀数组的逆序 \)

 

计算电压[洛谷P2011]

题目背景

相信不少人轻松灭掉 1,2 两题(蒟蒻无视此句) ,我相信,大家对物理也是很有兴趣的(众人:我们对揍人也是很有兴趣的) ,那么,再奉上 100 分给Physicaler 们。

题目描述

现给定一个电阻网络,已知其中每条边上的电阻,和若干个点和负极之间的电压(电源电压不变) ,现在求任意两点之间的电压。

输入格式

第一行三个数n,m,k,q,表示n个节点(可能是几个点用导线相连接,与一个点等价,编号为1-n,0号节点为电源负极),m个定值电阻,每个定值电阻连接两个点,k表示电源正极有k个接口,有q个询问。

以下k行,每行两整数,表[……]

继续阅读

[LOJ10013]曲线

三分法适合求解凸性函数的极值问题

\(设当前求解的区间为[l, r],令lmid = l+\frac{r-l}{3},rmid = r-\frac{r-l}{3},计算f(lmid), f(rmid)\)

将其中函数值更优的点叫做好点,函数值较差的点叫做坏点

最优点与好点会与坏点同侧,据此缩小区间

\(因为a≥0,所以S是开口向上的二次函数,F(x)=\max \{S_{i}(x)\} 也满足单调性,可用三分法求其区间最小值\)

 

[LOJ10012]Best Cow Fences

\(二分答案,判断是否存在长度不小于L的字段,平均数不小于二分的值\)

\(如果把数列中每个数都减去二分的值,就转化为判定是否存在一个长度不小于L的子段,子序列和非负\)

\(用前缀和维护数列,就可用O(1)的时间查询平均数\)

\(这题由于精度问题,需要先将读入的数乘上1000再整数二分……乘完之后还要开long long\)

 

[LOJ10011]愤怒的牛

求最小距离尽可能大,采用二分答案的方法

\(对二分的最小距离d进行校对,若不满足条件则减小,满足条件则增大\)