【BZOJ 4195】[NOI2015] 程序自动分析

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4195

解题报告

用并查集将相同的变量缩起来
然后判有没有两个不等的变量在一个连通分量即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = 300009;

int n, fa[N], cet[M], val[N], dif[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

int main() {
	freopen("prog.in", "r", stdin);
	freopen("prog.out", "w", stdout);
	for (int T = read(); T; T--) {
		n = read();
		int tot = 0, cnt = 0, tt = 0;
		for (int i = 1; i <= n; i++) {
			cet[++tot] = val[++cnt] = read();
			cet[++tot] = val[++cnt] = read();
			cet[++tot] = read();
		}
		sort(val + 1, val + 1 + cnt);
		cnt = unique(val + 1, val + 1 + cnt) - val - 1;
		for (int i = 1; i <= cnt; i++) {
			fa[i] = i;
		}
		for (int i = 1; i <= n; i++) {
			int t = cet[tot--];
			int u = cet[tot--], v = cet[tot--];
			u = lower_bound(val + 1, val + 1 + cnt, u) - val;
			v = lower_bound(val + 1, val + 1 + cnt, v) - val;
			if (t == 1) {
				fa[find(u)] = find(v);
			} else {
				dif[++tt] = u;
				dif[++tt] = v;
			}
		}
		bool ok = 1;
		for (int i = 1; i <= tt; i += 2) {
			int u = dif[i], v = dif[i + 1];
			if (find(u) == find(v)) {
				ok = 0;
				break;
			}
		}
		puts(ok? "YES": "NO");
	}
	return 0;
}

【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4886
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

我们把权值看做点,矩形看作边
不难发现一个大小为$n$连通块如果是树,那么最多选$n-1$个点
否则可以选完$n$个点

所以用并查集维护一下连通性之后
直接贪心即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 500009;
  
int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N]; 
LL ans;
  
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
  
int find(int x) {
    return x == fa[x]? x: fa[x] = find(fa[x]);
}
  
int main() {
    n = read();
    for (int i=1;i<=n;i++) {
        u[i] = val[++tot] = read(); 
        v[i] = val[++tot] = read();
        ans += u[i];
        ans += v[i];
    }
    sort(val+1, val+1+tot);
    tot = unique(val+1, val+1+tot) - val - 1;
    for (int i=1;i<=tot;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
    for (int i=1;i<=n;i++) {
        int x = lower_bound(val+1, val+1+tot, u[i]) - val;
        int y = lower_bound(val+1, val+1+tot, v[i]) - val;
        if (find(x) != find(y)) {
            sz[fa[y]] += sz[fa[x]];
            if (cir[fa[x]]) {
                cir[fa[y]] = 1;
            }
            fa[fa[x]] = fa[y];
        } else {
            cir[fa[x]] = 1;
        }
    } 
    for (int i=1;i<=tot;i++) {
        if (find(i) == i) {
            sz[i] -= (cir[i] ^ 1);
        }
    }
    for (int i=1,w=1;i<=n;i++,w++) {
        while (sz[find(w)] == 0) ++w;
        ans -= val[w]; 
        sz[fa[w]]--;
    }
    printf("%lld\n",ans);
    return 0;
}

【BZOJ 4883】[Lydsy2017年5月月赛] 棋盘上的守卫

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4883
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

把行和列看成点,格子看成边
那么一个$n$个点的连通块需要$n$条边
于是用$Kruskal$做一个基环树森林就可以了
时间复杂度:$O(nm \log nm)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000;

struct Edge{
	int u, v, c;
	bool operator < (const Edge &ee) const {
		return c < ee.c;
	}
}e[N];
int n, m, tot, cir[N], fa[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			e[++tot].c = read();
			e[tot].u = i;
			e[tot].v = n + j;
		}
	}
	sort(e + 1, e + 1 + tot);
	for (int i = 1; i <= n + m; i++) {
		fa[i] = i;
	}
	LL ans = 0;
	for (int i = 1; i <= tot; i++) {
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (cir[fu] && cir[fv]) {
			continue;
		} else if (fu != fv) {
			fa[fv] = fu;
			cir[fu] |= cir[fv];
		} else if (!cir[fu]) {
			cir[fu] = 1;
		}
		ans += e[i].c;
	}
	printf("%lld\n", ans);
	return 0;
}

