思路 1.记ans = INF 2.从任意点,用prim做最大生成树,记录最后一次加入到生成树中的点记为s,以及最后一次加入到生成树中的边记为e,记录e的另一端为t。 3.把与s节点相连的所有边权值相加记录为sum,去与ans取最小值更新ans 4.把s和t节点合并,若s和t都对r节点有边,合并后新的节点则是对r有重边。 5.回到步骤2,继续,直到只剩下了1个节点为止。 证明 定理1:sum就是上述的s和t的最小割。 证明 设与s相连的边分别是e1,e2,...,ene_1, e_2,...,e_ne​1​​,e​2​​,...,e​n​​,这些边的另一端分别为p1,p2,...,pnp_1, p_2, ..., p_np​1​​,p​2​​,...,p​n​​ 我们拿第一条边来举例子: 由于已经做了最大生成树,所以p1p_1p​1​​到ttt一定是可以通过最大生成树上的边到达的。 那么,考虑sss经过e1e_1e​1​​到达ttt,这条路径我们现在要让它断开。 可以分成两种情况,第一种情况是断开e1e_1e​1​​,第二种情况是断开p1p_1p​1​​与ttt不通过sss时的其他所有路径。 由于
acm
发表于 2017-08-08 10:01:23 | 条评论 | 阅读次数:85
KMP 扩展KMP AC自动机 Fail树 trie图 manacher 后缀平衡树 最小表示法 后缀数组 后缀自动机 复习傻逼考试,头皮发麻,不如总结一下常见的一些字符串算法啊。 KMP 我们这里主要是为了处理出NextNextNext数组和FailFailFail数组。 Fail[i]Fail[i]Fail[i]表示,第Fail[i]Fail[i]Fail[i]个前缀是第iii个前缀的后缀。所以如果下标是从000开始的,那么有Fail[0]=−1Fail[0]=-1Fail[0]=−1,即对于第iii个前缀,不存在一个前缀jjj,是前缀iii的后缀。 对于KMP的NextNextNext数组,有这样的性质:Next[i]=Fail[i]+1Next[i]=Fail[i]+1Next[i]=Fail[i]+1 int Next[MX];void getNext(char *S) { Next[0] = 0; int n = strlen(S), j = 0; //j表示当前要与i比较的位置 for(int i = 1; i < n; i++) {
acm
发表于 2017-06-09 19:42:12 | 条评论 | 阅读次数:228
由于题目标题都过于暴力,被强行改了一波题目名,不要在意这些细节。。 A.大新闻 B.黑框眼镜 C.华莱士 D.谈笑风生 E.图样 F.图森破 G.五点共圆 H.续一秒 I.一颗赛艇 J.真正的粉丝 A.大新闻 假设最后移动完后,紧挨着的平行x轴的线段的端点为(a,b),(a+n−1,b)(a, b),(a+n-1,b)(a,b),(a+n−1,b) 我们能够证明,如果刚开始两个人,X1<X2X_1 < X _2X​1​​<X​2​​, 那么移动位置后,第一个人的x坐标还是会小于第二个人的x坐标,因为交换两者的x大小关系只会导致总步数更多。 答案就等于∑i=1n∣Xi+(i−1)−a∣+∑i−1n∣Yi−b∣\sum_{i=1}^n|X_i+(i-1)-a| + \sum_{i-1}^n|Y_i-b|∑​i=1​n​​∣X​i​​+(i−1)−a∣+∑​i−1​n​​∣Y​i​​−b∣ 所以X和Y可以单独算贡献,把X和Y都单独排序一下。 对于Y,很显然b取Y的中位数时,会取最小值。 对于X,不是那么明显,如果我们令Xi=Xi+(i−1)X_i = X_i+(i - 1
acm
发表于 2017-06-02 00:53:59 | 条评论 | 阅读次数:361
5555,太堕落了,好久没有写博客了。 早就听说pb_ds这玩意了,有时候可以省很多东西。 好像最主要是为了替代set不能求第k大的问题。 感觉真的很方便啊~ //可并堆测试#include <ext/pb_ds/priority_queue.hpp>void ceshi_1() { //binary_heap_tag一般比std::priority_queue快 //pairing_heap_tag和std::priority_queue启发式合并时,速度差不多 __gnu_pbds::priority_queue<int, less<int>, __gnu_pbds::pairing_heap_tag> Q1, Q2; Q1.push(1); Q1.push(2); Q1.push(3); Q2.push(1); Q2.push(2); Q2.push(3); Q1.join(Q2);//pairing_heap_tag配对堆,zici O(1)合并 while(!Q1.empty()) { std::pr
发表于 2017-02-28 23:29:53 | 条评论 | 阅读次数:141
质数线性筛 O(1) gcd 可撤销的并查集 权值并查集 O(1)查询的lca 质数线性筛 复杂度:O(n)O(n)O(n) 以前没有深刻的理解这个,今天在看O(1)的gcd才发现这东西原来这么厉害。 每个数字只会被访问一次 每个合数可以拆分为 最小质数p*x 所以,我们要做到,筛数字的时候,只用那个最小的质数去筛,下面是代码: bool not_prime[MX];int prime[MX], prear;void prime_init() { prear = 0; not_prime[1] = 1; for(int i = 2; i < MX; i++) { if(!not_prime[i]) prime[++prear] = i; for(int j = 1; j <= prear && prime[j]*i < MX; j++) { not_prime[i * prime[j]] = 1; if(i % prime[j] == 0) break;
发表于 2017-02-13 18:22:41 | 条评论 | 阅读次数:367
Team Building Archery Training Shoot and kill Mr. Ant & His Problem The Chosen One How Many Answers Are Wrong Hill Climbing Drawing Circles is Fun Legen… Correct Bracket Sequence Editor Family Photos Racing Gems Factorial vs Power Menagerie Team Building 可以发现,可以考虑把两种年级合并成一种年级,那么问题就从3个年级变成了2个年级,然后考虑每次选人从一个年级选1人,另一个年级选2人。 之后很容易就能发现两个年级的做法。 #include <map>#include <set>#include <cmath>#include <ctime>#include <stack>#include <queue>#include <cstdio>
发表于 2017-02-13 14:14:40 | 条评论 | 阅读次数:111
并查集 简单图论概念 kruscal求最小生成树 并查集 基本作用:维护点之间的连通性,支持合并 通常用于一些点,然后可以把一些点和另一些点合并成一类,然后还能查询两个点是否连通。 引入问题 输入n,Q(1≤n,Q≤105)n,Q(1 \leq n,Q \leq 10^5)n,Q(1≤n,Q≤10​5​​),表示n个点,刚开始互相独立。 之后Q行,代表Q次操作。 1 u v,表示在u和v之间连接一条边 2 u v,表示查询,输出u是否和v通过边连通,连通输出YES反之输出NO 如果每次都去搜索,显然复杂度是承受不了的,我们考虑如何去优化 对于一个连通图,我们考虑用一棵有根树去表示它们的连通性。 用P[i]表示一棵树中,i的父节点为P[i],最刚开始时初始化P[i]=iP[i]=iP[i]=i 对操作1,我们就找到u节点所在的那棵树的根节点记为r1,以及找到v节点所在的那棵树的根节点记为r2。如下图1: r1等于r2时,表示现在u和v已经连通了,加了这条边对连通性没有任何影响,所以我们忽略这次操作。 如果r1不等于r2,我们就把P[r1]=r2P[r1]=r2P[r1]=r2当然也可以
发表于 2017-02-12 20:45:39 | 条评论 | 阅读次数:366
Copyright © 2017 - 2018 qwb's blog
blog.csustacm.com All Rights Reserved
Powered by qwb Contact me