misaka18931's blog
0%

Posted on Edited on

Implementation

Dinic最大流

各种剪枝

Dinic费用流

队列优化的bellman-ford, 实现时需要注意入队标记!

HLPP最大流

  1. 用优先队列会多\(\log\). (\(O(n^2\sqrt m\log n)\))
  2. 直接使用队列是\(O(n^3)\)的.
  3. gap优化
  4. bfs确定初始高度.

建图

最大流

按照定义建图

最小割

  1. 对于一条路径上的所有边, 是选择关系.
  2. 通过连inf边, 实现各种约束条件.

二分图匹配

在两个集合之间连接有向边即可.

最大权闭合子图

提前计算所有正权点的贡献.

运用最小割模型, source向正权点连 cap=权值 的边, 表示不选的代价; 负权点向sink连 cap=|权值| 的边, 表示选择的代价. 对原图中的边对应建一条inf边.

发现合法的子图一定是一个割.

最小路径覆盖

转化为二分图匹配: 每个点入度, 出度最多为1, 并且每连一条边, 入度, 出度均+1. 将每个点拆成入点和出点跑二分图匹配.

网络流24题

#6000. 「网络流 24 题」搭配飞行员

二分图最大匹配.

#6001. 「网络流 24 题」太空飞行计划

转化为最大权闭合子图

#6002. 「网络流 24 题」最小路径覆盖

最小路径覆盖

#6003. 「网络流 24 题」魔术球

增量网络流, 跑最小路径覆盖.

#6004. 「网络流 24 题」圆桌聚餐

最大流建图.

#6005. 「网络流 24 题」最长递增子序列

WA'ed QAQ

#6006. 「网络流 24 题」试题库

最大流建图

#6007. 「网络流 24 题」方格取数

最小割建图.(多变量选择)

#6008. 「网络流 24 题」餐巾计划

费用流建图

#6009. 「网络流 24 题」软件补丁

不是网络流...

#6010. 「网络流 24 题」数字梯形

费用流建图

#6011. 「网络流 24 题」运输问题

费用流建图

#6012. 「网络流 24 题」分配问题

同 #6011

#6013. 「网络流 24 题」负载平衡

简单建图

#6014. 「网络流 24 题」最长 k 可重区间集

考虑在数轴上建立网络流, 额外加入每一条长度为0的线段, 这样就变成一定覆盖k次.

#6015. 「网络流 24 题」星际转移

对时间拆点

#6121. 「网络流 24 题」孤岛营救问题

直接DP

#6122. 「网络流 24 题」航空路线问题

费用流+拆点.

Posted on Edited on

Posted on Edited on

LOJ定向练习(DP & Probability & Expectation)

#2112. 「HNOI2015」亚瑟王

如果直接对这个游戏过程DP, 是非常困难的, 我们可以直接考虑终局时选择到每一张牌的概率.

需要考虑两种情况: 1. 某一回合选的牌在他之前(不考虑他). 直接放到状态里 2. 这张牌在前面和回合中已经用过了. 补集转化即可.

#2136. 「ZJOI2015」地震后的幻想乡

利用第k大数的期望公式(题目中给出), 枚举MST中瓶颈的大小, 乘上概率即可. 容易求出MST\(\le k\)的概率(子集DP), 考虑差分转化.

#3312. 「ZJOI2020」传统艺能

考虑分别考虑每一个线段树上节点有标记的概率. 利用线段树上定位区间的性质, 利用人类智慧+矩阵快速幂过题.

#6495. 「雅礼集训 2018 Day1」树

数据范围诈骗! 直接递推!

#6406. 「ICPC World Finals 2018」绿宝石之岛

行列转置, 降低复杂度.

#2542. 「PKUWC2018」随机游走

关于树上随机游走问题:

法一: 计算边权. 期望距离依然具有可加性(考虑按照第一次经过中间点的时间划分) 于是可以使用up and down trick算出每条有向边的期望长度. 这样可求任意路径的长度.

法二: 树形消元解方程 考虑从终点出发倒着进行, 这样就可以列方程解出到每个点的期望. 树形消元的trick: 把起点当成根, 把儿子设成父亲的线性函数, 这样就可以dfs求出每个点的系数, 由于根没有父亲, 根的常数项就是答案.

#2145. 「SHOI2017」分手是祝愿

利用算术基本定理, 把因数关系看成高维前缀和, 剩下的部分就是一个一维的随机游走, 差分法解方程即可.

#3043. 「ZJOI2019」线段树

把操作1看成: 以\(\frac12\)的概率决定是否进行操作, 就可以利用 #3312 的方法做了.

#6509. 「雅礼集训 2018 Day7」C

TODO 解方程!

#6118. 「2017 山东二轮集训 Day7」鬼牌