【CodeChef PARITREE】[MARCH16] Parity tree

相关链接

题目传送门:https://www.codechef.com/MARCH16/problems/PARITREE
神犇题解:http://r64.is-programmer.com/posts/197030.html

解题报告

这题大概是PA2014 Kuglarz的升级版
我们发现其给定树上一条路径的奇偶性,实际上可以理解为给定路径上两个端点到根的路径的奇偶性的关系
换一句话来说,这两个的奇偶性定了一个,另一个也就确定了

所以给定$u,v$的奇偶性,就用并查集把这两货连一起
最后假设有$k$个连通块,那答案就是$2^k$
当然我们还需要特判一下无解的情况,在并查集那里多记录一点东西就可以了

【HDU 5575】Discover Water Tank

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5575
神犇题解:http://blog.csdn.net/qq_19592437/article/details/50252111
中文题面:https://ly.men.ci/problem/199

解题报告

这题我们可以用左偏树+并查集什么的
不过感觉分治更好写吧?

考虑$solve(l,r)$表示区间$(l,r]$的最优解
那么找出其中最高的挡板设为$x$,之后分两种情况讨论

  1. 区间水位低于$x$,那么我们分治$solve(l,x-1)+solve(x+1,r)$即可
  2. 区间水位高于$x$,那么我们搞一个前缀和就好

总的时间复杂度:$O(n \log n)$

【BZOJ 2001】[HNOI2010] City 城市建设

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2001
神犇题解Ⅰ:http://www.cnblogs.com/BLADEVIL/p/3512644.html
神犇题解Ⅱ:http://blog.miskcoo.com/2015/04/bzoj-2001

解题报告

如果没有边权,只需要维护连通性
那么搞一个可以撤销的并查集就可以啦!

现在考虑带边权的情况,我们仍然对时间进行分治
在每一层,我们进行两个操作:

1. Contraction 缩小点的规模

将所有当前分治区间内会被修改的边的边权置为 $-INF$
然后做一遍MST,将此时通过非 $-INF$ 连接的点用并查集缩起来
因为$-INF$边只会有区间长度个,所以每一次分治后,点的规模不会超过分治区间的长度

2. Reduction 缩小边的规模

将会被修改的边的边权置为 $INF$,然后再做一遍MST
将此时不在MST中的边删去,因为保留的边数不会超过点数,所以边的规模也不会超过分治区间的长度

所以时间复杂度写出来长这样: $T(n) = 2T(\frac{n}{2}) + n\log n$
用主定理化简之后,时间复杂度就是: $O(n{\log ^2}n)$

【BZOJ 4358】permu

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4358
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5049090.html
神犇题解Ⅱ:http://www.cnblogs.com/czllgzmzl/p/5644724.html

解题报告

1. 莫队+并查集

首先我们考虑一个简化版本:搞一个莫队,然后搞一个值域线段树
这样的话,我们的复杂度就是 $O({n^{1.5}}logn)$ 的,虽然可能会T,但很好想
现在考虑怎么把$log$去掉:如果莫队那里只存在插入操作,那么我们就可以使用并查集来维护
于是考虑莫队那里只有左端点的移动那里会有删除操作,于是我们每一次把左端点块内那一部分拿出来暴力重构
这样的话,复杂度就神奇地少了一个$log$!总复杂度: $O(n\sqrt n \alpha (n))$ 感觉可以A地样子!

2. KD-Tree

这里就是本题的高能部分!简直是太神啦!_(:з」∠)_
考虑将询问化为二维上的点,然后我们按照点值的大小,将序列的位置一个一个插入
每一次把所有包含他的询问的计数器加一,其他的询问的计数器置零
于是我们的每个询问对应的点上的计数器的历史最大值就是这个询问的答案啦!
时间复杂度:$O(n \sqrt n)$

