FlyInTheSky's blog

OI, 梦开始的地方。


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 朋友

  • 搜索

Codeforces 1110D (DP)

发表于 2019-02-08 | 分类于 Codeforces | | + s

Codeforces 1106E
题意:给定一个$n$长值域为$m$的序列,你要将其组成尽可能多的三元组$(a, b, c)$满足$a=b=c$或者$b=a+1,c=b+1$。

一开始读错题了。
先将所有数存在一个桶里,按数大小来DP。
显然对于一种方案$(a,b,c)$,他只会重复至多$2$次。
那么对于一个方案$(i,i+1,i+2)$,他最多只会有$2$个
那么设$dp(i,0/1/2,0/1/2)$为前$i$个数,第一个数是$i$的三元组个数,第二个数是$i$的三元组个数的最大个数。
转移
$$
dp(i,a,b)=\max_{0\leq c \leq 2}(dp(i-1,b,c)+c+(cnt-a-b-c) / 3)
$$
其中$cnt$为$i$数的个数。

后面$(cnt-a-b-c) / 3)$等价于将多余的$i$组成三元组$(i,i,i)$

阅读全文 »

「Hdu 5608」function (莫比乌斯反演 + 杜教筛)

发表于 2019-02-07 | 分类于 Hdu | | + s

hdu 5608
题意:给定$n$和函数$f, g$满足
$$
g(n)=n^2−3n+2\\
g(n)=\sum_{d|n} f(d)
$$
求
$$
\sum_{i=1}^n f(i) \mod 10^9+7
$$

显然$f * I = g$,杜教筛即可。
即
$$
S(n)=\sum_{i=1}^n g(i) - \sum_{i=2}^n S(\lfloor \frac nd \rfloor)
$$
将$g$每个项分离出来,用平方数列前缀和公式+等差数列公式即可求解。

对于前$n^{\frac 23}$的$f$,反演一下即可。即
$$
f(n)=\sum_{d|n} g(d) \mu(\frac nd)
$$
注意这个式子不是很常用。

阅读全文 »

LCT 学习笔记

发表于 2019-02-05 | 分类于 算法笔记 | | + s

模板及讲解

LCT,也就是Link-Cut Tree的缩写。它是最常见的一种解决动态树问题的工具。不过说它是树也不准确,因为它维护的可以是一片森林。

实链剖分

将某一个儿子的连边划分为实边,而连向其他子树的边划分为虚边。
区别在于虚实是可以动态变化的,因此要使用更高级、更灵活的Splay来维护每一条由若干实边连接而成的实链。
LCT维护的对象其实是一个森林。

LCT 性质

1、每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径,且中序遍历Splay得到的每个点的深度序列严格递增。

2、每个节点包含且仅包含于一个Splay中

3、边分为实边和虚边,实边包含在Splay中,而虚边总是由一棵Splay指向另一个节点(指向该Splay中中序遍历最靠前的点在原树中的父亲)。

阅读全文 »

「Bzoj 2730」「HNOI2012」矿场搭建 (边双联通分量+分类讨论)

发表于 2019-02-03 | | + s

Bzoj 2730
题意:给一张无向图,让你加一些出口,使得任意点删除后图上任意点都能找到出口。

复习一波点双联通分量
考虑求出割点和双联通分量,然后对于每个双联通分量,我们考虑
若这个双联通分量有两个及以上割点,那么不需要建立出口
若这个双联通分量有一个割点,那么如果这个割点删了这个图就找不到出口了,要加一个出口
若这个双联通分量没有割点,即这个子图与其他子图不连通,要加两个出口

加出口即加在任意非割点的点上即可

阅读全文 »

「Bzoj 1911」「Apio2010」特别行动队 (最大化斜率优化DP)

发表于 2019-02-02 | 分类于 Bzoj | | + s

BZOJ 1911
题意:有$n$个数$x_i$,将其分成连续的组,每组的分为$a\sum x_i + b\sum x_i +c$,求最大的总分。
设$dp(i)$为前$i$个分组的最大的总分。设$\operatorname{sum}(n)$为$\sum\limits_{i=1}^n x_i$
则
$$
dp(i)=\max(dp(j)+a[\operatorname{sum}(i)-\operatorname{sum}(j)]^2 + b[\operatorname{sum}(i)-\operatorname{sum}(j)] + c)
$$
则决策点可以表示为点$(\operatorname{sum}(j), dp(j)+a \cdot \operatorname{sum}(j)^2 - b \cdot \operatorname{sum}(j))​$

