【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)$ 辣!