【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 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;
}

【CDOJ 79】Playground

题目传送门:http://www.acm.uestc.edu.cn/#/problem/show/79
数据生成器:http://paste.ubuntu.com/18848244/

这个题,并查集搞一搞就过了。
然而后来得知一种二分图匹配的思路,感觉很科学,叉不掉。于是写了写代码。
最后发现,二分图匹配的话,只能保证在满足限制的情况下,得出最少解,并不能保证全部染完,比如十字架

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

const int MAXN = 500;

int fa[MAXN],n,tag[MAXN],vout,que[MAXN],mat[MAXN][MAXN];

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

inline void connect(int a, int b){
	int f1 = find(a), f2 = find(b);
	if (f2 != f1) fa[f2] = f1;
}	

inline void solve(int sta){
	int tot = 0, ret = 0;
	for (int i=1;i<=n*2;i++)
		if (fa[i] == sta)
			que[++tot] = i;
	for (int i=1;i<=tot;i++) if (tag[que[i]]){
		int w = que[i]; ret++;
		if (w <= n){ 
			for (int j=1;j<=n;j++)
				if (mat[w][j]) tag[n+j] = 0;
		} else {
			for (int j=1;j<=n;j++)
				if (mat[j][w-n]) tag[j] = 0;
		}
	}
	vout += min(ret, tot-ret);
}

int main(){
	int T; cin>>T;
	while (T--){
		scanf("%d",&n); vout = 0;
		for (int i=1;i<=2*n;i++) fa[i] = i;
		for (int j=1,tmp;j<=n;j++){
			for (int i=1;i<=n;i++){
				scanf("%d",&tmp);
				mat[i][j] = tmp;
				if (tmp == 1) 
					connect(i,j+n), 
					tag[i] = tag[j+n] = 1;
			}
		}	
		for (int i=1;i<=n*2;i++) fa[i] = find(i);
		for (int i=1;i<=n*2;i++) if (fa[i]==i & tag[i])
			solve(fa[i]);
		printf("%d\n",vout);
	}	
	return 0;
} 

【日常小测】再次挑战NPC

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/06/water_meeting.pdf

一看这题,TM这不今年wc的T1吗?哎呀,还是不会带花树QAQ,哎呀冬令营的时候网络流搞了40分,那就来写网络流吧!
于是开始骚写网络流。 然后写完了发现过不了样例QAQ 然后想了几分钟突然发现:
如果只考虑奇偶的话,这个一个联通块里不最多只有一个半空的筐QAQ
于是最后写了一个并查集。 后来问一问,发现带花树也是可以的,但是只有80分(╯-_-)╯╧╧

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;

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

const int MAXN = 400000;
const int INF = 100000000;

int n,m,A[MAXN],B[MAXN],bot[MAXN];
int vout,fa[MAXN],sum[MAXN],str[MAXN];
int Q[MAXN],cnt;

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

inline void connect(int b, int a){
	int f1=find(a),f2=find(b);
	if (f1 != f2) fa[f1] = f2;
}

int main(){
	freopen("cpn.in","r",stdin);
	freopen("cpn.out","w",stdout);
	n = read(); m = read();
	for (int i=1;i<=m;i++) fa[i] = i;
	for (int i=1;i<=n;i++){ 
		A[i] = read(); B[i] = read();
		bot[A[i]]++; connect(A[i],B[i]);
	}	
	for (int i=1;i<=m;i++) find(i);
	for (int i=1;i<=m;i++) if (bot[i]%2)
		{sum[fa[i]]++; str[fa[i]] = i;}
	for (int i=1;i<=m;i++) if (sum[i]%2)
		{vout++; Q[++cnt]=str[i];}
	 
	printf("%d\n",vout);
	for (int i=1;i<=cnt;i++)
		printf("%d\n",Q[i]);
	
	return 0;
} 

【BZOJ 3325】[Scoi2013] 密码

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3325
离线版题目:http://paste.ubuntu.com/18029355/
数据生成器:http://paste.ubuntu.com/18029394/

最近都在做字符串,所以接触了一点逆向字符串的题目,于是这题就会做啦!
这类给你字符串结构的过程数组,叫你统计方案数/构造符合要求的字符串,说到底就是给了你一堆字符等与不等的关系
而你就需要根据具体数据结构的特点来处理这些关系
比如说这道题,我上周六想了半个小时,一点思路都没有,觉得提供的关系可能是O(n^2)的。
但今天再来想的时候发现,相等关系可以用和manacher时间复杂度一样的整法证到时O(n)的
而不等关系很明显是O(n)的,于是保存好关系,并查集缩一缩点就搞好啦!
基本上1A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*

#include<iostream>
#include<cstdio>
#include<set>
#define SITR set<int>::iterator
using namespace std;

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

const int MAXN = 100000+9;
const int SIGMA_SIZE = 26;

int ld[MAXN],lo[MAXN],fa[MAXN];
int n,mx=1,vout[MAXN],col[MAXN];
set<int> Q[MAXN];

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 connect(int a, int b){
	int f1=find(a), f2=find(b);
	if (f1 != f2) fa[f1] = f2;
}

inline void discon(int a, int b){
	Q[fa[a]].insert(fa[b]);
	Q[fa[b]].insert(fa[a]);
}

int main(){
	n = read(); 
	for (int i=1;i<=n;i++) fa[i] = i; 
	for (int i=1;i<=n;i++) ld[i] = (read()-1)/2;
	for (int i=1;i<n;i++)  lo[i] = read()/2;
	
	for (int i=1;i<=n;i++){
		for (int j=max(mx-i+1,1);j<=ld[i];j++)
			connect(i+j,i-j);	
		mx = max(mx, i+ld[i]);
		
		for (int j=max(mx-i+1,1);j<=lo[i];j++)
			connect(i+j,i-j+1);		
		mx = max(mx, i+lo[i]);
	}
	for (int i=1;i<=n;i++)  fa[i]=find(i);
	for (int i=1;i<=n;i++){ if (i-ld[i] > 1 && i+ld[i] < n) discon(i+ld[i]+1,i-ld[i]-1); if (i-lo[i] > 0 && i+lo[i] < n) 
			discon(i+lo[i]+1,i-lo[i]);
	}
	
	for (int i=1;i<=n;i++){
		if (vout[fa[i]]) continue;
		else {
			for (SITR j=Q[fa[i]].begin();j!=Q[fa[i]].end();j++)
				col[vout[*j]] = i;
			for (int j=1;j<=SIGMA_SIZE;j++)
				if (col[j] < i) {vout[fa[i]] = j; break;}
		}
	}
	
	for (int i=1;i<=n;i++) putchar(vout[fa[i]]+'a'-1);
	
	return 0;
}