2020 EC-Final总结

由于教练临时起意，我们队意料之外地获得了EC的参赛资格。
第一次（也可能是最后一次）参加线下赛，总算是弥补了一直以来没机会外出打比赛的遗憾。

4.16

中午搭乘东航的飞机抵达西安。飞机上的伙食还挺不错。下飞机后头稍微有点晕，不过到室外后好了些。感觉西安白天比上海要热。
随后我们搭乘中巴车到达南山苑宾馆。宾馆紧挨着西工大，因此非常方便。住下之后教练请我们吃了一顿大盘鸡。菜很丰盛，分量也很充足。
饭后绕学校逛了一圈。由于是夜晚，许多风景、建筑看得不是很清楚，但总体感觉西工大的校园环境还挺不错（只是地理位置偏了些。要是能通地铁就好了）。整齐有序的建筑、钢筋水泥交错的施工地，处处体现着工业界的严谨与秩序。

4.17

上午去体育馆领了背包和衣服（以及企业的一堆***），合了张影，然后不想听企业讲座就回宾馆了（后来听说华为那可以白嫖鼠标就去蹭了一下）。中午吃完饭回去休息了一会，去打热身赛。
热身赛是3道题。第1题签到记不清了，第2题是要打个Stirling数的表（队友居然不会），然后推个式子就出来了。第3题树形dp只想到 $O(n^3)$ 的做法（其实可以证明复杂度是 $O(n^2)$ 的，但是没想到），在赛场上就没有去写。

后来测了一下环境。循环里套一个乘法能跑2e9，套一个取模能跑3e8，很快啊。

可惜电脑上没有VSCode。习惯用VSCode自动格式化的选手表示codeblocks很不方便。

最后排名是45（其实大部分队都过了2题，我们罚时比较靠前）。正式赛如果能有这个排名，我们也就知足了。

P.S. 我们对面是五点共圆，怕怕.jpg

4.18

早上吃完早饭就去了赛场。开场后，依然是和平时训练一样的看题顺序，只不过这次的赛程没有那么丝滑。。

当场过的题：

F:

fez过的签到

L:

给定一个数组$a$，要你构造一个数组$t$，使得 $\forall i(1\le i<n),a_i{t}_i{a}_{i+1}{t}_{i+1}$为平方数。同时使得${\prod }_{i=1}^n{t}_i$最小。（ $n\le 1e5,a_i\le 1e6$ ）

一开始以为是$t_i=\frac{\text{lcm}a}{a_i}$，交了一发WA了，发现有问题。

正解应该是将每个元素进行质因数分解，然后对于每个质因子，考虑所有$a_i{t}_i$，它的指数要么全是奇数，要么全是偶数。取代价较少的那个情况即可。

B:

一个 $n\times m$ 的矩形，每秒破掉一个格子，问每秒剩下的子矩形个数。

开始没啥思路，想到一个 $O(n^4)$ 的维护方法，就是每次统计破掉的格子在多少个完整的矩形内。后来发现 $O(n^4)$ 跑不满，写了一发，然后就卡过去了。

听说正解是离线做法，就是记录每个格子的消失时间，然后枚举上下边界，对每一列的最早破损时间构建Decartes树来统计每秒消失的矩形个数。

K:

txy过的德州扑克策略题

当场尝试搞，但没搞出来的题：

M:

$n\times m$的土地上有3个点，要分成3个连通块，使得3个点在不同块，且点 $i$ 分到的面积为 $S_i$。给出方案。（这里规定上下边界连通，左右边界连通）

想过让两个面积较小的人随意扩散，或是有规律地扩散，但总是避免不了一大堆特殊情况。最后受不了了。

D:

一个 $n$ 个点，$m$ 条边的无向图，每条边长度为1，且初始配速为1，甲从 $s1$ 到 $t1$， 乙从 $s2$ 到 $t2$。你有$k$次机会，每次可以把一条边的配速提升1，要使得甲和乙所花总时间最少。$n,m\le 5000$

一开始以为可以直接搞个类似贪心的什么东西，后来发现最优策略可能会因为 $k$ 的大小而发生变化。

后来想到枚举公共路径计算，但距离结束还有10min，来不及了。

A:

给定一个长度为 $n$ 的字符串，字符有62种，要统计其中ABCDCD（ABCD各不同）型子序列的个数。

首先想到一个 $O(62^{3}n)$ 的暴力：
考虑有限状态机的转移：

因此可以开5个dp数组暴力转移。

后来优化到 $O(62^{2}n)$：
首先改为记录允许D和A重复的情况：

再减去ABCACA型的个数：

结果还是TLE。
尝试改进状态设计，发现优化不下去了。

后来知道正解是双向维护的。先从右往左预处理出cdcd，然后枚举每个位置作为c，枚举d。前面的ab有多少种即可利用容斥原理求出。

C:

已知一个随机数生成程序，一个洗牌算法，给出洗好的牌，求随机数种子。

其实随机数生成程序就是一个线性变换，题目就是要求解一个线性方程组。可惜没反应过来。。。

G:

长5e5的数组，5e5组询问，每次询问一个区间有多少个子区间内元素种类数为奇数。

想了主席树、莫队，也想到记录每个元素所影响到的区间，但就是没想到扫描线。。。

J:

给定一个凸包，求所有半径为$r$且能覆盖整个凸包的圆的圆心组成的集合大小。

其实就是求 $n$ 个圆的交的面积。
尝试积分。
放弃orz
听说正解是魔改半平面交算法？告辞

总结

最后4题银尾收官，不算有太大遗憾吧，毕竟知道自己和金牌还有很大的实力差距。

两位大三的队友都要退役了，其他队的许多人貌似也要退役了。如今的我，不知不觉也已经到了大二下，大学剩下的时光也不多了。纵使还有许多遗憾没有弥补，也是时候选择告别了。
那就许愿下辈子进一次world final吧（逃