DAY 1(10.2)

CASIO

做法

这题可能是这几天最水的一题，并且由于数据过水，直接O(nloglogn)也可以过。
就是通过线性筛法，但是对于大于P的质数就不再进行筛法了。

CAR

[原题链接]

做法

首先按坐标排序
首先考虑只存在98的油，预处理从i个98加油站开始加满到终点还需要多少98的油
然后考虑只存在95和98的油，同样预处理。
最后处理三种油皆存在的情况。
对于无解情况，判断此点使用三种油是否还需要油，若需要，则无解。
然后考虑需要多少95油，就是假设不存在98的时候这个加油站到终点还需要的油，这个我们也预处理出来了。
最后考虑需要的92油，答案是不存在95和98时此加油站到终点还需要的油数量减去需要的95的数量。

EXCELLENT

[原题链接]

做法

DP，区间DP，预处理。
但是使用此方法无法通过LUOGU数据，需要后缀数组SA进行优化。

ROBOT

[原题链接]

做法

拓扑排序，线段树优化建图。
先使用树链剖分(LCT)，将每一条链处理出来。
再用线段树优化建图，最后在新图上跑拓扑排序。

真是综合的一套题。

DAY2(10.3)

JUMP

做法

单调栈。

LCA

做法

若根节点固定，算LCA总和是简单的。
于是去做换根DP(根本就没见过)，属于树形DP的一种。

FLIP

%CQR

做法

CQR DALAO通过推规律直接过了。
至于我们这些对数感不强的人只能学习怎么推组合数。
将操作看成操作区间，会发现这些区间只能是包含/相离。
不考虑填数时，答案是(2k-1)!!(!!为双阶乘)
接下来还剩下(n-k)对01序列，任意插入2k+1段，答案是C(n+k,2k)
总的答案就是将其相乘

EXPLORER

[原题链接]
将圆三条弦的关系列出，然后通过容斥，算出不合法方案。
第一种是三条弦互相平行，这种答案非常好算。
剩下的不合法方案有共性：三条弦中有两条满足另外的两条弦一条与其相交，一条与其相离。
于是又将这个问题转换成了二维偏序。

原本还想今天可以把DAY3都写完的，结果现在已经DAY4的凌晨了。
那就DAY3-4一起吧。