「云玩家拯救计划」小题单

AcFunction's Blog

2019-02-02

云玩家拯救计划（雾

网络流

A(CF1009G)：直接贪心，用二分图里的一个霍尔定理来判断合法性。实现上可以简单一点。

B(CF808F)：先二分答案，观察到除了 2 以外所有质数由偶数+奇数得来。于是 check 就可以特判 1 + 1 的情况，建图最小割即可。

C(CF164C)：把任务按照开始时间排序，S -> 最小的开始时间 -> 第二个 -> .. -> 第 n 个 -> T 连流量 m 费用 0 ，再对于每个任务连一条从起点到终点加 1，流量 1 费用 -c 的边。然后最小费用最大流就好了。~~我还是不会输出方案（捂脸~~

D(CF277E)：以前做过…写过题解…

E(CF1082G)：把每个点和每条边算成一个点，边的权值是负的，然后最大权闭合子图

F(BZOJ3158)：考虑 % 4 可以证明奇数方+奇数方不等于完全平方，同时偶数的最大公约数 > 1 所以奇数一边偶数一边建二分图然后就是套路的最小割了
G(CF863F)：可以求出每个点的可行区间，然后那个平方的条件就可以拆边。就是 (1,1), (3,1), (5,1), (7,1) …. 然后最小费用最大流

H(CF498C)：显然除质因子答案最大 && 质因子之间相互独立。对于每一个出现过的质因子跑最大流就行了

数论

A(BZOJ2154) ：不妨设 $n \leq m$

$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} lcm(i, j)$

$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \frac{ij}{\gcd(i,j)}$

$=\sum\limits_{d=1}^{n}\sum\limits_{i’=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j’=1}^{\lfloor \frac{m}{d} \rfloor} i’j’d [\gcd(i’,j’)=1]$

$=\sum\limits_{d=1}^{n}d \sum\limits_{i’=1}^{\lfloor \frac{n}{d} \rfloor} i’ \sum\limits_{j’=1}^{\lfloor \frac{m}{d} \rfloor} j’ [gcd(i’,j’)=1]$

$ =\sum\limits_{d=1}^{n} d \sum\limits_{i’=1}^{\lfloor \frac{n}{d} \rfloor} i’ \sum\limits_{j’=1}^{\lfloor \frac{m}{d} \rfloor} j’ \sum\limits_{d’|i’,d’|j’}\mu(d’)$

$=\sum\limits_{d=1}^{n}\sum\limits_{d’=1}^{n}\mu(d’)d \sum\limits_{i’=1}^{\lfloor \frac{n}{d’d} \rfloor} i’ \sum\limits_{j’=1}^{\lfloor \frac{m}{d’d} \rfloor} j’ $

令 $dd’=T, F(T)=\sum\limits_{d | T}\mu(d)\frac{T}{d}$ 。F 可以线性筛出来，就做完了）

然后这个题连分块都不用（

好像有需要分块的加强版被权限了（

B(BZOJ2440)：题解

C(BZOJ3529)：题解

D(HDU6053)： 待填坑

E(BZOJ2956)：

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} i\not= j(m\%j)$

$=\sum\limits_{i=1}^{n}n\%i\sum\limits_{j=1}^{m}m\%j-\sum\limits_{i=1}^{n}(n\%i)(m\%i)$

然后把 $n\%i$ 搞成 $n -i \lfloor\frac{n}{i}\rfloor $ ，$m\%i$ 同理，然后推推式子分个块就做完了

F(HDU4947)：待填坑

G(BZOJ2005)：有点简单懒得写hhh

H(HDU4473)：把题目要求转化为有多少个有序对 (a,b,c) 满足 abc = n。然后分三类 a,b,c;a,a,b;a,a,a 讨论下就行了（优秀的暴力…

I(HDU5942)：有点难啊…看的这个题解

线段树主席树

A(HDU4578)：线段树维护加标记乘标记以及三个值分别表示和，平方的和，立方的和。加标记更新就用二项式展开一下倒序更新；乘标记就是和乘上d，平方乘上d^2，立方同理…然后覆盖操作拆成先乘 0 再加。

B(BZOJ1818)：先把题目条件转化成所有由这些点组成的平行于坐标轴的线段之间有几个交点（端点也算）。然后就直接把坐标离散化一下然后扫描线扫过去中间用树状数组维护一下就行了。

C(COT)：板子再见

D(BZOJ3261)：搞个可持久化 0/1 trie 维护前缀异或和然后就做完了（板子）

E(CF484E)：二分答案下，然后对于一个值是否合法只需要把 > 该数的变成 1 ，小于该数的变成 0 然后用线段树维护这个区间内的最长的 1 序列。由于不能开一堆线段树，所以用主席数的思想就行了（我都觉得我说的不清楚…）

F()：

G：线段树合并裸题

H：kruskal 重构树上主席树

I：对每一位维护线段树就行了

J：压个位然后维护区间或就行了

K：模板题再见