【口胡】简谈福建省夏令营

Day1

t1：线段树区间修改

upd：更简洁的做法

离散化每个建筑的左右边界，可以用pq来查询右边界未被删除的建筑物的最值

t2：字符串哈希+尺取

t3：dp

upd:看错题目了，先奇怪的二分一下最大正方形大小，然后枚举左上角计算

Day2

t1：乱搞

t2：贪心

t3：八数码。各种搜索+剪枝

Day3

三题搜索

Day4

t1 t3普及组

t2：设状态f[i][j][k]，前i行，j列一个，k列二个，每行每列最多两个炮。然后dp

Day5

t1：正反计算一次最大子段和O(n) 枚举分界点

t2：用f(i,x,y,a,b)表示从1,1到x,y，从N,N到a,b，路径上相同的方案数，压掉y,b两维

t3：考虑次方的和可以这样计算

$1+k+k^2+...k^n=((1+k)*k+1)*k....$

用 $f_i$ 表示后i个能获得的最大价值，那么 $f_i=max_{1<=j<i,|j-i|<=M}f_j*k+a[...]$ 线段树单调队列维护最小值

如果用pq或者线段树会多一个log

Day6

t1：求凸包裸题

t2：强行分块考虑暴力算法的优化，即当前一维坐标差> $frac{c}{2}$ 时退出

那么我们可以用 $nlog_2^2n$ 的最近点对来求值

t3:首先考虑 $n^3$ 的做法，枚举两个顶点，判断是不是和所有对角线相交

然后优化，枚举一个顶点，求出这个顶点与每个矩形的对应对角线交所在区间，判断区间交集是否非空

像我这样的傻叉为什么会去写半平面交

半平面交的做法：一条直线 $ax+by$ 交矩形的条件是： $c_1$leq$ax+by$leq$c_2$ 。把这个不等式变成两个半平面，原问题就变成了查询半平面交是否为空的模板题目了

Day7

t1： $m-gcd(n,m)$

t2：对于每个点二分他到素数的最近操作次数，枚举行列统计最优解

t3：分类讨论。。具体不细述

Day8

t1：给定大小关系求合法性，拓扑排序

t2：2^联通分量个数-1

t3：题面这么长，出题人强行提高难度的最短路裸题

Day9

t1：二分图完备匹配是否存在

t2：二分图最大匹配

t3：把每个人拆成三个点：人、小时、日期，建图挺简单的吧，判断是否满流（？）

终测

t1：普及组题

t2：暴力统计啊

t3：脑洞（？）题好像也不算，你要看出，翻折顺序不重要，然后就是大暴力了

t4：并查集+暴力枚举，应该能过

总结：

夏令营面向群体：新高一 —>新初二初三

最终测试难度：提高+ –> 普及组？？？？？？？