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

前言

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

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

前期准备

计算机科学与技术系可谓十分热门，每年基本都是爆满状态[……]

Flappy Paimon

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

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

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

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

素材来源：

https://ww[……]

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

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

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

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

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

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

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

$latex 按照dfs序大小排序得到叶子节点u[……]

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

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

$latex 因为要取最大前缀，所以要用kmp求出next数组后res_{i,next[j]} -= res_{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的后缀数组 \)

$latex 要注意若没有t_j=t_i，则c_i = n，同时c_{n+1}[……]

计算电压[洛谷P2011]

题目背景

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

题目描述

现给定一个电阻网络，已知其中每条边上的电阻，和若干个点和负极之间的电压（电[……]

[LOJ10013]曲线

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

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

将其中函数值更优的点叫做好点，函数值较差的点叫做坏点[……]

[LOJ10012]Best Cow Fences

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

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

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

$latex[……]

[LOJ10011]愤怒的牛

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

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

#include<stdio.h>
#include<algorithm>
#include<string>
#define MAXN 100010
using namespace std;

inline int read() {
	int x = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 3)+(x << 1)+c-48, c = getchar();
	return x;
}

int n, m, x[MAXN];

int check(int d) {
	int k = 1, p = x[1]+d;
	for (int i = 2; i <= n; ++i) {
		if (x[i] < p) continue;
		k++;
		p = x[i]+d;
	}
	return k >= m;
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) x[i] = read();
	sort(x+1, x+n+1);
	int l = 0, r = x[n]-x[1];
	while (l <= r) {
		int mid = (l+r) >> 1;
		if (check(mid)) l = mid+1;
		else r = mid-1;
	}
	printf("%d", r);
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

#include<stdio.h>

#include<algorithm>

#include<string>

#define MAXN 100010

using namespace std;

inline int read() {

int x = 0; char c = getchar();

while (!isdigit(c)) c = getchar();

while (isdigit(c)) x = (x << 3)+(x << 1)+c-48, c = getchar();

return x;

}

int n, m, x[MAXN];

int check(int d) {

int k = 1, p = x[1]+d;

for (int i = 2; i <= n; ++i) {

if (x[i] < p) continue;

k++;

p = x[i]+d;

}

return k >= m;

}

int main() {

n = read(), m = read();

for (int i = 1; i <= n; ++i) x[i] = read();

sort(x+1, x+n+1);

int l = 0, r = x[n]-x[1];

while (l <= r) {

int mid = (l+r) >> 1;

if (check(mid)) l = mid+1;

else r = mid-1;

}

printf("%d", r);

return 0;

}

1
2
3
…
20
»