呜呜。

校内模拟赛

A

sxyz 评测机卡 printf。

不过在自己电脑上测 printf 也确实略慢，所以 $10^6$ 以上输出量就上快写吧。

B

不开 long long 见祖宗。

C

【模板】单调栈

D

不交叉地将凸 $n$ 边形切成 $k$ 份的方案数。

显然，这有重叠子问题，可以用 dp 来做。

直接做就是 $f_{i, j}$ 表示 $i$ 边形分成 $j$ 份，然后枚举加上去的一条边，$f_{i, j} = \sum f_{i-k, j-1}$, 但是这样子做显然会有重复，手模拟一下就会发现重复。

那么怎么处理呢，我就开始走歪路了。想着最外面的切割的个数就是一个方案会被重复计算的个数，而一个最外面的切割和新的拼起来有两种情况不会改变最外面的切割数，其它情况会使切割数小 $1$, 所以加一维……

这样子做非常的复杂，而且很多细节难以确定，所以来看正解的做法。

正解先钦定了一个点，将没有经过其的计算出来，显然是 $f_{i-1, j-1} + f _{i-1, j}$ ，就是把这个点划出去或者不划出去。

这样子计算出来的方案肯定不会有重复，因为它没有转，下一层转是不会导致重复的，同时，这样子分割也可以确保在本层中和不会和经过该点的重复。

那么如何计算经过该点的呢？

其实非常简单，只需要枚举两个连接的点然后将左右分开来就可以了。没想到吧，处理旋转重复的最好方式就是不要旋转，因为左右计算的方案数里都包括了所有的方案，必然也就包括了旋转过去的，同时，这一条先的确定还能保证两边不重不漏。

挺妙。

ARC

A

定义 twt 距离为 $\max \{|x_1-x_2|, |y_1-y_2|\}$， 输入 $n$ 个点，求 twt 距离第二大的。

肯定是最左边两个，最右边两个，最上面两个，最下面两个组合而成的，所以把这几个拉出来然后暴力跑一遍就可以了。

B

老板 twt 有 $2n$ 条狗，要去守门，twt-tec 有 $n$ 道门。狗有三种颜色，每道门两只狗守，若颜色相同则不用花钱买饭喂狗，但是颜色不同就要花费 $|a_i-a_j|$, 求 twt-tec 的最小花费。

把三种颜色分开做，若三种颜色都有偶数个那么答案就是 $0$ 了，否则一定是两个奇数个一个偶数个。

然后两种情况，一种是两个奇数组里面选出最接近的两个，另一种是偶数组中选出和两个奇数组中最接近的两个。

第一种很好写，第二种困扰了我很久，万一它们最接近的是同一个怎么办？最后找不出反例赌了一把直接不管这种情况居然过了。

其实确实不用管这样的情况，因为如果两个最接近的是同一个，那么这两个的差的绝对值肯定比再去找另外一个和这中间一个作差加上去要更优。

所以 遇到问题一定要证实问题存在。

最后

掉分。