【BZOJ 4423】[AMPPZ2013] Bytehattan

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4423
神犇题解:http://medalplus.com/?p=2428

解题报告

这个算是套路题吧?
考虑对偶图,两点之间不联通
当且仅当,一个点周围的空白部分全部联通

于是我们转成对偶图之后,用并查集判一判连通性就好
具体来说:删除一条边之前,如果该边相邻的空白区域已经联通则删除该边后两端点不联通
否则不影响连通性

【BZOJ 4537】[HNOI2016] 最小公倍数

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4537
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5406018.html
神犇题解Ⅱ:http://blog.csdn.net/heheda_is_an_oier/article/details/51197705

解题报告

考虑只有 ${{\rm{2}}^a}$ 的限制的话
只需要将边和询问排序后依次执行就可以了
具体的话,就是判一判在不在同一个连通块和连通块内的最大值是否符合条件

现在有两个限制,且独立不了的话
那么考虑将 $a$ 分块
边和询问按照 $a$ 所在的块为第一关键字,$b$ 为第二关键字
于是单次询问的加边数量就在 $\sqrt m $ 级别了
于是再搞一个持久化并查集什么的,遇到操作就暴力插入、还原
于是复杂度就是 $O({m^{1.5}}\log n)$ 辣!

【BZOJ 4662】Snow

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4662
神犇题解:http://www.cnblogs.com/ccz181078/p/6291464.html

解题报告

想了两个小时没有想出来
一看题解,居然是姿势优雅的暴力

考虑最开始的区间一定是长这样的

删掉正中间的那个区间之后就变成了这样

发现蓝色框住的区间右端点相同了,绿色框住的区间左端点相同了!
于是两个椭圆框住的区间以后就可以进行区间维护了,不用再一个一个改
复杂度的话,因为暴力修改会进行 $ O(n)$ 次,所以单次修改操作的均摊复杂度为 $ O(\log n)$

具体实现上的话,用线段树支持区间操作
再用一个并查集搞一搞,右端点/左端点相同了就并一起
修改就暴力再并查集上爬一爬就好啦!

【BZOJ 4551】[TJOI2016&HEOI2016] 树

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4551
双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=3319
神犇题解:http://medalplus.com/?p=1685

题解

  1. 强制在线做法 O(nlogn)
    考虑每一次标记点:只会影响其子树中的点
    所以使用DFS序+线段树就可以辣!

  2. 离线做法 O(nlogn)
    考虑将每一次标记的时间记录到点上
    然后使用倍增LCA的思想向上倍增

  3. 离线做法 O(nα(n))
    考虑离线之后进行逆序操作
    这样的话,操作就变成了删除标记
    这个可以形象地想成:打通了向上走地道路
    于是使用并查集即可
    ps:和BZOJ_3319是一毛一样的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;

int head[N],to[N],nxt[N],anc[N],fa[N];
int n,m,tot,opt[N],tag[N],vout[N];
char pat[10];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int find(int w) {
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

void DFS(int w, int last) {
	if (tag[w]) last = fa[w] = w;
	else fa[w] = last;
	for (int i=head[w];i;i=nxt[i]) {
		anc[to[i]] = w;
		DFS(to[i],last);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u,v);
	}
	for (int i=1;i<=m;i++) {
		scanf("%s",pat+1);
		opt[i] = read(); 
		if (pat[1] == 'C') tag[opt[i]]++;
		else opt[i] *= -1;
	}
	tag[1]++; DFS(1,1);
	for (int i=m;i;i--) {
		if (opt[i] > 0) {
			if (!(--tag[opt[i]])) {
				fa[opt[i]] = anc[opt[i]];
			}
		} else {
			vout[++tot] = find(-opt[i]);
		}
	}
	while (tot) printf("%d\n",vout[tot--]); 
	return 0;
}

【BZOJ 3714】[PA2014] Kuglarz

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3714

首先我们可以得到一个结论:如果知道了每一个点的前缀和,那么我们就知道了答案
其次我们又可以知道:假如我们知道了sum(i-j)那么这两个点的前缀和可以知二推一
换一句话来说,第i个点和第j个点结合了起来
考虑什么时候可以得出答案:当所有点的前缀和都结合起来以后
然后就成了求一个最小生成树辣!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000+9;
const int M = N * N;

