Hello 2024 (A~D)

传送门

代码框架

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
#define se second 
#define fi first
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pli pair<LL,int>
#define MEM(a,x) memset(a,x,sizeof(a))
#define lowbit(x) ((x)&-(x))
#define db double
typedef long long LL;
using namespace std;
const int N=1e6+10,M=998244353;
inline void Solve()
{
     
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		Solve();
	}
	return 0;
}

A. Wallet Exchange

题意?

A,B两个人玩游戏，A为先手。初始两个人钱包钱数分别有a,b。每一轮玩家依次进行两个操作：1.交换两人的钱包，也可以不交换。2.把手上钱包钱数减一，如果为0不能操作。

最后不能操作的人输掉游戏。

给定初始a,b的值，判断A,B哪个能赢。

思路

注意到第一个操作使得当前玩家可以在第二步操作任意一个他想要操作的钱包，两个钱包可以等价为一个钱包，每一个人操作将总钱数减一，于是只需判断总钱数 a+b 的奇偶性即可，奇数则先手赢。

代码

inline void Solve()
{
	int a,b;
	cin>>a>>b;
	if((a+b)&1) cout<<"Alice"<<endl;
	else cout<<"Bob"<<endl; 
}

B. Plus-Minus Split

题意

给定长度为 n 包含 -1 或 1 的数组 a，将 a 做分割，要求每一段不能为空。每一段的花费为这一段的所有数和的绝对值乘长度，总花费为为所有段花费之和。

现在要使得总花费最小。

思路

如果一段长度为 n 的连续段一种值，不如将其划分为 n 个长度为 1 的区间，得到总花费最小为 n 。其他任何划分长度大于 1 都会产生比 1 大的花费，使得总花费大于 n。

如果一段中有 a 个 1 和 b 个 -1 ， a 大于 b ，可以将 b 个 -1 和 1 划分为一个对总花费无贡献的区间，剩下 a-b 个 1 的最小花费为 a-b 。其他划分方法都会使得相同长度的段增多使得值大于 a-b。

可以得到贪心策略：如果可以把若干相等个数的1和-1划为一段，将剩下多出来1或-1全部分为长度为1的区间，这样最优的情况就是整个数组和的绝对值，这种划分总是存在的。

代码

inline void Solve()
{
	int n,tot=0;string s;
	cin>>n>>s;
	rep(i,0,n) tot+=(s[i]=='+'?1:-1);
	cout<<abs(tot)<<endl;
}

C. Grouping Increases

题意

将长度为 n 的数组划分为两个子序列（不一定连续，可以为空）s，t，最小化 p(s)+p(t) 。其中 p(b) 定义为 b 数组中??的个数。

思路

从前往后考虑每一个?，将??放到 s 或 t 中，最终要使得 s ，t 的相邻严格上升的对的数量最小。贪心思路类似于构造最长上升子序列，注意到在分配??? 时只需要考虑 s，t 的栈顶元素，故用s，t 分别表示栈顶元素，初始化将足够大的数先压入 s，t 中，分为以下几种情况：?

1. 如果满足??，添加到其中任意一个都会使得答案 +1，按照“越大越好”的思想，栈顶越大在后续更不容易形成上升序列，此时应该保留 s,t 中较大的一个。

2. 如果满足??，同理，加入到栈顶值小的一个中。

3. 如果其中一个满足条件，将其加入到另一个栈中，以避免答案增加。

代码

const int N=2e5+10;
int a[N];
inline void Solve()
{
	int n,ans=0,s1=0,s2=0;
	cin>>n;
	rep(i,1,n+1){cin>>a[i];}
	s1=s2=n+1;
	rep(i,1,n+1){
		if((a[i]<=s1&&a[i]<=s2)||(a[i]>s1&&a[i]>s2)){
			if(a[i]>s1&&a[i]>s2) ++ans;
			if(s1>=s2) s2=a[i];
			else s1=a[i];
		}else{
			if(a[i]<=s1) s1=a[i];
			else s2=a[i];
		}
	}
	cout<<ans<<endl;
}

D. 01 Tree

题意

给定一个长度为 n 的数组，每个值代表一颗完全二叉树的叶子到根节点的距离，顺序是从根的 dfs序 （从左到右），问能否构造出来这样的完全二叉树，且满足每个非叶子节点连接左儿子和右儿子的边权其中一个为 1，一个为 0。

思路

对于合法的完全二叉树，同一个父节点的两个子节点，由于父节点到根节点的距离是不变的，而且两个儿子边权一个为 1，一个为 0，说明这两个子节点的值相差为1。因为有一个边为0，可知较小的子节点的距离就是该父节点到根的距离。我们可以从给出的数组开始，每次合并最大且相邻相差为 1 的点，保留小的一个值，重复操作直到不能合并为止，最后能合并成一个 0 则合法。

这个过程可以用双向链表来模拟。首先初始化链表：将原数组中连续相同的值删除只保留一个，为其创建双向节点，用集合 s[i] 维护元素值为 i 的链表下标集。从大到小对链表进行操作：遍历 s[i] 的每一个节点，检查节点左右邻节点的值是否存在比它小 1 的，如果不存在说明该节点无法删除，不合法；否则删除该节点，注意删除后还要处理左右的值相等的情况（例如 ... 2 3 2 ... ），这时删除左边或者右边，只需要保留一个即可。

代码

const int N=2e5+10;
int a[N],v[N],l[N],r[N];
set<int>s[N];
inline void Mkn(int k,int x,int pre,int ne)
{
	v[k]=x;l[k]=pre;r[k]=ne;
}
inline void Del(int x)
{
	r[l[x]]=r[x];
	l[r[x]]=l[x];
}
inline void Solve()
{
	int n,m=0;
	cin>>n;
	rep(i,1,n+1){cin>>a[i];}
	rep(i,0,n) s[i].clear();
	rep(i,1,n+1){
		++m;Mkn(m,a[i],m-1,m+1);
		s[a[i]].insert(m);
		int j=i;
		while(j<=n&&a[j]==a[i]) ++j;
		i=j-1;
	}
	Mkn(0,-1,0,1);Mkn(m+1,-1,m,0);
	sort(a+1,a+1+n);
	if(a[1]==0&&a[2]==0||a[1]!=0){
		cout<<"NO"<<endl;
		return;
	}
	per(i,n,1){
		int j=i;
		while(j>=1&&a[j]==a[i]) --j;
		i=j+1;
		for(int x:s[a[i]]){
			if(v[l[x]]!=a[i]-1&&v[r[x]]!=a[i]-1){
				cout<<"NO"<<endl;
				return;
			}
			Del(x);
			if(v[l[x]]==v[r[x]]){
				s[v[l[x]]].erase(l[x]);
				Del(l[x]);
			}
		}
	}
	cout<<"YES"<<endl;
}