Codeforces Round 1023 (Div. 2) 补题

此次排名情况：

• 共8k+，排名1651，做出ABC三题。
• Rating+81，当前为 1442 。
• 比赛链接

A. LRC and VIP

题意：有一个长度为 n 的数组 a ，你需要将数组分成 2 个序列，满足一下条件：

• 每个元素只能属于二者之一
• 每个序列至少包含一个元素
• 两个序列全部GCD不相等

题解：当数组 a 中的元素全部相等时，不论序列如何分，两序列gcd相等，不可能划分。

比较数组 a 中的最大值和最小值，如果最大值和最小值相等，输出 no。

否则将最大值一个元素作为序列，其余的作为另一个序列即可。

因为 \(gcd(a,b)≤min(a,b)\) ，其余的元素的 gcd 肯定比最大值小，且不相等。

//获得最大值
m=*max_element(a.begin(),a.end());
//获得最小值
n=*min_element(a.begin(),a.end());

void solve(){
	int n;cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	//获得最大值最小值
	int mn=*min_element(a.begin(),a.end());
	int mx=*max_element(a.begin(),a.end());
	if(mn==mx){cout<<"No\n";return;}
	cout<<"Yes\n";
	for(int i=0;i<n;i++)
		cout<<(1+(a[i]==mx))<<"\n";
}

B. Apples in Boxes

题意：有一个长度为 n 的数组 a ，两个人轮流操作。

• 选择一个 a 中的大于 0 的元素，使这个 \(a_i\) 减 1。
• 如果没有可以减的元素，当前人输。
• 如果操作后，数组中最大值 - 最小值大于 k ，那么当前人输。

题解：

假设 \(max(a)-min(a)≤k\) 成立，并且至少有一个 \(a_i≥1\)。那么可以在保持这个条件的情况下拿走一个苹果。

我们从最大元素中减去，最小元素不会发生变化。即 \(max(a)\) 减少 0 或者减少 1，\(max(a)-min(a)\) 只会减少，与 k 进行比较显然成立。有一个特例，即所有元素都相同的情况，操作后极值的差由 0 变成 1。

因此，对于一个有 \(max(a)-min(a)≤k\) 的数组来说，唯一输的方式，就是将所有的 \(a_i\) 全部输掉，全部等于 0。执行 \(\sum_{i=1}^{n} a_i\) 次操作后全部输掉，因为每个回合都只会减少 1 。

如果一开始数组就不成立，直接输出第一个人。

void solve(){
	int n,k;cin>>n>>k;
	vector<int> a(n);
	ll sum=0;
	for(int i=0;i<n;i++) cin>>a[i],sum+=a[i];
	sort(a.begin(),a.end());
	a[n-1]--;//最大值-1
	sort(a.begin(),a.end());
	if(a[n-1]-a[0]>k||sum%2==0) cout<<"Jerry\n";
	else cout<<"Tom\n";
}

C. Maximum Subarray Sum

题意：给你一个长度为 n 的数组 a 和一个正整数 k，数组中有些元素可以任意更改，使最大子数组和正好是 k 。

题解：

不可能的情况：将可替换元素全部改为 -INF，如果最大子数组和仍然大于 k ，答案不可能。还有，如果没有可替换元素，且最大子数组和不为 k ，答案不可能。

其余皆有可能。

将可替换元素全部改为 -INF，然后选某个可替换元素，计算此元素前面的最大子数组和，计算后面的最大子数组和，然后将这个元素更改为某个值，使最大子数组和为 k 即可。

void solve(){
	ll n,k;cin>>n>>k;
	string s;cin>>s;
	vector<ll> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	int pos=-1;
	for(int i=0;i<n;i++)
		if(s[i]=='0')
			pos=i,a[i]=-1e13;
	ll mx=0,cur=0;
	for(int i=0;i<n;i++){
		cur=max(cur+a[i],a[i]);
		mx=max(mx,cur);
	}
	if(mx>k||(mx!=k&&pos==-1)){
		cout<<"No\n";
		return;
	}
	if(pos!=-1){
		mx=0,cur=0;
		ll l,r;
		for(int i=pos+1;i<n;i++){
			cur+=a[i];
			mx=max(mx,cur);
		}
		l=mx;
		mx=0,cur=0;
		for(int i=pos-1;i>=0;i--){
			cur+=a[i];
			mx=max(mx,cur);
		}
		r=mx;
		a[pos]=k-l-r;
	}
	cout<<"Yes\n";
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<"\n";
}

D. Apple Tree Traversing

题意：有一棵 n 个节点的树，每个节点上有一个苹果。你可以进行如下操作：

• 选择一条路径 (u,v)，这条路径每个节点上都有一个苹果。
• 假设 d 是路径上苹果的个数，依次写下三个数字 (d,u,v)。
• 然后去掉这条路径上所有的苹果

使写下的序列最大，输出序列。

题解：题解复杂度为 \(O(nlogn)\)。

一棵树中的最长路径为树的直径，可以使用树形DP或者搜索求解。

假设 \(f_i,g_i\) 是 \(i\) 的子树中从 \(i\) 出发的最长和第二长路径，

则树的直径为 \(max_{i=1}^n f_i+g_i\)。

当我们找到直径 \((u,v)\) 时，让我们更新路径 \((lca(u,v),root)\) 上所有 \(u\) 的直径 \(f_u,g_u\)。

使用 set 为每个节点 \(u\) 查找 \(f_u,g_u\) ，并使用 priority_queue 保持最大 \(f_i+g_i\)。总复杂度为 \(O(nlogn)\)。