ComplexPug

分类

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

/ 注册

全部文章（共277篇）

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

# bzoj2215: [Poi2011]Conspiracy 2-sat

bzoj2215: [Poi2011]Conspiracy 2-sat 链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2215 思路一个点的属性为去当同谋者和后勤两种求出一种方案来很简单(只需要用简单的2-sat) 我们发现一条特...

2-sat

2019-03-07

0 511

hdu1814 Peaceful Commission 2-sat

hdu1814 Peaceful Commission 链接 emm，三个链接，三个都不同 loj随便做 hdu字典序最小 bzoj求合法方案数思路 loj是任意一组解，直接跑tarjan然后判。 hdu是求最小字典序的2-sat解，真的是码力弱的要死呀。只有O(N*M)的dfs复杂度能...

2-sat

2019-03-03

0 606

2-sat相关复习

2-sat相关复习 noi曾经考过，谁能说得准呢 sat问题通俗的sat问题表述一般是这样的：有很多个集合，每个集合里面有若干元素，现给出一些取元素的规则，要你判断是否可行，可行则给出一个可行方案。如果所有集合中，元素个数最多的集合有k个，那么我们就说这是一个k-sat问题。 k-sat是N...

2-sat

2019-03-03

0 542

#2718. 「NOI2018」归程 kruskal重构树

链接 https://loj.ac/problem/2718 思路我们希望x所在的连通块尽量的大，而且尽量走高处离线的话可以询问排序，kruskal过程中更新答案在线就要用kruskal重构树这kruskal重构树的话，看图就明白了叶子节点都是原树节点非叶子节点都是边按照从大到小...

kruskal重构树并查集树链剖分二分

2019-03-02

0 550

JXOI2018守卫区间DP

链接 https://loj.ac/problem/2545 思路 f[i][j]表示i到j区间的最小监视人数可以预处理出来g[i][j],表示i能否监视到j (其实预处理的关系不大，完全可以直接判断,不过比较不能加=) 一个区间\([l,r]\)，一定会选r，显然然后只要管r不能监视的地...

DP 区间DP

2019-02-28

0 560

[NOI1995]石子合并四边形不等式优化

链接 https://www.luogu.org/problemnew/show/P1880 思路总之就是很牛逼的四边形不等式优化复杂度\(O(n^2)\) 代码 #include <iostream> #include <cstdio> #include &l...

四边形不等式优化 DP

2019-02-26

0 550