Hello 2024补题

Wallet Exchange（Problem - A - Codeforces）

题目大意：A，B做游戏，它们的钱包里各有a,b个硬币，轮到它们操作时，它们可以扔掉自己或者对手钱包里的硬币，谁不能操作谁输，问最后的胜者是谁。

思路：很显然取决于总数的奇偶性，奇数则A胜，偶数则B胜。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		a += b;
		if(a%2) printf("Alice\n");
		else printf("Bob\n");
	}
}

Plus-Minus Split（Problem - B - Codeforces）

题目大意：+代表1，-代表-1，给定一个字串，要求进行划分（划分中原来的相对顺序不能改变），每个划分的值是划分内的和的绝对值*划分的长度，结果是各个划分值的和，问最小的结果是多少。

思路：很显然只要划分的和为0，那么这段划分的值就最小，我们只用看有多少不能抵消，如果不能抵消那么就一个一个划开，使长度最小。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		string s;
		cin>>s;
		int c=0;
		for(int i=0;i<n;i++)
		{
			if(s[i]=='+') c++;
			else c--;
		}
		printf("%d\n",abs(c));
	}
}

Grouping Increases（Problem - C - Codeforces）

题目大意：现有一个a[]，需要把它拆成两个数组，a[]中的元素只能属于两个数组之一，而且相对顺序不能改变，然后我们去计算两个数组中b[i]<b[i+1]的数对的对数和，要求输出最小和。

思路：这道题实际上是贪心的题目，因为只需要考虑相邻元素之间的关系，我们只用记录新数组最后位置的元素即可，假设已经插入了i-1个元素了，现在要插入第i个元素，而此时新数组的两个元素分别为b,c,且b<c（b==c那么两个数组完全等价，没有讨论的必要，随便插入一个即可）,那么现在的问题就转化成将a[i]插入哪个数组。a[i]与b,c有三种关系：

1.a[i]<=b<c:此时，无论插入哪个数组都不会产生影响，但是我们注意到a[i]的插入会减小末尾元素，所以如果插c后面，a[i+1]如果小于c,但是大于b,就不得不产生影响，所以为了后面能让更大的数插入不产生影响，我们将它插到b后面。

2.b<c<a[i]：显然插在哪个后面都会造成影响，插入的过程实际上也是增加末尾元素的机会，显然增加b比增加c效益更大，因为增加b后，b,c后面都可以接更大的元素了。

3.b<a[i]=<c:此时插在c后面不会造成影响，另外对于a[i]<a[i+1]<c,a[i]插在b后面a[i+1]插在c后面，与a[i]插在c后面，a[i+1]插在b后面实际影响是等价的(b<a[i+1]<a[i]，讨论类似，也是产生1个影响)再者若a[i+1]>c,将a[i]插在c后面还能减少一次影响。

至此贪心部分就讨论完毕。（边界可以再细推一下）?

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int b=0x3f3f3f3f,c=0x3f3f3f3f;//为了保证b<c始终成立，记得更新后交换
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			if(x<=b) b=x;
			else if(x>c) 
			{
				b=x;
				swap(b,c);
				ans++;
			}
			else c=x;
		}
		printf("%d\n",ans);
	}
}

这个题的贪心解法和活动 - AcWing第二问有些相似，我们在此处一并讨论一下。

?

每个系统只能拦截非上升子序列，第二问要求找出最少需要配备多少个系统，才能拦截所有的导弹，我们再抽象一点，这题考的就是用多少个非上升的序列可以覆盖整个区间。也是从贪心的角度来进行分析：

假设现在已经有若干个系统了，然后要拦截高度为h的导弹，我们有两种选择，一种是用已经有的系统去拦截，另一种是新开一个系统，根据每个系统的性质我们可以知道，系统末尾元素肯定是最小的，而且比它大的元素不能接在它后面，所以如果所有系统的末尾都小于h，那么只能新开，如果有一部分系统的末尾不小于h，那么为了使结果尽可能的少，肯定是接在它们中某一个的后面更划算，那么就要考虑接在谁的后面更好，把h接上后会减少序列末尾的值，为了使它们能够拦截后面更高的导弹，肯定是将h接在这些序列中小的那个后面才是最优的解法。进而我们考虑如果维护，显然这些结尾是满足单调递增的关系的，这样就可以二分查找答案。进而该题的贪心部分分析完毕。

这两题都有一个很明显是贪心的点，就是需要对于每一个点进行决策，那么对每一个决策讨论的过程就是贪心的过程。所以下次涉及需要对一个区间进行操作，而且每步操作需要考虑策略的时候就要想一想贪心是否可以。

01 Tree（Problem - D - Codeforces）

题目大意：给出一个序列，我们需要判断这个序列是否与某个特定二叉树dfs遍历的叶子节点序相同，这里的特定二叉树是指除了叶子节点外的节点都有两个子节点，同时两条边的边权一个为1，一个为0.

思路：这里的叶子节点可能有兄弟节点，也可能没有兄弟节点。来看叶子节点与父节点的关系，父节点与其中一个子节点的值相同，比另一个子节点的值小1，那么如果一个点的左右相邻位置有比它小1的值，那么就说明它可能有兄弟节点，我们如果删除较大的子节点，那么因为另一个子节点的值与父节点的值相同，所以实际上相当于删除了两个子节点，将父节点变成一个叶子节点。我们可以确定值最大的那个点一定有兄弟节点，我们从最大的那个入手，不断往前删，最后如果只有一个点没被删，而且值为0，那么就说明有这样的二叉存在。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N],l[N],r[N],st[N];
int n;
int ok(int k)
{
	if(k<1||k>n) return 0;
	if(a[k]-a[l[k]]==1||a[k]-a[r[k]]==1) return 1;
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			l[i]=i-1;
			r[i]=i+1;
			st[i]=0;
		}
		a[0]=a[n+1]=-10;//指针会指到它们，初始化一下，防止误判
		priority_queue<pair<int,int>>p;
		for(int i=1;i<=n;i++)
		{
			if(ok(i))
			{
				st[i]=1;
				p.push({a[i],i});
			}
		}
		while(p.size())
		{
			auto it=p.top();
			p.pop();
			int v=it.first,i=it.second;
			//这里更新一定要特别注意，很容易出错。
			l[r[i]]=l[i];
			r[l[i]]=r[i];
			if(!st[l[i]]&&ok(l[i]))
			{
				st[l[i]]=1;
				p.push({a[l[i]],l[i]});
			}
			if(!st[r[i]]&&ok(r[i]))
			{
				st[r[i]]=1;
				p.push({a[r[i]],r[i]});
			}
		}
		int f=0,v=3e5;
		for(int i=1;i<=n;i++)
		{
			if(!st[i])f++;
			v=min(v,a[i]);
		}
		if(f==1&&v==0) printf("YES\n");
		else printf("NO\n");
	}
}

有时候做不出来的意义只是告诉你该学什么东西了，别附加太多别的意义。