这里要维护最大值,所以与之前的斜率优化不同,维护一个上凸包即可。

注意有负数时不要用叉积,符号不能确定!

知识点
1、有负数时不要用叉积,符号不能确定

阅读全文 »

「Luogu 3768」简单的数学题 (莫比乌斯反演 + Dirichlet卷积 + 杜教筛)

发表于 2019-02-02 | | + s

3768 简单的数学题
题意:给定$n, p$,求
$$
\sum_{i=1}^n \sum_{i=1}^n ij\gcd(i,j) \mod p
$$
枚举约数
$$
\sum_{d=1}^n d\sum_{i=1}^n \sum_{i=1}^n ij [\gcd(i,j)=d]
$$
将后面的提取因数
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij [\gcd(i,j)=1]
$$
将布尔式化成$\mu$
$$
\sum_{d=1}^n d^3 \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac nd \rfloor} ij \sum_{k|i,k|j}\mu(k)
$$
先枚举$k$
$$
\sum_{d=1}^n d^3 \sum_{k=1}^{\lfloor \frac nd \rfloor} k^2 \mu(k) (\sum_{i=1}^{\lfloor \frac n{kd} \rfloor} i)^2
$$
设$T=kd​$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 \sum_{d|T}d^3 (\frac Td)^2 \mu(\frac Td) \\
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2\sum_{d|T}d \mu(\frac Td)
$$
后面是个卷积形式,根据$\mu * id = \varphi$
$$
\sum_{T=1}^n (\sum_{i=1}^{\lfloor \frac nT \rfloor} i)^2 T^2 \varphi(T)
$$
现在要求$T^2 \varphi(T)$的前缀和。不妨先设$g=id^2$

$$
(f * g)(i)=\sum_{d|i} d^2 \varphi(d) \times id^2(\frac id) \\
= \sum_{d|i} d^2 \varphi(d) \times (\frac id)^2 \\
= \sum_{d|i} i^2\varphi(d) \\
= i^2\sum_{d|i} \varphi(d) \\
= i^3
$$

则

$$
g(1)S(n)=\sum_{i=1}^n(f * g)(n) - \sum_{i=2}^n g(i)S(\lfloor \frac ni \rfloor) \
S(n)=\sum_{i=1}^n i^3 - \sum_{i=2}^n i^2 S(\lfloor \frac ni \rfloor)
$$

再由两个公式
$$
1^3+2^3+ \dots + n^3 = (1+2+ \dots + n)^2 \\
1^2+2^2+ \dots + n^2 = \frac{n(n+1)(2n+1)}{6}
$$
即可完成求解

坑:
1、$n$要运算时一定要先模,否则$10^{10} \times 10^{10}$马上爆炸
2、$2n$也要模
知识点:
1、整除分块只有$\lfloor \frac nd \rfloor$部分相同,可以用来乘
2、Dirichlet卷积运用
3、LCM和那题没搞明白的东西
4、预处理逆元免除$\log$

阅读全文 »

「Loj 6008」「网络流 24 题」餐巾计划 (最小费用最大流,资源调配)

发表于 2019-02-01 | 分类于 Loj | | + s

Loj 2632
题意:见上。

orz 网络流24题之餐巾计划问题 - five20 - 博客园

做法($(c=容量, w=费用)$):
将每天拆点拆成$x_i,y_i$($x$为脏餐巾点,$y$为干净餐巾点)
1、$S$到$x_i$:$(r_i, 0)$,补脏的 (用过的毛巾假设全丢掉,然后再从$S$补偿脏毛巾。以达到一个毛巾用$n$次有流量$n$)
2、$S$到$y_i$:$(∞, P)$,买入毛巾
3、$y_i$到$T$:$(r_i, 0)$,使用毛巾 (用过的毛巾假设全丢掉)
4、$x_i$到$y_{i+M}$:$(∞, F)$,快洗
5、$x_i$到$y_{i+N}$:$(∞, S)$,慢洗
6、$x_i​$到$x_{i+1}​$:$(∞, 0)​$,存着脏毛巾

上述博客思路为:
1、先拆点,然后考虑快洗慢洗、不洗(存着脏毛巾)
2、发现错误(一个毛巾用两次只有流量$1$),修改为舍弃流和补偿流

知识点:
1、资源调配问题,舍弃流和补偿流的方法

阅读全文 »

「poj 3709」K-Anonymous Sequence (斜率优化DP,延迟加入决策)

