2021 NSFZ TCS 游记

Posted on Edited on

我只是去摸鱼的。

总的来说机试要比去年难的多，大概CSP2019Day1的难度。

事实上这篇游记的目的大概就是介绍流程。

放上去年yzh神仙的游记做个对比 orz

Day 0

放学前居然还考了场数学。学校估计是知道我们要考特长生就特意把题目放难了点。有那味了。考完发现最后一题出了点小毛病，但答案居然还是对的。只能希望明天的考试不要这样就行。

Day 1

上午8:55 到达nsfz。
事实上这是迟了点的，最好8:50到，我是最后一个到的。

但一到那就有神仙开始假我/fad

走之前突然听到楼上高一的学长xwy也在假我/fad

先去考的综合卷。9:30 考到 11:00。

今年是近几年来第一次放上物理题（但这道题只是套了一件物理的外套，实质上只是求个二次分式最值）。

大约9:55写完数学，物理先空着。然后大约10:15写完语文除了作文外的题目。

10:32写完英语（包括作文）。这次的作文，怎么也想不到居然是校内书上的作文 （初二的学弟们听好了，是九下要把机器人退货那一篇）

10:47写完语文作文。10:58写完最后一道物理数学题。

11:00收卷。折腾了15min才出考场。

去附近的KFC吃了个饭，背了会儿板子就回来了。（事实证明这还有点用）

在学生剧场等待，碰到的全是工程物理的。

工程物理的人数：软件工程的人数≈30:1

12:50出发，先去抽签。本来还以为是每个人的题目都不一样 /yun 但原来只是抽机位号 抽到的是01号 2333

试机的时候测了一下电脑，1s 1e8估计都有点危，慌

发题了。

T1：

有一张 n 点 m 边的无向图。有 q 组询问。每一组询问有4个参数 s,t,l,r 表示假如起点为 s，终点为t，不同的长度在[l,r] 范围内的路径条数是多少。$1\le n,q,\le 40, 1\le m \le 10^3,1 \le l,r\le 10^9$，保证$r-l \le 200$

T2：

有一棵树。每个节点上都有一个人。现在这些人要走到1号节点上，每次从儿子走到父亲用时1。所有人同时走，不能等待。

你可以使用k次技能，每次技能可以将一个节点上的人瞬移到它的父节点上，用时0。技能是瞬时的，没有后效性

给定这棵树和k，问你所有人都到达1号节点的最少时间是多少。

$1 \le k \le n \le 5\times10^5$

T3：

一张有向图，边权为1或2。问你从1号节点到n号节点的最短路。

$n \le 3\times10^5, m\le 5\times10^5$

口胡思路：

T1看来是个矩阵快速幂。（但问了一圈居然好像只有我写了矩阵快速幂/yiw）

T2是个O(n)的dp不多说，主要是要猜个结论。

T3有点迷。边权干嘛是1,2?写了个裸的dijkstra本地跑了1.1s。卡了会儿常跑了1.01s。有点慌，最后加了个快读就0.6s了。

upd:

T1估计是挂了40

忘了小粉兔的QQ名（慢即快）！！！！

不用对 l…r 都做矩阵快速幂

求出l 然后暴力跑到r就行了！！！

总分第一，还行