推式子练习.

Posted on Edited on

JOI 2022 Final

#3662. 「JOI 2022 Final」星际蛋糕推销

implement useful algorithm

#3663. 「JOI 2022 Final」自学

useful algorithm\(\times2\).

#3664. 「JOI 2022 Final」选举

直接枚举最终一共有\(m\)人在演讲.考虑当确定哪些city需要招人, 另外哪些要拿到选票时, 一定是先把人招全, 再拿到剩下的选票更优. 并且招人的顺序一定是按\(b_i\)不减.

于是按照\(b_i\)排序, 发现去掉只拿选票的城市以后, 招到人的城市一定在剩余城市中构成一个前缀.

定义\(f[n][k]\)表示前\(n\)个城市, \(k\)个只拿选票的最短时间. \(O(n^2k)\) DP.

另外据说可以三分\(m\), 正确性不明. link

#3665. 「JOI 2022 Final」铁路旅行 2

经典的倍增+维护可达区间. 这次转移需要用RMQ. \(O(n\log^2 n + q \log n)\), 空间2log 或 \(O((n+q)\log^2 n)\), 空间1log.

#3666. 「JOI 2022 Final」沙堡 2

idea: 1. 对于合法状态的判定, 尝试把它写成一个对每一个元素相对独立的函数(即每个元素的贡献具有局部性), 方便后续各种操作. 2. 扫描线

考虑到对于每个数, 我们显然会走它在相邻格子中的前驱和后继, 考虑连一条有向边, 这样一个矩形合法, 也就是成链, 当且仅当\(0\)入度点只有\(1\)个.

而每个点的入度只在border在它附近的时候会变化.

大力前缀和即可.

做到\(O(H^2W)\)需要枚举一维, 用一个桶计数另一维.

Posted on Edited on In

  1. 一个和为\(0\)的随机序列\(\{a_n\}\), \(E(\max_i(\sum_{j\le i}a_j))=O(\sqrt N)\). 常用于DP, 通过随机化降低时间.

  2. 任意一个序列, 其中满足\(\max(A[l,r])\gt \max(A[l',r']),[l,r]\subsetneq [l',r']\)的极大子段个数是\(O(n)\)的. 求法: 单调栈

  3. 对于一个排列, 对逆序对连边, 形成的连通块一定是区间.

  4. 一个在\([0,1]\)之间随机的实数序列, 长为\(n\), 则第k小数的期望 \(=\frac k {n+1}\).

Posted on Edited on In

AtCoder Regular Contest 135

D - Add to Square

考虑寻找不变式。

发现\(r_i=\sum_{i,j}(-1)^{ij}A_{ij}\)与\(c_j=\sum_{i,j}(-1)^{ij}A_{ij}\)是不变的。充分性可以贪心消元构造。

于是把每个数乘上\((-1)^{ij}\)以后，就变成每行/列和不变。

答案就是行/列的绝对值的和中更大的那个。

E - Sequence of Multiples

不妨设\(B_i=A_i/i\). 有递归式\(B_{i+1}=\lfloor \dfrac {iB_{i}}{i+1}\rfloor+1\). 至此通过枚举不同的\(B\)可以做到\(O(\sqrt N)\). 发现可以继续差分， 令\(C_i=B_i-B_{i+1}\)， 枚举\(C_i\)可以做到\(O(\sqrt[3] N)\).

F - Delete 1, 4, 7, ...

考虑通过\(f(x)=\lfloor1.5x\rfloor+1\)来表示保留的数原来的位置.

这样就可以用\(f^{(k)}(x)\)通过复合计算出原来留下了哪些数.

考虑当\(k\)较大时, 最终剩下的数较少, 可以直接暴力.

当\(k\)较小时, 需要考虑研究\(f\)的性质: \(f^{(k)}(x+2^k)=f^{(k)}(x)+3^k\).

然而\(O(k2^k)\)的做法不能通过..., 发现可以重复利用这个性质: \(f^{a+b}(x+2^b)=f^a(f^b(x)+3^b)\)

内层是一堆形如\(a, a + c, a + 2c \dots\)的数的点值. 倍增即可.

Posted on Edited on In

集合幂级数及其运算

集合幂级数

对于实值函数 \(f:U\rightarrow R\), 定义集合幂级数\(F(z)=\sum_Sf(S)z^S\), 其中\(z^S\)满足\(z^S\cdot z^T=z^{S\cup T}\).

位运算卷积

FMT (子集求和)

按位分治

1
2
3
4
for (int i = 1; i < N; i <<= 1)
  for (int j = 0; j < N; j += i * 2)
    for (int k = j; k < i + j; ++k)
      f[k+i] += f[k];