发表于 2019-02-01 | 分类于 poj | | + s

poj 3709
题意:给定一个数列 $a$, 分成若干段,每段至少有$k$个数, 将每段中的数减少至所有数都相同, 求最小的变化量

设$dp(i)$为前$i$个的最小变化量。
则
$$
dp(i)=\min_{i-j \leq k}(dp(j)+\operatorname{sum}(i)-\operatorname{sum}(j)-i \cdot a_{j+1} +j \cdot a_{j+1})
$$

显然可以斜率优化。决策表示为$(a_{j+1}, dp(j)-sum(j)+j \cdot a_{j+1})$,即可算斜率。
注意$i-j \leq k$的限制,我们可以考虑延迟加入决策(具体看代码),预处理$[0,2k]$的答案。

知识点
对于这种有限制的斜率优化可以考虑延迟加入决策

阅读全文 »

Codeforces 1106E (倒序DP + Set)

发表于 2019-02-01 | 分类于 Codeforces | | + s

Codeforces 1106E
题意:有 $k$ 个区间 $[s_j, t_j]$ 表示一段时间,每个区间有 $t_j, w_j$ 表示若选择这个区间则 $t_j$ 后才能选其他的区间,选择区间的权为 $w_j$ 。现在有一个人从 $1$ 时刻开始选区间,他会选当前能选的最大权的区间,若存在多个,选 $d_j$ 大的区间。现在有 $m$ 次机会,每次可以使得这个人在某一秒不能选区间。求当这 $m$ 次机会使用得最优时,这个人最小能选择区间权和。

正序DP不太好做。
考虑倒序DP,设$dp(i,j)$为$[i,n]$用了$j$次机会的最小权和。
则
$$
dp(i,j)=\min(dp(i+1,j-1),dp(i+1,j),dp(g, j))
$$
其中$g=\max\limits_{i \in {[s_j, t_j], j\in[1,k]}}(d_j)$

这个$g$可以用set维护。
具体就是将区间端点存起来,然后枚举时间线时看是否超出了,超出即删掉,如果有新的加入,就加入。

阅读全文 »

「Bzoj 3930」「CQOI2015」选数(莫比乌斯反演 + GCD性质 / 杜教筛)

发表于 2019-01-30 | 分类于 Bzoj | | + s

BZOJ 3930
题意:给定$n,K,H,L$,求

Markdown

这个形式和在$[1,n],[1,m]$中的$gcd$类似,我们从$N=2$开始考虑。
显然
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \left \lfloor \frac n{kd} \right \rfloor^2
$$
扩展到高维也类似,所以可以得到
$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor} \mu(d) \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n
$$

然而$\lfloor \frac Hk \rfloor$是$O(H)$级的,不能满足。

引理:

当所有数不全部相同时,$\gcd\left ( i_1, i_2, \dots, i_N \right ) \leq \max\left ( i_1, i_2, \dots, i_N \right ) - \min\left ( i_1, i_2, \dots, i_N \right )$

证明:设$d = \gcd\left ( i_1, i_2, \dots, i_N \right ), a = \min\left ( i_1, i_2, \dots, i_N \right ), b = \max\left ( i_1, i_2, \dots, i_N \right )$
显然$a = k_1d (k_1 \in \mathbb{Z}^+), b = k_2d (k_2 \in \mathbb{Z}^+, k_2 > k_1)$, 所以$b - a \geq d$,证毕。

所以$[H, L]$中的一个不全部相同的序列的$\gcd$不会超过$H - L$个,只用处理不全部相同的序列,所以可以得到

$$
f(k)= \sum_{d=1}^{\lfloor \frac Hk \rfloor - \lfloor \frac {L-1}k \rfloor} \mu(d) \left( \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )^n - \left (\left \lfloor \frac H{kd} \right \rfloor - \left \lfloor \frac {L - 1}{kd} \right \rfloor \right )\right)+[L \leq k \leq H]
$$

注意需要加上$[L \leq k \leq H]$,因为这样就可以选$n$个$k$。

本题也可以直接杜教筛筛出$\mu(d)$的前缀和,但是我并不会……等学了杜教筛再来填坑吧。

阅读全文 »
123…52
FlyInTheSky

FlyInTheSky

自己选择的路,跪着也要走完。

515 日志
17 分类
123 标签
一言
© 2016 — 2019 FlyInTheSky
由 Hexo 强力驱动
|
主题 — NexT.Gemini v6.0.3
Hosted by Coding Pages
本站总访问量次