OceanEye's Blog

是时候表演真正的技术了!

@OceanEye2月前

08/30
16:52
OI

BZOJ3832

思路清奇的一道题
首先有向图的最长链可以通过添加超级源超级汇,计算超级源超级汇之间的最长路来实现
如果仅仅如此并不足以做这道题
这道题还用了最小割的思想
看大佬题解吧……不是很清楚这题要怎么讲明白

大佬题解的传送门

\(S\) 为超级源
\(T\) 为超级汇
\(g[i] \) 为 \(S\) 到 \(i\) 的最长路
\(f[i] \) 为 \(i\) 到 \(T\) 的最长路
\( edge={ From,To } \)
令一条边存在的贡献为 \( g[From]+f[To]+1 \)
这是这条边对最长路的贡献
我们维护两个点集 \( A,B \) 。一开始 \( A \) 中只有S,其余点都在 \(B\) 中。
我们用数据结构来维护两个集合之间的连边,注意这是一定包括了所有能从S到T的路径的。每次我们按照昂拓扑序从B中拿点到A中,在这个过程中维护边集即可
令被移动的点为 \(x\)
那么我们需要先把从 \(A\) 到 \(x\) 的边全部删除,即删除 \(x\) 的所有入边 【为什么?我们之前用的是拓扑序啊不是吗】
完成统计后再将 \(x\) 到 \(B\) 的边全部加入即可
同时为了保证一个点在被删除后,两端的点依然有贡献,我们要在一开始加入 \(f[x]\)
后面点 \(x\) 从B移动到A后,我们要把 \(f[x]\) 删除,再将 \(g[x]\) 加入边集。
某次删点之后我们选出来的边的贡献值中最大的最小,那么这就是我们要求的答案
值的维护随便挑个数据结构就做了
难点是边的值要怎么去想到
【算了反正我也是看题解的记住这个思路就好了】

代码:

BZOJ3832

@OceanEye5月前

05/29
21:50
OI

BZOJ2597

T飞了……
前排膜拜PoPoQQQ大神的题解

反正我的SPFA费用流是T飞了……
估计因为不停的memset 一共 \( n^2 \) 次然后就炸了吧
:-(等我学个ZKW的姿势回来再切这道题

BZOJ2597

@OceanEye5月前

05/19
16:03
OI

BZOJ4869

这道题是这样子的……一个区间求和一个区间加幂

之前刚刚学了降幂大法就是为了写这道题:-D

然后就直接肝……当然最后还要展开多一层的1[EXM?]

 

BZOJ4869

@OceanEye6月前

04/27
09:59
OI

BZOJ4810 莫队+bitset

题目 链接 :http://www.lydsy.com/JudgeOnline/problem.php?id=4810

kry大爷的代码好短……可以看看orz

[bzoj 4810] [Ynoi2017]由乃的玉米田

这题目测只要是根号+压位就能过得去的了……所以不要太在意细节
[然后就被细节骗走了五次wa]
如果我们压了位……
减法就可以直接右移解决 b-c=a
加法的话把它反过来右移解决 大概是变成 a+b=c -> b-c=-a

乘法很simple,直接暴力就好了,根号可是比n/64要小的
而且时限30s,跑起来好像还挺稳的?
代码:

BZOJ4810 莫队+bitset