【Codeforces 797D】Broken BST

相关链接

题目传送门:http://codeforces.com/contest/797/problem/D

解题报告

之前做过类似的题:https://oi.qizy.tech/?p=298
大概就是说,排序之后,每个点的左右子树切换至多发生一次
于是用基排来离散化的话,时间复杂度就是:$O(n)$的

Code

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

const int N = 200009;

int n,rt,is_rt[N],val[N],ch[N][2],TOT[N];
int tot,_hash[N],cnt[N],dep[N],vout;
set<pair<int,int> > id[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;
}

void dfs(int w, int f) {
	dep[w] = dep[f] + 1;
	if (ch[w][1]) dfs(ch[w][1], w);
	if (ch[w][0]) dfs(ch[w][0], w);
}

void add(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].insert(make_pair(dep[w], w)); 
	cnt[val[w]]++;
	if (val[w] > sta) add(ch[w][0], sta);
	else add(ch[w][1], sta);
}

void del(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].erase(make_pair(dep[w], w));
	cnt[val[w]]--;
	if (val[w] > sta) del(ch[w][0], sta);
	else del(ch[w][1], sta);
}

int main() {
	n = read();
	for (int i=1,l,r;i<=n;i++) {
		val[i] = read(); _hash[++tot] = val[i];
		if ((l = read()) != -1) ch[i][0] = l, is_rt[l] = 1;
		if ((r = read()) != -1) ch[i][1] = r, is_rt[r] = 1;
	}
	for (int i=1;i<=n;i++) if (!is_rt[i]) {rt = i; break;}
	dfs(rt, rt);
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) val[i] = lower_bound(_hash+1, _hash+1+tot, val[i]) - _hash, TOT[val[i]]++;
	
	add(rt, 1);
	if (!cnt[1]) vout += TOT[1];
	for (int i=2,w;i<=tot;i++) {
		if (id[i].size() > 0) {
			auto tmp = id[i].begin();
			w = tmp->second;
			del(w, i-1);
			add(w, i);
		}
		if (cnt[i] == 0) vout += TOT[i];
	}	
	printf("%d\n",vout);
	return 0;
}

【Codeforces 741D】Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

相关链接

题目传送门:http://codeforces.com/contest/741/problem/D
中文题面:https://blog.sengxian.com/solutions/cf-741d

解题报告

看起来这个串的定义非常强的样子,但仔细观察不难发现,就是出现次数为奇数的字母最多出现一个
于是我们定时一个二进制状态$f_{i,j}$表示$i$到$j$这段路径中哪些字符出现了奇数次

我们考虑在每一条合法路径的LCA处将其统计
于是就变成了子树相关问题,于是非常自然想到启发式合并

考虑从子树最大的儿子那里继承集合,其他的儿子的集合暴力加入
因为走一条边,需要异或一个值,整个集合的转移我们可以记录一个标记,然后在插入时使其生效
考虑统计的话,我们在暴力插入的时候,枚举是哪一位不同,单次查询是$O(22)$的
又因为加入是$O(1)$的,所以总的时间复杂度$O(n \log n \cdot 22)$

【BZOJ 1086】[SCOI2005] 王室联邦

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

来学习树上莫队的前置技能——树分块
题解让我们来%Po娘:《手把手教你块状树系列》

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

const int N = 1000+9;
const int M = N * 2;

int head[N],to[M],nxt[M],stk[M],top;
int num[N],pri[N],n,lim,cnt; 

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 void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void DFS(int w, int f, int bot) {
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i],w,top);
			if (top - bot >= lim) {
				pri[++cnt] = w;
				for (int i=top;i>bot;i--) {
					num[stk[i]] = cnt;
				}
				top = bot;
			}
		}
	}
	stk[++top] = w;
}

int main(){
	n = read(); lim = read();
	for (int i=1;i<n;i++) {
		Add_Edge(read(),read());
	}
	
	DFS(1,1,0);
	while (top) {
		num[stk[top--]] = cnt;
	}
	
	printf("%d\n",cnt);
	for (int i=1;i<=n;i++) {
		printf("%d%c",num[i],i==n?'\n':' ');
	}
	for (int i=1;i<=cnt;i++) {
		printf("%d ",pri[i]);
	}
	return 0;
}

【BZOJ 3569】DZY Loves Chinese II

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器:http://paste.ubuntu.com/23227745/

这个题,是我到目前为止,做过的最妙的一道题
没有之一

给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况:删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样,判一下是否线性无关即可

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

const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971; 
const int SGZ = 40;

int head[N],nxt[M],to[M],n,m,q,val[M];
int vis[N],c[SGZ],cnt,bas[SGZ],sym[N];

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 void Add_Edge(int u, int v) {
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; 
	to[++T] = u; nxt[T] = head[v]; head[v] = T; 
}

void DFS1(int w, int f) {
	vis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
		if (vis[to[i]]) {
			int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
			sym[w] ^= W; sym[to[i]] ^= W;	
		} else DFS1(to[i],w);
	}
}

void DFS2(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i]) 
		DFS2(to[i], w), val[i] ^= sym[to[i]], 
		val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}

inline bool update(int w) {
	for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
		if (!bas[i]) {bas[i] = tmp; return false;}
		else {tmp ^= bas[i]; if (!tmp) return true;}
	} return val[w]?false:true;
}

int main(){
	srand(9999971); n = read(); m = read(); 
	for (int i=1;i<=m;i++) Add_Edge(read(),read());
	DFS1(1,1); DFS2(1,1);
	for (int q=read(),k,tag;q;q--) {
		k = read(); tag = 1; memset(bas,0,sizeof(bas));
		for (int i=1;i<=k;i++) c[i] = read()^cnt;
		for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
		if (tag) puts("Connected"), cnt++;
	}
	return 0;
}

【Codeforces 700B】Connecting Universities

题目传送门:http://codeforces.com/problemset/problem/700/B
中文体面:http://paste.ubuntu.com/23084330/

好题啊!做了以后心旷神怡!巧啊!妙啊!
题解的话,让我们来召唤官方题解:http://codeforces.com/blog/entry/46283

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int N = 400000+9;

int n,k,tot,head[N],to[N],nxt[N],tag[N],f[N];
LL vout;

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

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

void DFS(int w, int fa) {
	f[w] = tot; if (tag[w]) tot++;
	for (int i=head[w];i;i=nxt[i]) 
		if (to[i] != fa) DFS(to[i], w);
	f[w] = tot - f[w];
}

int main(){
	n = read(); k = read();
	for (int i=1,lim=k*2,a,b;i<=lim;i++) tag[read()] = 1;
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	DFS(1,1); for (int i=2;i<=n;i++) vout += min(f[i],2*k-f[i]);
	printf("%I64d\n",vout); 
	return 0;
}