ComplexPug

未归档

做题记录(1)

/ 注册

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

# 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

3900: 交换茸角

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3900 思路状态压缩，f[i]表示只包含i中的所有元素的最小代价所有元素排序后两两配对都不能满足，就是inf 其他的，一定小于等于元素个数-1 orz wxy 收获 1，知道自己啥...

DP 状态压缩

2019-02-26

0 516

CF767C 记录错误

链接 https://codeforces.com/contest/767/problem/C 思路之所以把这个题放进来，是因为要记录错误情况不止一种所以答案存储就是>=2了代码 #include <iostream> #include <cstdio>...

DP

2019-02-26

0 417

bzoj2086: [Poi2010]Blocks DP，单调栈

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2086 思路这就有点妙了题目意思就是让你求平均数>=k的最长序列先求出a[i]-k的前缀和就是求sum[i]-sum[j]>=0的最大i-j 当\(j<=k&...

单调栈 DP

2019-02-24

0 482

bzoj1566: [NOI2009]管道取珠 DP

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1566 思路 n个球，第i个球颜色为ai，对于颜色j，对答案的贡献为颜色为j的球的个数的平方 k^2=(1+1+1+..+1)*(1+1++1+..+1) for (i=1; i<...

DP 转化

2019-02-24

0 556