牛客第四场 题解
比赛传送门

by fn

比赛概况
过了四道，感觉还可以，算正常发挥啦。

---

签到题

F题 Just a joke 只是一个玩笑

考察内容
思维

分析
对于第一种操作, 会使得边数 -1
对于第二种操作, 会删除一棵树，使得点数 -k, 边数 -(k-1)

任何一种操作都会使得点数+边数的和减少一个奇数, 所以答案只跟 n+m 的奇偶性有关

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
int main(){
    
	cin>>n>>m;
	for(int i=1;i<=m;i++){
    
		int u,v;
		cin>>u>>v;
	}
	
	if((n+m)%2==0) cout<<"Bob"<<endl; //
	else cout<<"Alice"<<endl; 
	return 0;
}

---

基本题

C题 LCS 最长公共子串

题目大意
构造长为 $n$ 的字符串s1,s2,s3, 使s1,s2的最长公共子串长 $a$, s2,s3的最长公共子串长 $b$ , s1,s3的最长公共子串长 $c$。

考察内容
暴力

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
ll n,m,a,b,c;
char s[4][N];
int main(){
     //
	cin>>a>>b>>c>>n;
	
	int min1=min(a,min(b,c));
	
	if(n<a+b+c-2*min1){
     // 判断可行性 
		puts("NO");
		return 0;
	}
	
	for(int i=1;i<=3;i++){
     // 初始化 
		for(int j=1;j<=n;j++){
    
			s[i][j]=' ';
		}
	}

	if(min1==a){
     // a最小 
		for(int i=1;i<=a;i++){
    
			s[1][i]='a';
			s[2][i]='a';
			s[3][i]='a';
		}
		if(b<c){
    
			for(int i=a+1;i<=b;i++){
    
				s[2][i]='b';
				s[3][i]='b'; 
			}
			for(int i=b+1;i<=c+(b-a);i++){
    
				s[1][i]='c';
				s[3][i]='c';
			}
		}
		else{
     // b>=c
			for(int i=a+1;i<=c;i++){
    
				s[1][i]='c';
				s[3][i]='c'; 
			}
			for(int i=c+1;i<=b+(c-a);i++){
    
				s[2][i]='b'; //
				s[3][i]='b';
			}
		}
	}
	else if(min1==b){
    
		for(int i=1;i<=b;i++){
    
			s[1][i]='b';
			s[2][i]='b';
			s[3][i]='b';
		}
		if(a<c){
    
			for(int i=b+1;i<=a;i++){
    
				s[1][i]='a';
				s[2][i]='a'; 
			}
			for(int i=a+1;i<=c+(a-b);i++){
    
				s[1][i]='c';
				s[3][i]='c';
			}
		}
		else{
     // a>=c
			for(int i=b+1;i<=c;i++){
    
				s[1][i]='c';
				s[3][i]='c'; 
			}
			for(int i=c+1;i<=a+(c-b);i++){
    
				s[1][i]='a';
				s[2][i]='a';
			}

		}
		
	}
	else{
     // min1==c 
		for(int i=1;i<=c;i++){
    
			s[1][i]='c';
			s[2][i]='c';
			s[3][i]='c';
		}
		if(a<b){
    
			for(int i=c+1;i<=a;i++){
    
				s[1][i]='a';
				s[2][i]='a'; 
			}
			for(int i=a+1;i<=b+(a-c);i++){
    
				s[2][i]='b';
				s[3][i]='b';
			}
		}
		else{
     // a>=b
			for(int i=c+1;i<=b;i++){
    
				s[2][i]='b';
				s[3][i]='b'; 
			}
			for(int i=b+1;i<=a+(b-c);i++){
    
				s[1][i]='a';
				s[2][i]='a';
			}

		}
		
	}
	
	// 填满空格 
	for(int i=1;i<=3;i++){
    
		for(int j=1;j<=n;j++){
    
			if(s[i][j]==' ') s[i][j]='c'+i;
		}
	}
	
	// 输出 
	for(int i=1;i<=3;i++){
    
		for(int j=1;j<=n;j++){
    
			cout<<s[i][j];
		}
		puts("");
	}
	return 0;
}

