【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

【Timus 1099】Work Scheduling

题目传送门:http://acm.timus.ru/problem.aspx?space=1&num=1099
离线版题目:http://paste.ubuntu.com/19164744/

一般图匹配的板题
然而抄范大神的代码抄错了,调了一个下午QAQ
详细情况见之后的博文吧,会单独写一篇算法笔记的

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

const int MAXN = 1000000;

int n,match[MAXN],fa[MAXN],que[MAXN],fro,bak;
int next[MAXN],mark[MAXN],vis[MAXN];
int T,nxt[MAXN],head[MAXN],to[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 merge(int a, int b){
	int f1 = find(a), f2 = find(b);
	if (f1 != f2) fa[f1] = f2;
}

inline int LCA(int x, int y){
	static int t = 0; t++;
	while (true){
		if (x) {
			x = find(x);
			if (vis[x] == t) return x;
			else {
				vis[x] = t;
				x = next[match[x]];
			}
		} swap(x, y);
	}
}

inline void gather(int a, int p){
	while (a != p){
		int b = match[a], c = next[b];
		if (find(c) != p) next = b;
		if (mark[b] == 2) mark[que[++fro]=b] = 1;
		if (mark == 2) mark[que[++fro]=c] = 1;
		merge(a, b); merge(b, c);
		a = c;
	}
}

inline void Augment(int s){
	for (int i=1;i<=n;i++) next[i]=mark[i]=vis[i]=0, fa[i]=i;
	mark[s] = 1; que[fro=bak=1] = s; 
	while (bak <= fro) {
		int w = que[bak++];
		for (int i=head[w];i;i=nxt[i]){
			if (match[w] == to[i]) continue;
			else if (find(to[i]) == find(w)) continue;
			else if (mark[to[i]] == 2) continue;
			else if (mark[to[i]] == 1) {
				int lca = LCA(w, to[i]);
				if (find(w) != lca) next[w] = to[i];
				if (find(to[i]) != lca) next[to[i]] = w;
				gather(w, lca);
				gather(to[i], lca);
			} else if (!match[to[i]]) {
				next[to[i]] = w;
				for (int u=to[i]; u; ) {
					int v = next[u];
					int fv = match[v];
					match[v] = u; match[u] = v;
					u = fv;
				}
				return;
			} else {
				next[to[i]] = w;
				mark[que[++fro] = match[to[i]]] = 1;
				mark[to[i]] = 2; 
			}
		}
	}
}

inline void AddEdge(int a, int b){
	to[++T] = b; nxt[T] = head[a]; head[a] = T;
	to[++T] = a; nxt[T] = head[b]; head[b] = T;
}

int main(){
	scanf("%d",&n); int a,b;
	while (~scanf("%d%d",&a,&b)) AddEdge(a, b);
	for (int i=1;i<=n;i++) if (!match[i]) Augment(i);
	
	int vout = 0;
	for (int i=1;i<=n;i++) if (match[i]) vout++;
	printf("%d\n",vout);
	for (int i=1;i<=n;i++) if (match[i] > i) printf("%d %d\n",i,match[i]);
	return 0;
}

另外,此题有坑QAQ
边数巨多,TM还不告诉你是RE,给你说的是TLEQAQ

【日常小测】再次挑战NPC

题目传送门:http://oi.cyo.ng/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;
}