【BZOJ 3811】玛里苟斯

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3811
神犇题解Ⅰ:https://blog.sengxian.com/solutions/bzoj-3811
神犇题解Ⅱ:http://yyy.is-programmer.com/posts/200623.html

解题报告

这题这么神,我们来分情况讨论:

1. $k = 1$

这就是一般的期望题。因为期望的线性,所以我们在二进制位下每一位分开考虑:

如果这一位上每一个数都是$0$,那么贡献肯定为$0$
如果有一个数为不为$0$那么我们有贡献的概率为$\frac{1}{2}$

证明的话,可以设$f_{1,0/1}$为考虑到第i个数,异或起来为0/1的概率
写出$DP$式子可以很轻松地发现这俩总是对半分,Q.E.D

于是我们直接把所有数$or$起来,然后除二输出即可
时间复杂度:$O(n)$

2. $k = 2$

这不是一般的期望题了,不是线性的,不能直接加 /(ㄒoㄒ)/~~
但我们发现某一个异或和为$(b_mb_{m-1} \cdots b_0)_{bin}$的话
其中第$i$位与第$j$位的贡献为$b_i \cdot b_j \cdot 2^{i+j}$

因为$b_i$与$b_j$是线性的,所以我们就可以枚举$i,j$然后直接加起来了!
根据$k = 1$时得到的结论,不难发现:

如果这两位独立则贡献的概率为$\frac{1}{4}$
如果这两位不独立,那么贡献的概率为$\frac{1}{2}$
如果这两位中有至少一位从没出现过,那么概率为$0$

于是我们暴力枚举$i,j$直接算贡献就可以了
时间复杂度:$O(62n + 62^2)$

3. $k \ge 3$

我们先来看一个结论:若$E(x^k) < 2^{63}$,初始集合中的每个数小于$2^{22}$
证明的话,sengxian教我的:

不妨用反证法,考虑答案为:$\sum\limits_{s \in \{1,2,\cdots,n\}}{\frac{v^3}{2^n}}$
假如有一个数的二进制下第$22$位出现了$1$,有$2^{n-1}$个集合异或起来后这一位为$1$
所以这一位的贡献就已经为$2^{63}$了,又因为答案小于$2^{63}$,矛盾,故不可能,Q.E.D

所以我们可以求出这些数的线性基,然后暴力枚举线性基的子集
根据$k = 1$时的人生经验,我们又可以得到每一种情况出现的概率相等
于是我们暴力枚举,然后暴力算贡献就可以了
时间复杂度:$O(21n + 2^{21})$

【NOI六连测】[D1T3] 联盟

题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18671145/
数据传送门:http://pan.baidu.com/s/1qYRC8w8
数据生成器:http://paste.ubuntu.com/18671482/

先来说一说lcr的很好想的做法,分类讨论:
1)联盟的所有城市,有一些在首都的子树外,一些在首都的子树内
2)首都在联盟形成伞形内,且子树中,无联盟的城市
3)首都和联盟完全独立
然后是分类处理:
1)用主席树查一查,这个答案是0
2)树上倍增,再利用主席树查一查
3)直接lca搞一搞
lcr的code:http://paste.ubuntu.com/18671740/

然后是std的算法,分类讨论同lcr,做法稍有不同:
1)这个可以不用主席树查,我们使用DFS序,二分找到小于首都的DFS序最大的一个,然后+1,即可判断
2)这个,我们还是用DFS序,找到小于首都最大的那个,然后+1,那么这两个一定是卡得最紧的两个,然后用LCA更新答案
3)直接lca搞一搞

这两种算法优越在,分来讨论以后,把一个帮派缩成了一个代表城市
std的算法优越在,神奇的DFS序,DFS离得近就是夹得紧
另外这种题目,反正不是分类讨论乱搞,就是分治,以后还是要多推推式子
递归版本:http://paste.ubuntu.com/18670939/
非递归版本:

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

const int MAXN = 1000000+9;
const int INF = 100000000;

int n,T,head[MAXN],to[MAXN],nxt[MAXN],k,dep[MAXN],fa[MAXN][20],LC[MAXN];
int l[MAXN],r[MAXN],tot,cnt[MAXN],que[MAXN],*itr[MAXN],BUF[MAXN],now[MAXN];

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

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