FMT 满足如下性质:

  1. \(FMT(A)+FMT(B)=FMT(A+B)\)
  2. \(FMT(A_B)=FMT(A)\cdot FMT(B)\), 其中\([A_B]_i=\sum_{k|j=i}A_kB_j\)

### IFMT (子集差分)

FMT 的逆运算

1
2
3
4
for (int i = 1; i < N; i <<= 1)
  for (int j = 0; j < N; j += i * 2)
    for (int k = j; k < i + j; ++k)
      f[k+i] -= f[k];

集合幂级数运算

集合幂级数按占位拆分

\(F_i(z)=[u^i]\sum_Sf(S)z^Su^{|S|}\)

子集卷积

\(H(z)=\sum_{S\cap T=\emptyset}[z^S]F(z)\cdot [z^T]G(z)z^{S\cup T}\)

注意集合不交的条件, 可以改成\(|S|+|T|=|S\cup T|\), 于是利用占位幂级数进行运算即可.

\[ \begin{aligned} H_k(z)&=\sum_{i+j=k}F_i(z)G_j(z)\\ FMT(H_k)&= \sum_{i+j=k}FMT(F_i)FMT(G_j)\ \end{aligned} \] 交换求和次序, 对\(FMT\)数组的每一项独立计算.

记\(f_S(z)=\sum_k [FMT(F_k)]_Sz^k\), 子集卷积实际上是 \(h_S(z)=f_S(z)g_S(z)\).

其他运算

\(\exp\), \(\ln\), 求逆, 多项式复合等运算, 和刚才的分析同理. 对每一项占位多项式进行对应的操作即可.

note: exp将联通图转化为有多个联通分量的图, ln作为逆运算反之.

关于半在线/在线卷积

注意到\(O(n^2)\)递推的方向是集合大小不断增加, 下一层的值由前面层的答案组成, 天然支持在线.

Eg

https://loj.ac/p/6719

https://loj.ac/p/6729

https://loj.ac/p/6730

https://loj.ac/p/2340

Posted on Edited on In

AtCoder Regular Contest 134

E - Modulo Nim

现考虑\(m=2,3,4\)的情况, 发现必败局面要么是\(\{a:a\in A\}=\{4,8\}\), 要么所有的数都是\(12\) 的倍数. 因为值域很小\(a_i\le 200\) , 可以直接暴搜.

(赛时没有推出\(m=3\)的情况, 没有利用值域性质)

F - Flipping Coins

  1. 发现操作对环独立(ok)

  2. \(\Delta\)考虑到如果把环拆成若干个递增的区间, 则每个偶数长的区间全部覆盖, 奇数长的区间会空出第一个位置. 于是答案就是奇数长度区间的数量.

Posted on Edited on

「CCO 2021」换换排序

题意转化为: \(Q\)次查询数组中两个值之间形成的逆序对数.

这个问题可以利用双指针在\(O(\#a+\#b)\)时间内解决, 且贡献是对称的.

考虑根号分治, 对于\(\#a\ge B\)的值, 利用\(O(n\cdot \#a)\)时间求出对所有数的逆序对个数.

对于其余部分, 每次询问时间是\(O(B)\) 的.

时间可以做到\(O(n\sqrt Q)\)

空间: 在线\(O(n\sqrt n)\), 离线\(O(n)\).

「CCO 2021」在黑暗中走出另一个迷宫

考虑如果每一个指针都指向父亲, 移动的过程就是Euler Tour.

考虑到当每个点被第一次访问到以后, 回溯时一定会把指针指向它的父亲.

模拟这个让整棵树逐渐变得"合法"的过程: 每访问一个"不合法"的节点, 对在指针顺时针方向的节点都进行访问(按照dfs序), 然后回溯. 而剩下的节点一定会在下一轮从根出发时被第一次访问到.

于是直接进行dfs, 每次dfs顺时针方向的儿子, 把其他的儿子加入一个队列中, 依次处理, 可以得到每一个点最早访问到的轮数.

于是问题转化为在欧拉序上不断插入, 查询第k大.

时间\(O(n\log n + Q)\).

「CCO 2021」商旅

首先对没有出度的点递归删除, 去除无解情况.

现在考虑最大边权的边\(e\), 如果它是\(e.u\)的唯一出边, 则\(e.u\)的答案一定是\(e.r\). 删掉这条边, 并递归删除无出度的点和它连的边. 删除边\(e\)时, \(\mathrm{chkmin}(Ans_{e.u}, \max(e.r,Ans_{e.v}-e.p))\).

如果它不是唯一出边, 这条边一定不对答案造成影响, 直接删掉.

对于残余图重新进行这个操作即可. 注意唯一出边时用\(\mathrm{chkmin}\), 不要直接赋值, 因为可能再递归删除时得到了更小的答案.