Day1考试总结及学习笔记

考试心路历程

预计得分：$0 + 40 + 30$

实际得分：$0 + 40 + 30$

排名：$30$

看到T1，想了半个小时发现一点都不会做。看了下T2发现有20分暴力，稍微改一下就有40分了。T3裸的暴力有10分，拆点之后能得到30分。写完这些就差不多过去两个小时了，然后后面就再也没有输出了qwq。。回头看T1,想了两个半小时想出了一个和正解相似度$80\%$的做法，写了一会儿发现根本不可写，这时候也差不多快到时间了，就检查了一下离场了。

出了考场和mjt交流了一下发现自己忽略了T1一个非常重要的性质：所有的斜率全都是整数。好像全场的AC代码都是基于这个做的(除了我和std)

下午讲课的时候发现我误以为T1得到的是二维矩形，然而实际上是半平面。不过还好影响不大，毕竟想到了也写不出来。。。

考试题解

T1

mjt的做法：首先枚举斜率，斜率为$0$的时候显然是上端点的$min$ - 下端点的$max$，斜率为其他值的时候可以考虑把斜率转化为$0$，同时更改其他点的长度。

每个点的长度变化显然是一次函数，那么分别维护上下凸壳就好

最后算答案的时候可以把每段分开算

T2

不懂。。大概思路是考虑递推式的循环节然后用数据结构维护一下

T3

$k$很小，考虑$2^k$的算法。可以考虑对每个集合分别计算，再对不同集合内的点分别统计答案

自己在代码里面写了一点注释，统计答案那部分还没看懂。。

https://paste.ubuntu.com/p/XZBYjQVy9K/

题目

gym 100962 D

PA2009

白羽的Paper屋

ukkknin algorithm

《后缀树区间节点》陈江伦2018集训队论文