inline void DFS(){
	for (int i=1;i<=n;i++) now[i] = head[i];
	int w = 1; tot = 1;
	while (w) {
		if (!now[w]) {
			r[w] = tot;
			w = fa[w][0];
		} else {
			if (!l[w]) l[w] = ++tot;
			int tmp = to[now[w]]; now[w] = nxt[now[w]];
			if (dep[tmp] != dep[w]+1) continue;
			else w = tmp;
		}
	}
}

inline void BFS(){
	BUF[1] = 1; dep[1] = 1;
	for (int fro=1,bak=1;bak<=fro;bak++){
		int w = BUF[bak];
		for (int i=head[w];i;i=nxt[i]){
			if (!dep[to[i]]) dep[to[i]] = dep[w]+1,
			fa[to[i]][0] = w, BUF[++fro] = to[i];
		}
	}
}

inline bool cmp(const int &A, const int &B){
	return l[A] < l[B];
}

inline int find(int *arr, int ri, int val){
	if (l[arr[1]] >= val) return -1;
	else {
		int li=1,mid,ret;
		while (li <= ri){
			mid = (li+ri)/2;
			if (l[arr[mid]] < val) li=mid+1,ret=mid;
			else ri=mid-1;
		}
		return ret;
	}
}

inline int LCA(int a, int b){
	if (dep[a] < dep[b]) swap(a, b);
	for (int i=18;i>=0;i--)
		if (dep[fa[a][i]] >= dep[b]) 
			a = fa[a][i];
	if (a==b) return a;
	else {
		for (int i=18;i>=0;i--) if (fa[a][i] != fa[b][i])
			a = fa[a][i], b = fa[b][i];
		return fa[a][0];
	}
}	

inline void init_LCA(){
	for (int k=1;k<=18;k++)	for (int i=1;i<=n;i++)
		fa[i][k] = fa[fa[i][k-1]][k-1];
}

inline int DIS(int a, int b){
	int lca = LCA(a, b);
	return dep[a]+dep[b]-2*dep[lca];
}

inline void update(int *arr, int c, int v, int &ans, int lc){
	int lca = LCA(lc, v);
	if (lca == v) ans = min(ans, DIS(lc,v));
	else if (lca != v && lca != lc) ans = min(ans, dep[lc]+dep[v]-2*dep[lca]);
	else {
		int tmp = find(arr,c,l[v]);
		if (tmp==-1){
			if (l[arr[1]] <= r[v] && l[arr] > r[v]) ans = 0;
			else ans = min(ans, DIS(v,LCA(v,arr[1])));
		} else {
			if (tmp < c && l[arr[tmp+1]] <= r[v]) ans = 0;
			else {
				int lca = LCA(v,arr[tmp]);
				ans = min(dep[v]-dep[lca], ans);
				if (tmp < c){
					lca = LCA(v,arr[tmp+1]);
					ans = min(dep[v]-dep[lca], ans);
				}
			}
		}
	}
}

int main(){
	freopen("alliances.in","r",stdin);
	freopen("alliances.out","w",stdout);
	srand(19991226); n = read(); 
	for (int i=1;i<n;i++) AddEdge(read(),read());
	BFS(); DFS(); itr[1] = que; init_LCA();
	k = read(); for (int i=1;i<=k;i++) {
		cnt[i] = read(); 
		itr[i+1] = itr[i]+cnt[i];
		for (int j=1,tmp;j<=cnt[i];j++) itr[i][j] = read();
		int buf = itr[i][1];
		for (int j=2;j<=cnt[i];j++) buf = LCA(buf, itr[i][j]);
		LC[i] = buf; sort(itr[i]+1,itr[i]+cnt[i]+1,cmp);
	}
	
	for (int v,t,ans,Q=read();Q;Q--){
		v = read(); t=read(); ans = INF;
		for (int i=1,w;i<=t;i++){
			w = read(); 
			BUF[i] = itr[w][1];
			update(itr[w], cnt[w], v, ans, LC[w]);
		} 
		if (ans){
			int buf = BUF[1];
			for (int i=2;i<=t;i++) buf = LCA(buf, BUF[i]);
			sort(BUF+1,BUF+t+1,cmp), 
			update(BUF, t, v, ans, buf);
		}
		printf("%d\n",ans);
	}
	
	return 0;
} 

在%原教的代码的时候,发现了一点特殊的技能:
如果我们使用“当前弧”类似的技能,那么我们可以用一个BFS + while()很优雅的代替掉DFS()