int n,m,fa[N]; LL vout;
struct Edge{
	int u,v,w;
	inline bool operator < (const Edge &B) const {
		return w < B.w;
	}
}edge[M];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int find(int w) {
	int f = fa[w], tmp;;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f; 
}

int main(){
	n = read();
	for (int i=1;i<=n+1;i++) {
		fa[i] = i;
	}	
	for (int j=1;j<=n;j++) {
		for (int i=j;i<=n;i++) {
			edge[++m].u = j;
			edge[m].v = i + 1;
			edge[m].w = read();
		}
	}
	sort(edge+1,edge+1+m);
	for (int i=1;i<=m;i++) {
		if (find(edge[i].u) != find(edge[i].v)) {
			fa[fa[edge[i].u]] = fa[edge[i].v];
			vout += edge[i].w;
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 4569】[SCOI2016] 萌萌哒

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4569

这题,出题人是怎么想到的QAQ
真心服 Orz

考虑网络流的区间建边的方法:先搞出一个像线段树的玩意
然而这个题目没办法了,因为线段树的区间拆分是不规则的,对不上 QAQ
于是考虑ST表,用ST表来搞一搞,其实是用来去掉区间合并中的重复部分

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int MOD = 1000000007;

int n,m,fa[18][N],vout=1;

inline int find(int p, int w) {
	int f = fa[p][w], tmp;
	while (f != fa[p][f]) f = fa[p][f];
	while (w != f) tmp = fa[p][w], fa[p][w] = f, w = tmp;
	return f;
} 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void merge(int t, int a, int b){
	int t1 = find(t,a), t2 = find(t, b);
	if (t1 == t2) return; fa[t][t1] = t2;
	if (!t) return; t--, merge(t,a,b), merge(t,a+(1<<t),b+(1<<t));
}

int main(){
	n = read(); m = read(); if (n == 1) return puts("10"), 0;
	for (int j=0;j<=17;j++) for (int i=1;i<=n;i++) fa[j][i] = i;
	for (int i=1,a,b,c,d,stp;i<=m;i++) 
		a = read(), b = read(), c = read(), d = read(), stp = 31 - __builtin_clz(b-a+1),
		merge(stp,a,c), merge(stp,b-(1<<stp)+1,d-(1<<stp)+1);
	for (int i=1,tag=1;i<=n;i++) if (find(0,i) == i) vout = vout*(tag?9LL:10LL) % MOD, tag = 0;
	return printf("%d\n",vout), 0; 
}

另外说到压代码这个事,Claris我是真心服 (:зゝ∠)
545646454
第一眼看上去,还以为只有主要的函数QAQ
再次 Orz

【POJ 3522】Slim Span

题目传送门:http://poj.org/problem?id=3522

今天在水位运算生成树,无聊来水一水
很暴力,枚举最大边,然后搞一搞,并查集判树

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100+9;
const int M = 10000+9;
const int INF = 1000000000;

struct Edge{int u,v,w;}e[M];
int n,m,vout,fa[N];

inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline int Get_Ans(int lim){
	for (int i=1;i<=n;i++) fa[i] = i;
	fa[e[lim].u] = fa[e[lim].v];
	for (int i=lim-1,t=n-2,f1,f2;i;i--) {
		f1 = find(e[i].u); f2 = find(e[i].v);
		if (f1 != f2) fa[f2] = f1, t--;
		if (!t) return e[i].w;
	}
	return -INF;
}

int main(){
	while (scanf("%d%d",&n,&m) && (n||m)) {
		for (int i=1;i<=m;i++) e[i].u = read(), e[i].v = read(), e[i].w = read();
		sort(e+1,e+1+m); vout = INF;
		for (int lim=m;lim>=n-1;lim--) 
			vout = min(vout, e[lim].w - Get_Ans(lim));
		if (n <= 2) printf("0\n");
		else printf("%d\n",vout>=INF?-1:vout);	
	}
	return 0;
}