2022冬令营总结

冬令营的各式各样的总结

2022.1.18总结

T1：一道数学思维题，想了一个上午，发现$n$特别小，二分答案后寻找以各顶点为圆心，二分出来的答案为半径，交于多边形的边的扇形，讨论一下交点数，用相似求出交点坐标，用一些奇妙的算法（叉积或者暴力）求出面积判断交点是否在多边形以内，就可以了；考场上，有一种情况没讨论对，当交点数为0时应该把交点当成扇形与两边的交点

T2：不会

T3：$30'$暴力$BFS$,但是考试的时候没注意到它可以移到哪里，挂0，$60'$二维前缀和，二维差分，$100'$用二维字符串通配，$FFT$优化，但是我没学

T4：用前缀异或和来求解

2022.1.19总结

T1：一道记忆化搜索，两个$dfs$轮流跳，根据最优策略，状态压缩即可。考场时以为是求$D$的最大值，所以炸零了

T2：又是一道数学思维题，观察可以发现$n \le 10^4$，因此$n^2$的算法理论上也是能过的。对一个点，若它与其他点围成了一个凸包，那么一定有一条经过它的直线使得所有的点都在它的一侧。那么作每个点与$A$城的直线，暴力判断左右点数，（也可以排序后$n \log n$判断），找出最小值；还有要特判一下$x_i = x_A$的情况，因为此时$k$值为无穷大，于是乎我考场切掉了

T3：打的是暴力，但是有些地方挂掉了，于是又炸零了，题目看得还不够仔细，正解是二分图匹配，把剑与法术连一条小怪的边，跑一个$KM$算法或者转化成费用流模型做一遍网络流$Dinic$

T4：暴力$n^3 m^3$优化一下可以卡过去，正解是$n^2 m^2$的，设$f_{i,j,k}$ 表示当前在点$i$，$j$，模值为$k$，由此可以列出$dp$式

2022.1.20总结

T1：一道$dp$题，考场时以为复杂度太高，所以没怎么打。正解是设$f_i$，$g_i$表示以左边或者右边的点为结尾的最大值，可以列出一个状态转移方程，对边集进行排序，发现$n \le 10^4$，所以说$n^2 \log n$也是可以稍稍卡过去的

T2：又是一道网络流，$Dinic$学得不怎么样，以后还是得要过基础先

T3：线段树优化，暴力删点，用线段树维护区间最小最大值，单点修改，当然也可以用$set$来存储当前还剩余的点，以后读题要读详细点，居然漏看了一个关键性句子：

它将炸毁坐标在[Yi-Bi,Yi+Bi]范围中所有$D_k \le A_i$的尚未被炸毁的德军阵地。而同时对其他针对不造成任何影响。

所以以后要仔细读题，不要挂掉能拿分的题（永远都猜不到出题人的数据是有多么水）!

T4：没有考虑到几个矩形重叠在一起的情况（考虑了也不会做呵呵呵）

2022.1.21总结

$dp$专题了属于是……

T1：双向$BFS$，暴搜，再稍稍优化一下常数，赛时打的是单向$BFS$，所以$TLE$成了$50'$。$Upd$：空间开的也太小了，十分辛苦地把代码运行空间从$80000KB$压成$20000KB$，全场最·毒·瘤的题目

T2：二分，用$dp$来$check$，由题知，每一个塔只对一个区间产生贡献，且每一个塔的高度不同，于是可以按从高到低的顺序进行$dp$，这样子就没有了后效性。

T3：正解是一个区间$dp$，设$f_{i,j,0/1}$表示当前在$i$和$i+1$之间，上次的运算符出现在$j$和$j+1$之间，$0/1$表示当前选择$+$或者$\times$。由此可以列出$dp$式，但是也可以使用暴力$dfs$剪剪枝，不仅思路简单，码量小，而且空间小，还跑得飞快（$154ms$，$308KB$，$553bytes$）。考场的时候用了$BFS$，导致有一个问题，若选择添加符号，对答案产生$1$的贡献，否则没有贡献，这样就不保证队列中相连的一段产生贡献相同，还有若当前和与积之和超过了$T$，答案还是要保留，有可能后面$*$了一个$0$，刚好卡过去

T4：缩点，将一个环缩成一个点，再愉快地$dp$

2022.1.22总结

T1：通过循环节来寻找规律，显然$v_i \in [-m,m]$，因此循环节最长为$M$，那我们只需要考虑前$K+2M$个$v_i$就可以了，复杂度为$O(3000^2)$，跑得飞快$15ms$，话说我居然真的以为它给出来的$v_i$是随机数……

T2：双向$BFS$暴搜，优化常数，考场的时候队列开太大了，导致$MLE$成$90'$（主要是用了$map$不知道会消耗多少空间）。从起点和终点两点同时出发进行搜索。

T3：网络流，给矩阵进行黑白染色之后建立二元关系网络流模型，然后使用$Dinic$进行最小割

T4：呃呃呃暂时还不会