Day3考试总结及学习笔记

考试心路历程

预计得分：$15 + 10 + 10$

实际得分：$15 + 10 + 10$

排名：$14-25$(都是$35$分)

考试的前一天晚上得知今天的出题人是lca，那么就差不多明确方向了：认真打暴力！。果然今天的题目非常难，甚至连暴力都非常难写。三道题的暴力打完差不多已经过去了三个半小时。。剩下的时间稍微思考了一下T2T3，感觉T3可以用玄学做法得高分于是就写了写(然而并没有什么卵用。。)

考试结束后和他们交流了一下，发现题目果然都不可做，我们学校的很多人甚至连暴力都不会打。。全场最高分只有$160$，从$14$名开始就全都是暴力分了。

考试题解

一道题都没听懂，题解也没发，只能记一下大体思路了。。。。

T1

考虑把问题转化一下，对于每个$V$，我们算出前缀和，那么如果到达每"对"$V$时都满足条件，那么方案就是合法的

由于前缀和的最大值只有$N$，考虑直接$dp$，设$f[i][j]$表示前$i$个位置，前缀和最小值为$j$的方案数

然而没搞懂怎么转移qwq。。。。

T2

生成函数神仙题，略过。。。

思路大概是要先证几个引理：首先要构造本原连续段，然后证明本原连续段会构成一棵树

然后就不会了。。。。

T3

并查集神仙题。。。略过

题目知识点

讲了怎么构造dft，我基本全程都在听，但是好像一点都不懂。。

讲到最后lca来了一句：今天下午我们讲的知识点目前还没有什么应用，我只见过一道题，清华集训Day2T3。。

我：。。。。。。。。。。。。。。。。。。。。。。。。