传送门

Hello 2024

A.Wallet Exchange

题目大意

Alice 和 Bob 玩游戏，Alice 先手。

两人各有一个数字 \(a,b\)。每个人需要依次进行下面两个操作：

交换两个人的数字或什么都不做。
将自己当前的数字减 \(1\)。

如果自己的数字小于 \(0\) 则输。求最后谁会赢。

多组测试，\(1 \le a,b \le 10^9, T \le 1000\)。

思路

因为如果任意一方的数字不为 \(0\)，我们就可以将这个数字换给自己，所以游戏结束时两人的数字一定均为 \(0\)。

判断两人初始数字和的奇偶性即可。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;

ll n,m;

void mian(){
	scanf("%lld%lld",&n,&m);
	if((n+m)&1)printf("Alice\n");
	else printf("Bob\n");
}
 
int main(){
	int T=1;
	scanf("%d",&T);
	while(T--)mian();
	return 0;
}

B.Plus-Minus Split

题目大意

给定一个长度为 \(n\) 的序列 \(a\)，你需要将它划分成若干个区间。区间的权值为其中所有数的和的绝对值。

求所有区间权值和的最小值。

多组测试，\(1 \le n \le 5000, T \le 1000\)。

思路

显然不划分就是最优的。直接计算答案即可。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;

ll n,m;

void mian(){
	ll ans=0;
	scanf("%lld",&n);
	while(getchar()!='\n');
	For(i,1,n){
		if(getchar()=='+')++ans;
		else --ans;
	}
	printf("%lld\n",abs(ans));
}
 
int main(){
	int T=1;
	scanf("%d",&T);
	while(T--)mian();
	return 0;
}

C.Grouping Increases

题目大意

给定一个长度为 \(n\) 的序列 \(a\)。你有两个空序列 \(s,t\)。

你需要依次操作每个序列 \(a\) 中的数。你可以选择将它加入 \(s\)，也可以选择将它加入 \(t\)。

假设 \(s,t\) 的长度分别为 \(p,q\)。定义权值 \(val=\sum\limits_{i=1}^{p-1}[s_i<s_{i+1}]+\sum\limits_{i=1}^{q-1}[t_i<t_{i+1}]\)。

求权值 \(val\) 的最小值。

多组测试，\(1 \le n \le 2 \times 10^5, 1 \le a_i \le n, T \le 10^4, \sum n \le 2 \times 10^5\)。

思路

贪心地考虑每个数。记 \(s,t\) 的最后一个数为 \(x,y\)，初始时 \(x,y\) 为极大值。

定义一个数能加入序列，当且仅当这个数不大于序列的最后一个数。

考虑加入数 \(z\)。

如果 \(z\) 能加入 \(s\) 也能加入 \(t\)：将 \(z\) 加入 \(x,y\) 中较小值代表的集合。
如果 \(z\) 只能加入 \(s\) 或只能加入 \(t\)：将 \(z\) 加入其能加入的集合。
如果 \(z\) 不能加入 \(s\)也不能加入 \(t\)：将 \(z\) 加入 \(x,y\) 中较小值代表的集合。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
const ll N=1e6+10;
using namespace std;

ll n,m;
ll a[N],b[N];

void mian(){
	ll ans=0;
	ll t1=1e9,t2=1e9;
	scanf("%lld",&n);
	For(i,1,n){
		scanf("%lld",&a[i]);
		if(t1>=a[i]&&t2>=a[i]){
			if(t1>t2)t2=a[i];
			else t1=a[i];
		}else if(t1>=a[i])t1=a[i];
		else if(t2>=a[i])t2=a[i];
		else if(t1<t2)t1=a[i],++ans;
		else t2=a[i],++ans;
	}
	printf("%lld\n",ans);
}
 
int main(){
	int T=1;
	scanf("%d",&T);
	while(T--)mian();
	return 0;
}

D.01 Tree

题目大意

一棵树是好树当且仅当其满足以下条件：

所有非叶子节点都有两个儿子。
所有非叶子节点连向左右儿子的边中，一条边权值为 \(0\)，一条边权值为 \(1\)。

定义树上两点的距离为它们的路径上所有边权的和。

将一棵好树的所有叶子节点按 dfs 序依次标号为 \(1 \to n\)。

给定一个长度为 \(n\) 的序列 \(a\)，求是否存在一棵好树，满足 \(i\) 号节点到根节点的距离为 \(a_i\)。存在输出 Yes，否则输出 No。

多组测试，\(2 \le n \le 2 \times 10^5, 0 \le a_i \le n-1, T \le 10^4, \sum n \le 2 \times 10^5\)。

思路

发现一个合法的序列一定有且仅有一个 \(0\)，且 \(x(x>0)\) 在序列中时，\(x-1\) 必定在序列中。

由于边权只有 \(0,1\)，所以如果我们需要在序列中插入一个数 \(x\)，那么一定只能在 \(x-1\) 的左边或右边。

直接判断给定的序列是否满足条件即可。

我们使用 dfs。

假设当前的数字为 \(x\)，区间为 \([l,r]\)。

用 vector 记录 \(x+1\) 出现的位置，二分找到所有在 \([l,r]\) 内的 \(x+1\)，将 \([l,r]\) 分隔为一些小区间，递归处理。

如果到达一个长度为 \(1\) 的区间且这个数不为 \(x+1\) 则输出 No。

代码实现

注意特判 \(0\) 的个数。

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
const ll N=1e6+10;
using namespace std;

ll n,m,flag;
ll a[N],b[N];
vector<ll>t[N];

void dfs(ll l,ll r,ll x){
	if(l>r)return;
	//二分
	ll lx=lower_bound(t[x].begin(),t[x].end(),l)-t[x].begin();
	ll rx=upper_bound(t[x].begin(),t[x].end(),r)-t[x].begin()-1;
	if(rx-lx+1==0)return void(flag=1);//区间中的数不为x+1
	//拆分小区间，递归
	for(ll i=lx;i<=rx;++i){
		dfs(l,t[x][i]-1,x+1);
		l=t[x][i]+1;
	}
	dfs(l,r,x+1);
}

void mian(){
	
	scanf("%lld",&n);
	//预处理
	flag=0;
	For(i,0,n-1)t[i].clear();
	For(i,1,n){
		scanf("%lld",&a[i]);
		t[a[i]].pb(i);
	}
	if(t[0].size()!=1){//特判
		printf("No\n");
		return;
	}
	For(i,0,n-1)t[i].pb((ll)1e9);//防止二分越界
	dfs(1,n,0);
	if(flag){
		printf("No\n");
		return;
	}
	printf("Yes\n");
	
}
 
int main(){
	int T=1;
	scanf("%d",&T);
	while(T--)mian();
	return 0;
}