纪中NOIP集训总结

$2021-11-10$

$T1$：

思路$AK$，$long \; long$ 开爆空间

分组背包之后合并

$T2$：

暴力$55$，

正解二分答案再套二分求解

$T3$：

莫反？？不会

$T4$：

单调队列加二分求出某个$Wenhao$左右最近的比他高的袋鼠墙

再用树状数组之类的搞出前缀和，总时间复杂度$O(n \log n)$

$2021-11-11$

$T1$：

发现可以让前面的牌变化大，后面的牌变化小，这样就会是最优的

（当$a<b<c<d$时，$ad+bc>ac+bd$）

可以$O(n)$排序，求出变化后的序列，再用$O(n \log n)$匹配求答

$T2$：

$f_i=\sum f_j * [mex([i,j]) == K]$ 其中$f_i$表示结尾为i的方案数和，$K$为全局$[1,n]$的$mex$

用双指针和桶维护$\sum f_j$，可以$O(n)$过

$T3$：

类似$kruskal$重构树的笛卡尔树，以点权从小到大构造树$T1$，从大到小构造树$T2$，

对于一个点对$(x,y)$，如果$T1$中$x$为$y$祖先，$T2$中$y$为$x$祖先，那么对答案产生$1$的贡献

用树状数组（常数小），$O(n \log n)$

$T4$：

分类讨论，用类线段树优化$dijkstra$的方法解决特殊点到特殊点和一般点

一般点到特殊点和一般点就为一般点出边权

$2021-11-15$

$T1$：

考场$n^2$求和为$n$的连通块，没想到鸽巢，链式前向星还开小了

用前缀和$+$鸽巢线性找到连续一段的连通块

快读快输可以有效提升速度

$T2$：

考虑答案总和是$2^{n-1}$，当$k>1$的时候，方案数一定$\le 1$

$T3$：

打的是$2^n$的暴力$dfs$，居然拿了$60$分

正解是看性质，当$k$为偶数，存在一个中心点使得所有点到它的距离为$k/2$

当$k$为奇数，只能选择两个点，统计一下乘起来，再用点分治或长链剖分

$T4$：

迷惑？？？？？？

$2021-11-16$

$T1$：

奇偶函数转换，（一大堆看不懂的符号和定义），最后求$gcd$

$T2$：

矩阵快速幂优化概率$dp$转移

$T3$：

数论题，知道对于一个数$n = \prod p_i ^ {a_i}$（$p_i$为素数），有$ans(n) = \prod (a_i + 1)*[p_i \mod 4 == 1]$

可以暴力枚举$p_i$，加高精度，求出答案

$T4$：

$bitset +$ 定期重构

$2021-11-17$

$T1$：

结论题，设$d_i$表示第$i$个点的度数，则答案为$\sum_{i=1}^{n} \frac{d_i}{d_i+1}$

可以线性求逆元，快读可以有效加速($26ms$)

总复杂度为$O(n)$

$T2$：在线莫队我不会

$T3$：恶心构造调半天

$T4$：

限制变为了⼀类中某个元素与另⼀类中某个元素同时选/不选，要付出代价。我们只需反转其中⼀类元素的选/不选即可。 现在我们只需建图后在⼆分图上跑最小割即可。由于每条边流量都为$1$ ，因此使⽤ $Dinic$ 算法时间复杂度$O(n \sqrt{n})$

$2021-11-18$

$T1$：用单调栈$+$二分，找出最长逆序对，覆盖区间

$T2$：整除分块，即$\sum_{i=1}^{n} \lfloor \frac{n}i{} \rfloor$，可以转换成

$$\sum_{l=r+1,r=\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor} \rfloor}^{l>n} (r-l+1)*(\lfloor \frac{n}{l} \rfloor)$$

$T3$：$dp$前缀和优化

$T4$：离线分块双指针大恶心题