知识回顾:
-
巩固:生成树,DP,分层图,简单数论,线段树。
-
深入研究:网络流。
-
简单了解/没学明白:FFT。
练题:
P6144 [USACO20FEB]Help Yourself P
定义 \(f_r\) 为以 \(r\) 结尾的线段集合的总贡献。
对于一个线段 \([l,r]\) 可以考虑分成 \([1,l)\), \([l,r]\) 和 \([r+1,n]\) 三种情况转移。
区间求和,区间乘 2,显然可以用线段树。
由于 k 次方的存在,线段树的每个结点还需维护 \(d_i\) ,表示值的 i 次方为多少。
复杂度 \(O(nk^2 \log k)\) 。
AT_abc280_d [ABC280D] Factorial and Multiple
先给 k 分解质因数,接着二分 x ,判断 x! 是否能包含 k 的所有因子。
而对于 x! 中质因子 d 的个数,可以在 \(O(\log x)\) 内计算出来,即:
\[\sum\limits_{i=1}^{\log_d x}\left\lfloor \frac{x}{d^i}\right\rfloor \]每个因子都算一遍,判断大小即可。
k 很小,直接建一个 k 层的分层图然后跑一边最短路。
很久以前在信友队里做过的一道题,偶然看见就又做了一下。
非常经典的容斥 DP。
定义 \(f_i\) 为从起点走到第 i 个障碍点的方案数,则转移方程为:
\[f_i=\dbinom{x_i+y_i-2}{x_i-1}-\sum\limits_{j(x_j\le x_i, y_j \le y_i)}^{n}f_j \cdot \dbinom{x_i-x_j+y_i-y_j}{x_i-x_j} \]最后 \(f_n\) 即为答案。
题目要求我们求出 \(\sum\limits_{i=1}^{n} k\mod i\) 。
稍微转化一下变为 \(n \cdot k - \sum\limits_{i=1}^{n}i \cdot \left\lfloor \frac{k}{i}\right\rfloor\) 。
可以用除法分块 \(O(\sqrt{n})\) 解决。
64pts 很好拿,暴力建图暴力 kruskal。
然后我们发现其实只用考虑横条和纵条。
先将它们的权值从小到大排序,然后考虑加入当前条后又多少个边需要选上即可。
网络流基础题。
原点 s 向练习册连边,练习册向答案连边,答案向终点 t 连边。边权均为 1。
为了防止同一本练习册被走多次,将其一本练习册拆为两个点,边权为1。
跑一边 dinic/EK 就行了。
显然可以先跑一边 spfa 求出 dis 数组。
然后只需要考虑在最短路上的边,即 \(dis_v==dis_u+w\)。
由于容量限制在点上,我们要拆点,之后就是各种连边。
可以先将问题简化,逐位计算。
每个给定值的点的点权都变为了0/1。
把 0 连向 s,把 1 连向 t,求一边最小割就行了。
最大权闭合子图模板题。
净收益 = 实际总收入 - 实际总成本 = 全部的收入项 - 放弃的收入项 - 必要的成本项 = 全部的收入项 - (放弃的收入项 + 必要的成本项)
后者就是一个最小割问题。
总结了一首打油诗:
成本收入两头连,依赖关系无穷边,从源找出最小割,全部收入往下减。
P4001 [ICPC-Beijing 2006] 狼抓兔子
平面图转对偶图,疯狂建边,跑一边最短路。
模拟赛:
校内模拟赛:
T1: 解方程
老套路题了,meet in the middle。
T2:序列
老 DP 题了,定义 \(f_{i,j}\) 为 i 的全排列中逆序对个数为 j 的个数,转移直接从 i-1 里找就行,可以用前缀和优化到 \(O(nm)\) 。
听说有更优的做法,之后研究一下。
T3:完全图
老生成树题了,按边权从小到大枚举每一条边,合并的时候计算一下端点分别在两个连通块里的边的个数,并将其边权定为 w+1。复杂度 \(O(n \log n)\)。
T4:平面上的点A
有点意思。
赛时做法:复杂度 \(O(n \log n \log n)\)。
考虑从大到小枚举 y 的坐标,然后二分 x 的坐标,利用树状数组快速计算出四个区域的个数。
设 k0~k3 表示从左上角顺时针区域的个数。
则我们可以定义 s 树状数组实时更新 k0 的大小。
然后再搞一颗维护以点的 x 坐标为关键字的树状数组,用来计算 (k0+k1),和一颗以点的 y 坐标为关键字的树状数组,用来计算 (k2+k3)。
相减即可得出 k0~k3 的值。
更优的做法:复杂度 \(O(n \log n)\)。
我们先二分答案 ans。
然后从下到上枚举 y 坐标。
可以发现上半部分的个数越来越少,下半部分的个数越来越多(废话。
于是可以用类似双指针的方法在上下两部分分别找到最后一个能使 k0 和 k2 小于等于 ans 的位置,并更新答案。
T5:密钥
简单题。
两两枚举,找到第一个不相同的位置,并连一条边,最后判断一下有没有环即可。
复杂度 \(O(能过)\)
标签:线段,log,第一周,省选,复杂度,个数,计划,练习册,k0 From: https://www.cnblogs.com/HQJ2007/p/17561591.html