嗯多谢某神牛提供的不知道是哪一年的各地的NOIP模拟赛（质量挺不错的

给我们这个偏远小渔村提供了宝贵的模拟赛资料

怎么我也高二了QAQ

NOIP玩挂就真的退役了（悲伤

[9.14] #15

被腾爷和CZL实力踩脸

B

题意：给K维空间的几个点，求最远点对（距离为曼哈顿距离）

正解：枚举正负然后算（曼哈顿距离的性质）

C

DP，我发现能单调队列，但是写了个堆多了个log，事实上不需要堆。。。

【Think】

以后DP能利用其单调性就利用，为啥每次都要写个堆QAQ

曼哈顿距离的性质还真的是好玩啊

|x1-x2|+|y1-y2|=max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|)，扩展到K维就各个维正负号都取一遍

[9.16] #16

A

正解是直接判断能否用一个石子救能隔断（答案不超过2）

我是S固定然后T每个水的点都跑一遍网络流

B

每个点求最短路网然后求割点

【Think】

重置网络流可以连S-T的边，就不用全部重建了

求割点的姿势（自己理解）就是dfs的时候返回dfs一遍，然后看哪些点没被反向dfs到

[9.18] #17

被标程踩脸。。。

A

其实可以贪心放。。。

B

求出MST后就转化成求树上路径最长边

没想到居然可以\(O(n^2-1)\)。。。

C

考场写了个搜索+map排重剪枝过了40%

后来发现题解写了个DP，然后阐述了一下DP的正确性，瞬间整个人就poi了

【Think】

有时候敲倍增比敲链剖划得来

[9.21] #18

C

有N个矩形，问他们能构成的最大矩形的大小。（其实这道是模版题。。。

\(O(n^2)\)枚举左上角和右下角，\(O(n^2)\)预处理每个点沿边界线能到达的最远处。

【Think】

自己测试的时候可以跑一些能手算的大数据

[9.23] #20

B

高斯消元简直。。。这么基础的算法都不会敲了QAQ

C

把有可能相交的边看成点，然后染色

【Think】

有两个互质数a和b，则最大无法表示成ax+by的数是ab-a-b

高斯消元需要注意无解和自由基的情况

[10.16] #25

【Think】

B题SXBK卡精度，能少用double就用double

常数优化：减少%运算次数