---

J题 Average 平均值

题目大意
给定序列 a,b, 找 a 的一个长度至少为 x 的平均值最大的子区间和 b 的一个长度至少为 y 的平均值最大的子区间。输出两个平均值的和。

考察内容
二分，前缀和

分析
poj2018，经典二分+前缀和，套板子。注意一下边界和精度。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+10; //
int n,F;
double ans;
double a[maxn+5],b[maxn+5],sum[maxn+5];

bool ok(double mid){
    
	for(int i=1; i<=n; ++i){
    
		b[i]=a[i]-mid;
	}
	for(int i=1; i<=n; ++i){
    
		sum[i] = sum[i-1] + b[i];
	}
	double min_val = 1e10,ans=-1e10;
	for(int i=F; i<=n; ++i){
    
		min_val = min(sum[i-F], min_val); // 前面（0~i-F）的最小前缀和 
		ans = max(ans, sum[i]-min_val);
	}
	return ans>=0;
}
void solve(){
    
	double l=-1,r=100010,eps=1e-8; // 2分平均数 
	while(r-l>eps){
    
		double mid = (l+r)/2;
		if(ok(mid)) l=mid;
		else r=mid;
	}
	ans+=(l+r)/2; // 累加答案 
}

int main(){
    
	int m,y;
	cin>>n>>m>>F>>y;
	for(int i=1; i<=n; ++i){
    
		scanf("%lf",&a[i]);
	}
	solve();
	
	n=m;
	F=y;
	for(int i=1; i<=n; ++i){
    
		scanf("%lf",&a[i]);
	}
	solve();
	
	printf("%.8f",ans);
	return 0;
} 

---

I题 Inverse Pair 逆序对

题目大意
给定全排列 $a$ ,对每个元素可以执行+1的操作或不变，求操作后最少的逆序对对数。

分析
考虑一下什么情况下 +1 这个操作会让逆序对变少

如果 x 在 x+1 的后面, 则我们把 x 这个数+1, x+1 不变, 就能让逆序对减少 1

那考虑建一张图, 如果 x 在 x+1 后面则连边 (x,x+1), 最后会得出若干条链, 一条长度为 L 的链我们最多用它减少 L/2 个逆序对

时间复杂度 $O(nlogn)$

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

long long n,a[200005],tr[200005],t[200005],ans;
void add(long long x) {
    
	for(long long i=x;i<=n+1;i+=i&-i) {
    
		tr[i]++;
	}
	return;
}
int ask(long long x) {
    
	long long ans=0;
	for(long long i=x;i;i-=i&-i) {
    
		ans+=tr[i];
	}
	return ans;
}
int main() {
    
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) {
    
		scanf("%lld",&a[i]);
		if(t[a[i]+1]==1) {
    
			ans+=ask(n+1)-ask(a[i]+1);
			add(a[i]+1);
		} else {
    
			t[a[i]]=1;
			ans+=ask(n)-ask(a[i]);
			add(a[i]);
		}
	}
	printf("%lld",ans);
 	return 0;
}

---

进阶题

E题 Tree Xor 树异或

题目大意
给定一棵有 $n$ 个结点的树，每个结点记录一个权重 $w$。给定每个结点权重的区间，每一条边上记录相邻两个结点进行异或后的值。求树上有多少种可能的权重分配。

考察内容
数据结构（线段树 或 字典树）

分析
先令 $w[1]=0$, 解出剩下的 $w$。
之后可以发现, 如果要 $w[1]=a$ , 那么剩下的 $w$ 都会 $xor$ 上 $a$
所以就变成了求解合法的 $a$ 的数量, 限制有 $n$ 个不等式, 形式为

$l[i]<=w[i]$ $xor$ $a<=r[i]$ , $i=1,2,3,4,...,n$

也就是 $a$ $in$ { $x$ $xor$ $w[i]$ | $l[i]<=x<=r[i]$ }

考虑把 $[L[i],R[i]]$ $xor$ $w[i]$ 分成若干个连续的区间。

