JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj3894]文理分科_网络流_最小割

文理分科 bzoj-3894 题目大意：题目链接。注释：略。想法：这种题也是一种套路。我们新建一个点表示收益点。然后把所有的收益都加一起，求最小割表示代价即可。 Code： #include <bits/stdc++.h> #define inf 0x...

2019-01-09

0 471

[bzoj2229][Zjoi2011]最小割_网络流_最小割树

最小割 bzoj-2229 Zjoi-2011 题目大意：题目链接。注释：略。想法：在这里给出最小割树的定义。最小割树啊，就是这样一棵树。一个图的最小割树满足这棵树上任意两点之间的最小值就是原图中这两点之间的最小割。这个性质显然是非常优秀的。我们不妨这样假设，我么已经把...

2019-01-09

0 436

[bzoj2561]最小生成树_网络流_最小割_最小生成树

最小生成树 bzoj-2561 题目大意；题目链接。注释：略。想法：我们发现：如果一条权值为$L$的边想加入到最小生成树上的话，需要满足一下条件。就是求出原图的最小生成树之后，这个边当做非树边的情况下覆盖的边的最小值不可以比$L$小。如此，我们级就可以通过网络流来求了。...

2019-01-09

0 475

[bzoj3630][JLOI2014]镜面通道_计算几何_网络流_最小割

镜面通道 bzoj-3630 JLOI-2014 题目大意：题目链接。注释：略。想法：我们发现，只要上下界没有被完全封死，我们就一定有一条合法的光路。所以只需要将上界和下界拆开即可。拆点，把每个点分为入点和出点，入点向出点连1的边。元件之间如果连通就连$inf$。和...

2019-01-09

0 420

[bzoj1324]Exca王者之剑_最小割

Exca王者之剑 bzoj-1324 题目大意：题目链接。注释：略。想法：最小割经典模型。所有格子向源点连权值为格子权值的边。将棋盘黑白染色后白点反转源汇。如果两个格子相邻那么黑点向白点连$inf$的有向边。求最小割即可。开始把所有点的权值都加上，如果被割掉那么...

2019-01-09

0 420

[bzoj3489]A simple rmq problem_KD-Tree

A simple rmq problem 题目大意：给定一个长度为$n$的序列，给出$m$个询问：在$[l,r]$之间找到一个在这个区间里只出现过一次的最大的数。注释：$1\le n\le 10^5$，$1\le mle 2\cdot 10^5$。想法：我的第一想法是莫队。结果...

2019-01-09

0 497

[bzoj1934/2768][Shoi2007]Vote 善意的投票_最小割

Vote 善意的投票 bzoj-1934 Shoi-2007 题目大意：题目链接。注释：略。想法：这是最小割的一个比较基本的模型。我们将所有当前同意的小朋友连向源点，边权为1。不容易的连向汇点，边权为1。如果两个小朋友是好朋友那就把他们之间连一条边权为1的无向边即可。最...

2019-01-08

0 443

[bzoj4520][Cqoi2016]K远点对_KD-Tree_堆

K远点对 bzoj-4520 Cqoi-2016 题目大意：已知平面内 N 个点的坐标，求欧氏距离下的第 K 远点对。注释：$1\le n\le 10^5$，$1\le k\le 100$，$k\le n*(n-1)/2$，$0\le x,y<2^{31}$。想法： KD-Tr...

2019-01-08

0 411

[bzoj4826][Hnoi2017]影魔_单调栈_主席树

影魔 bzoj-4826 Hnoi-2017 题目大意：给定一个$n$个数的序列$a$，求满足一下情况的点对个数：注释：$1\le n,m\le 2\cdot 10^5$，$1\le p1,p2\le 1000$。想法：我们先用单调栈求出一个数左边第一个比它大的，和右边第一个比它大...

2019-01-08

0 350

[bzoj4994][Usaco2017 Feb]Why Did the Cow Cross the Road III_树状数组

Why Did the Cow Cross the Road III bzoj-4994 Usaco-2017 Feb 题目大意：给定一个长度为$2n$的序列，$1$~$n$个出现过两次，$i$第一次出现的位置记为$a_i$，第二次记为$b_i$，求满足$a_i<a_j<b_i<...

2019-01-08

0 451