ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

loj6068. 「2017 山东一轮集训 Day4」棋盘二分图，网络流

loj6068. 「2017 山东一轮集训 Day4」棋盘链接 https://loj.ac/problem/6068 思路上来没头绪，后来套算法，套了个网络流经典二分图左边横，右边列先重新算一下行和列，就是他们x相通的的算一个然后就去掉了障碍的作用然后每一行贡献是递增的(0,...

网络流二分图

2019-03-29

0 576

bzoj1133: [POI2009]Kon

bzoj1133: [POI2009]Kon 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1133 思路 f[i][k]表示前i个，选了k个，其中必选i的最大值 f[i][k]=f[j][k-1]+贡献这个贡献就是j到i之间的边界...

DP

2019-03-28

0 552

luogu3426 [POI2005]SZA-Template 后缀树

链接 bzoj不能auto https://www.luogu.org/problemnew/show/P3426 思路这个要求的串一定是S的前缀和S的后缀。转化一下建立出来fail树（fail[i]->i的树）答案就在0和n之间的链条上，且答案在分界点上(上面全不可以，下面全可...

fail树

2019-03-28

0 666

loj#2483. 「CEOI2017」Building Bridges 斜率优化 cdq分治

loj#2483. 「CEOI2017」Building Bridges 链接 https://loj.ac/problem/2483 思路 \[f[i]=f[j]+(h[i]-h[j])^2+(sum[i-1]-sum[j])\] \[f[i]=f[j]+h[i]^2+h[j]^2-2*h...

斜率优化 cdq

2019-03-22

0 506

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