我们可以利用 $[0,2^{30-1}]$ 的线段树（或者字典树）, 把 $[L[i],R[i]]$ 分成 $O(logW)$ 个连续的区间, 且每个区间的形式是 : $k...30$ 位相同, $0...k-1$ 位是 $0$ 到 $2^{k-1}$, 这样的区间异或上 $w[i]$ 后仍然还是一个区间

之后我们对这 $n$ 组区间求个交, 就可以得出答案的区间
时间复杂度 : $O(nlo{g}^{2}n)$

#include<bits/stdc++.h>
using namespace std;
const int M=8000005;

int son[M][2];
bool flag[M];
int rt=1,tot=1;
int l[100005],r[100005];
struct ed{
    
	int x,l,nx;
}e[100005*2];
int nx[100005],ecnt=1;
void add(int x,int y,int l){
    
	e[ecnt]=(ed){
    y,l,nx[x]};
	nx[x]=ecnt++;
}
void del(int t,int v){
    
	int p=rt;
	for (int i=30;i>=t;i--){
    
		if (!son[p][(v>>i)&1])son[p][(v>>i)&1]=++tot;
		p=son[p][(v>>i)&1];
	}
	flag[p]=1;
}
void chk(int l,int r,int x){
    
	int t1=l^x,t2=r^x;
	for (int i=30;i>=0;i--){
    
		if ((l>>i)&1)del(i,t1^(1<<i));
		if (!((r>>i)&1))del(i,t2^(1<<i));
	}
}

void dfs(int f,int x,int v){
    
	chk(l[x],r[x],v);
	for (int i=nx[x];i;i=e[i].nx)if (e[i].x!=f){
    
		dfs(x,e[i].x,v^e[i].l);
	}
}
int res;
void dfs1(int d,int x,int v){
    
	if (flag[x])return;

	if ((!x)){
    
		res+=(1<<(d+1));
		return ;
	}
	dfs1(d-1,son[x][0],v);
	dfs1(d-1,son[x][1],v+(1<<d));
}
int calc(){
    
	dfs1(30,rt,0);
	return res;
}
int n;
int main(){
    
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
    
		scanf("%d%d",&l[i],&r[i]);
	}
	for (int i=1;i<n;i++){
    
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		add(x,y,t);
		add(y,x,t);
	}
	dfs(1,1,0);
	printf("%d\n",calc());
}

---

B题 Sample Game 样品游戏

题目大意
给定范围 $n$ 和生成每个数字的概率 $p$ ，不断生成 $[1,n]$ 范围的随机数，如果当前生成的数字大于等于之前所有的数字就继续生成。求生成数字个数平方的期望。

考察内容
概率与数学期望

结论
答案是 $2f^{{}^{\prime }}(1)+f(1)$，其中 $f(1)=\prod _{i=1}^n\frac{1}{1-p_i}$ , $f^{{}^{\prime }}(1)=f(1)\sum _{i=1}^n\frac{p_i}{1-p_i}$

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

const int N=105;
const int mo=998244353;
int n,a[N],p[N],T[N],S;
int power(int x,int y){
     // 快速幂 
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo;
	return s;
}
int main(){
    
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]), S+=a[i]; 
	
	for (int i=1;i<=n;i++) a[i]=1ll*a[i]*power(S,mo-2)%mo;
	S=1;
	for (int i=1;i<=n;i++){
    
		p[i]=1ll*a[i]*S%mo*power(1+mo-a[i],mo-2)%mo;
		S=(S+p[i])%mo;
	}
	for (int i=n;i>=1;i--){
    
		int S=1;
		for (int j=i+1;j<=n;j++)
			S=(S+1ll*a[j]*T[j])%mo;
		T[i]=1ll*S*power(1+mo-a[i],mo-2)%mo;
	}
	int ans=1;
	for (int i=1;i<=n;i++)
		ans=(ans+1ll*a[i]*T[i])%mo;
	for (int i=1;i<=n;i++)
		ans=(ans+2ll*p[i]*T[i])%mo;
	cout<<ans<<endl;
}

---