Day1
t1:线段树区间修改
upd:更简洁的做法
离散化每个建筑的左右边界,可以用pq来查询右边界未被删除的建筑物的最值
t2:字符串哈希+尺取
t3:
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:考虑次方的和可以这样计算
用表示后i个能获得的最大价值,那么 线段树单调队列维护最小值
如果用pq或者线段树会多一个log
Day6
t1:求凸包裸题
t2:强行分块 考虑暴力算法的优化,即当前一维坐标差>时退出
那么我们可以用的最近点对来求值
t3:首先考虑的做法,枚举两个顶点,判断是不是和所有对角线相交
然后优化,枚举一个顶点,求出这个顶点与每个矩形的对应对角线交所在区间,判断区间交集是否非空
像我这样的傻叉为什么会去写半平面交
半平面交的做法:一条直线交矩形的条件是:。把这个不等式变成两个半平面,原问题就变成了查询半平面交是否为空的
Day7
t1:
t2:对于每个点二分他到素数的最近操作次数,枚举行列统计最优解
t3:分类讨论。。具体不细述
Day8
t1:给定大小关系求合法性,拓扑排序
t2:2^联通分量个数-1
t3:题面这么长,出题人强行提高难度的最短路裸题
Day9
t1:二分图完备匹配是否存在
t2:二分图最大匹配
t3:把每个人拆成三个点:人、小时、日期,建图挺简单的吧,判断是否满流(?)
终测
t1:普及组题
t2:暴力统计啊
t3:脑洞(?)题 好像也不算 ,你要看出,翻折顺序不重要,然后就是大暴力了
t4: 并查集+暴力枚举,应该能过
总结:
夏令营面向群体:新高一 —>新初二初三
最终测试难度:提高+ –> 普及组???????