Panda2134's Blog

Not only coding

ISAP算法学习笔记

ISAP，即改进的SAP算法。算法基于：如果每次在残量网络中从汇点开始反向BFS， s-t 距离是单调不减的。流程如下：首先用BFS从汇点出发计算每个点到汇点的距离标号。 Advance: 每次走满足 $d_v = d_u - 1$ 的路径，即走最短路。维护每个点的当前弧。（实践证明，只有ISAP需要当前弧优化……原始对偶加了之后反而更慢……Dinic加了之后有时候快很多...

Posted by panda_2134 on March 7, 2018

[SCOI2012]奇怪的游戏

BZOJ2756 题意给出一个 $n \times m$ 的矩阵，初始每个格子有一个正整数。每次可以给相邻两个格子加1，求最少操作多少次使得矩阵里面数字相同。思路就差一点点就想出来了QAQ 先转化为判定性问题。显然我们可以把“+1”的操作看成网络流的增广操作，黑白染色后建图。设每个格子都变成了 $x$ ，连s->黑点边，容量 $x-w_{ij}$ ；白点->t...

Posted by panda_2134 on March 6, 2018

[NOI2010]海拔

链接：bzoj2007 思路经过思考可以发现2个结论：选0/1外的值作为海拔没有必要小于0的值改为0，大于1的值改为1，答案不会更差。对(0, 1)之间的值，不如选0/1更优。海拔为0/1的分别只有一个连通块如果1有≥2个连通块，把不包含(n, n)的连通块拍扁，答案不会更差。 ...

Posted by panda_2134 on March 6, 2018

[BZOJ2893]征服王

链接：BZOJ2893 题意给定一个有向图，以及每次行走的起点终点集合。每次只能在起点集合开始，终点集合结束。求最少多少次行走可以覆盖每个节点。思路先吐槽下白学家出题人…… 不过话说回来，这个题还是很好的。至少暴露了我对上下界网络流理解的几个问题。首先我看到这个题，就想到了[AHOI2014]支线剧情。当时的思路如下：每个点拆成2个，赋节点流量下界1，上...

Posted by panda_2134 on March 2, 2018

网络流常见建模总结

自己对最近网络流学习的一些整理和理解…… 如果有什么错误，请立即纠正，非常感谢。这边Blog的排版估计很渣……我懒得管了，丢个 $\LaTeX$ 版的吧……戳我 UPD:发现洛谷上面的网络流题目严重不全……这么多年省选也不会只考了10道网络流啊……翻了翻hzwer的博客，屯了40几题，准备先用一个星期做个二十几道，剩下的边练DP边带着做我已经做了 8 题 ✅bzoj4...

Posted by panda_2134 on February 26, 2018

[NOI2016] 旷野大计算

UOJ-224 神题。扑通一声跪下来，千古神犇vfk。早就听说了这个造计算机题。正好，前几天上洛谷的省选课，这个题目作为提答作业布置了下来。于是我就开始了我的愉快作死之旅啦~ 自己xjb乱搞，搞了56pts，发现不会做了XD 于是参考了chrt的题解和vfleaking的slide，各种卡，终于拿到了95pts… 未完待续工具按照vfk的题解的说法，题目中给出...

Posted by panda_2134 on February 19, 2018

省选计划

古人之观于天地、山川、草木、虫鱼、鸟兽，往往有得，以其求思之深而无不在也。夫夷以近，则游者众；险以远，则至者少。而世之奇伟、瑰怪，非常之观，常在于险远，而人之所罕至焉，故非有志者不能至也。有志矣，不随以止也，然力不足者，亦不能至也。有志与力，而又不随以怠，至于幽暗昏惑而无物以相之，亦不能至也。然力足以至焉，于人为可讥，而在己为有悔；尽吾志也而不能至者，可以无悔矣，其孰能讥之乎？此余之所...

Posted by panda_2134 on February 12, 2018

[NOI2009]变换序列

链接：Luogu-P1963 思路这个题目可以看出你真正理解了匈牙利算法没有。首先我们可以建立二分图的模型：每个位置可以有2种取值，于是我们把位置作为左边的点，取值作为右边的点。然后进行二分图匹配，只要有完美匹配，完美匹配就是一个可行解。再考虑题面中最优性的要求。对于字典序问题，我们常常按照字典序枚举。于是这里也可以枚举：从上往下枚举左边的点，按照字典序枚举和右边的哪个点匹配...

Posted by panda_2134 on January 22, 2018

NOIP2017游记

考完NOIP已经2个月了，也是时候写个游记了。考前还是得从NOIP2016讲起。去年NOIP，我啥都不会，然后原地爆炸，赛场上调试3个小时线段树导致day2差点爆零。由于去年NOIP炸飞的缘故，在NOIP2017之前我基本没学什么超出“暴力、DP、图论基础”之外的算法，只是想把基础的东西学好。确切地说，去年NOIP之后很长一段时间我都几乎失去了OI的信心，大致说来，整个高一都投入...

Posted by panda_2134 on January 20, 2018

[NOI2014]魔法森林

链接：Luogu-P2387 这是我做的第一道非模板LCT题目……自己并没有想出来，看题解也看了好久，于是总结下做这个题目的思路。题意给出一个$n$个点，$m$条边的无向图，每条边都有权值$a_i,b_i$，求一条从点$1$到点$n$的路径，使得这条路径上边的$a_i,b_i$最大值之和最小。$2 \leq n \leq 5 \times 10^4, 0 \leq m \leq 1...

Posted by panda_2134 on January 18, 2018