ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

loj2353. 「NOI2007」货币兑换

loj2353. 「NOI2007」货币兑换链接 https://loj.ac/problem/2353 思路题目不重要，重要的是最后一句话提示必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。所以f[i]表示第i天最大收益...

cdq 斜率优化

2019-03-22

0 517

bzoj2124: 等差子序列线段树+hash

bzoj2124: 等差子序列线段树+hash 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2124 思路找大于3的等差数列其实就是找等于三的等差数列三个等差数列的话，枚举中间点。如果有对称点(a[i]-j,a[i]+j)在两...

线段树 hash

2019-03-15

0 533

luogu2046[NOI2010]海拔对偶图优化

luogu2046[NOI2010]海拔对偶图优化链接 https://www.luogu.org/problemnew/show/P2046 思路海拔一定是0或者1，而且会有一条01交错的分界线。转化为最小割，用对偶图优化求得。最小割论文写的特清楚。代码 #include &...

网络流最小割对偶图

2019-03-14

0 574

bzoj1001狼抓兔子对偶图优化

bzoj1001狼抓兔子对偶图优化链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1001 思路菜鸡总是要填坑的！很明显让你求网格图的最小割不过1000*1000明显不能跑dinic(虽然可以水过) 我们可以用对偶图来优化辣。...

网络流对偶图图论最短路

2019-03-14

0 553

bzoj1565: [NOI2009]植物大战僵尸最大权闭合子图，tarjan

bzoj1565: [NOI2009]植物大战僵尸链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1565 思路很容易的想到最大权闭合子图但这个图是有环的有环的地方当然是都过不去的地方显然他所保护的地方也是过不去的他保护的地...

最大权闭合子图 tarjan 网络流

2019-03-10

0 530

bzoj1497 [NOI2006]最大获利最大权闭合子图

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1497 思路最大权闭合子图的裸题一开始知道是这个最大权闭合子图(虽然我不知道名字)，但是我不理解所以还是去复习了一遍。 Orz 错误写读入优化的时候迷迷糊糊的多打了等号代码...

网络流最大权闭合子图

2019-03-09

0 478

bzoj1458: 士兵占领网络流

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1458 也可以去luogu 思路想成倒着删去点，使得依旧满足覆盖！！左边横，右边列，之间用点链接起来，流量1 S到i为之间总公共最多去掉m-h[i]-L[i]个，i到T同理。代码...

网络流

2019-03-09

0 501

SCOI2011 糖果

SCOI2011 糖果题目 https://loj.ac/problem/2436 思路直接查分约束建图，跑spfa 不过这题目***坑。要开long long(这个不吭) 卡spfa，真的是MMP。 S连边的时候倒着就OK了还有就是建边的时候判一判，要不然也会TLE MD我咋老是T...

查分约束卡常

2019-03-08

0 683

P1337 [JSOI2004]平衡点 / 吊打XXX 模拟退火

链接 https://www.luogu.org/problemnew/show/P1337 思路交了好多发，都是wrong 初始值取平均数就1A了真的是玄学的算法代码 // luogu-judger-enable-o2 #include <bits/stdc++.h> ...

模拟退火

2019-03-07

0 542

[POI2011]Garbage 欧拉回路

[POI2011]Garbage 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2278 https://loj.ac/problem/2162 https://www.luogu.org/problemnew/show/P3520 思...

欧拉回路未完成

2019-03-07

0 507