Codeforces Round 899 (Div. 2)补题

Increasing Sequence（Problem - A - Codeforces）

题目大意：现有一个数组a[],同时定义good数组b[]:

1.b[i]为正整数

2.a[i]!=b[i]

3.b1<b2<...<bn;

求所有good数组中bn的最小值。

思路：实际上很简单，我们将b[1]从1开始，每次递增1，如果b[i]==a[i],那么就往后延一个。因为要想是b递增，后一个必须比前一个大，同时，a[i]!=b[i]，那么等于的时候再往后延一个即可。

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main ()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		int b=1;
		for(int i=1;i<=n;i++)
		{
			if(b==a[i]) b++;
			b++;
		}
		printf("%d\n",b-1);
	}
}

Sets and Union（Problem - B - Codeforces）

题目大意：现有n个集合：s1,s2,...,sn,我们需要从中挑选若干个集合，求它们的交集s，并使s!=s1Us2U...Usn，求s的最大元素个数。

思路：很明显，我们需要找到尽可能多的集合去得到这个交集，那么我们首先统计出每个元素出现几次，以及出现在哪些集合当中。我们要合并尽可能多的集合，就要从这些出现次数特别少的数入手，将它们存在的集合去掉。

但是这些元素可能存在于一个空间，可能存在于两个空间，可能存在与3个空间，这样的话，找最小值是很麻烦的。

那么既然区间麻烦，我们来考虑单点，就是去考虑这个数最后能不能出现在结果中，我们讨论能出现，显然很麻烦，如果要用二进制数表示状态的话，2^50一定超时，那么我们来讨论如果某个元素不能出现在结果中，那么它出现过的数组，肯定都不能出现在结果中，我们对于每个数都去讨论如果它不出现在结果中，结果的值是多少，取一个最大值即可。

这个题就很好体现了区间和单点之间的转换，首先肯定回想将哪些区间合并起来（诚然这里用区间并不是很严谨，但是对于集合这种一大块包含很多数的容器，我们暂且这么称呼），既然同时考虑很多个数麻烦的话，我们就一个数一个数考虑，考虑它出现麻烦的话，我们就考虑它不出现的情况。问题就是需要一点一点地去分析清楚，一条路不通就换一条，不要怕。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		set<int>s[n+2],all;
		for(int i=1;i<=n;i++)
		{
			int c;
			scanf("%d",&c);
			while(c--)
			{
				int x;
				scanf("%d",&x);
				s[i].insert(x);	
				all.insert(x);
			}
		}	
		int mx=0;
		for(auto it:all)
		{
			set<int>m;
			for(int i=1;i<=n;i++)
			{
				if(!s[i].count(it))
				{
					for(auto j:s[i]) m.insert(j);
				}
			}
			int d=m.size();
			mx=max(mx,d);
		}
		printf("%d\n",mx);
	}
}

Card Game（Problem - C - Codeforces）

题目大意：现有一叠牌，共n张，我们初始分数是0，每次可以进行如下三个操作之一：
1.抽走一张序号为奇数的牌，并加上它的值；

2.抽走一张序号为偶数的牌；

3.结束游戏

需要求最后的最大分数

思路：这道题我本来以为是动态规划，但没想到它是贪心。我们还是来分析下状态与操作的本质吧。

首先对于每张牌，位于它后面的牌怎么抽走都对它没有影响，但是位于它前面的牌被抽走就会影响它的奇偶性。每张牌被抽走都对结果有一个贡献，比如，一张正数牌a在奇数位置被抽走，那么对结果的贡献就是a，在偶数位置被抽走，那么对结果的贡献就是0；一张负数牌，在奇数位置被抽走，那么对结果的贡献就是负的，如果在偶数位置被抽走，那么对结果的贡献就是0，我们对于每一张牌要尽可能地去最大化它地贡献。如何最大化它的贡献呢，首先如果一张正数牌，我们尽量要让它在奇数位置被抽走，一张负数牌，要么不动，要么在偶数位置被抽走。那么要想实现，我们就要考虑前面的牌得动，不然可能无法实现，那么如果动的话，动哪张呢？实际上不用具体到某一张牌，我们将所有牌的移动后产生的效益计算出来，从前往后计算，并同时记录前面的效益中的最大值，然后，我们如果要移动，肯定也是移动前面效益中的那个最大值，如果不移动那当然更好。这个最大值可能是负的，那么这也是记录它的意义。因为负的会对后面移动后产生的实际效益产生影响，正的就无所谓，就是要记住不能累计。而且还有一个点，a,b,c如果对于b，前面的数需要移动，对于c又不能移动的话，我们可以先移动c，再移动a，再移动b，不用担心a的移动对c产生影响，因为我们只是考虑前面的能不能优化它的状态，如果不能优化，那么先移动它不就好了。最后遍历将正的贡献加起来即可，不用担心前面的移动的贡献，我们在计算每个点的贡献的时候，已经将它前面的点考虑进去了，所以累加即可。

那么至此，其实已经讨论结束。这道题就是每个点对于结果都有一个贡献，我们要优化它对结果的贡献。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010],s[200010];
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		s[1]=a[1];
		int mx=a[1];
		for(int i=2;i<=n;i++)
		{
			if(a[i]>0) 
			{
				if(i%2) s[i]=a[i];
				else
				{
					if(mx<0) s[i]=max(0ll,mx+a[i]);
					else s[i]=a[i];
				}
				mx=max(mx,s[i]);
			}
			else 
			{
				s[i]= i%2 ?a[i]:0;
				mx=max(mx,s[i]);
			}
		}
		int sum=0;
		for(int i=1;i<=n;i++) sum += s[i]>0?s[i]:0;
		printf("%lld\n",sum);
	}
}

ps:我去查了下，贪心类的题目到底考什么，找到一个比较精简的答案，贪心就是找到局部最优解，如果局部都是最优的，那么合起来也是最优的。比如c题，我们最大化了每个点的贡献，那么最后的结果一定可以得到最优解。贪心（参考链接）

像c题：

数学模型就是——对于每张牌，位于它后面的牌怎么抽走都对它没有影响，但是位于它前面的牌被抽走就会影响它的奇偶性。同时每张牌在不同的位置被抽走，贡献不同。

子问题就是——每张牌的贡献

子问题最优解——每张牌是否移动，进而被抽走后能够得到的最大值

合并——最后统计所有正贡献的过程。

这和dp的区别在于，dp是把问题分小，一步一步逼近临界，直到能算出状态位置，而贪心则是尽可能独立地算出每个最优状态，将他们合并起来。贪心还有一种与排序有关的思想，本题不涉及而已。

Tree XOR(Problem - D - Codeforces)

题目大意：我们给定一棵树，树的根是不定的，树上的每个节点都有一个值，我们选择任意一个点作为树的根，然后我们对树进行操作，每次操作可以选择一个节点v和一个值c，我们需要做的就是将v以及它的子树的节点值异或上c，然后此次操作的花费就是c*sv(sv表示v的子树的节点数)，我们需要对于以每个点为根的情况找出将树上节点的值统一的最小花费。

思路：这题既然涉及二进制，我们就一位一位来看，我们的操作实际意义是什么呢？就是将一个点以及它的子树上的这一位全部操作一次，我们既然一位一位来看，那么对于每一个点，相当于只有0和1两种情况，异或上0是没有意义的，那么就简化成某个点是否需要异或1（后面所说的操作就是让它异或1，不操作就是不异或1）每次操作选定一个点，实际上选定的就是它即它后面的所有点，它们需要被操作一次，我们很容易发现，此时的c==1，要想使这一位上统一的操作数最小，那么实际就是总的操作数尽可能的小，那么根节点自然是不动最好，后面的点如果与根节点相同（只是这一位上的01值相同），那么自然不用操作，或者操作偶数次（因为它前面可能有祖宗节点被操作了，那么会影响它的操作次数），如果与根节点不同，那么就需要操作奇数次。对于每个点的操作次数，我们单独来考虑，它的祖宗节点被操作了，我们可以累加到它上面去。相当于树上dp。

那么我们对于以某个点为根的某一位的操作情况就讨论清楚了，那么对于以这个点为根得到的结果的影响就是（1<<b）*dp[i]求和(b是二进制的位数，i是节点数)，因为我们对于单点来说具体操作多少次就讨论清楚了，那么每个单点的操作次数已知，而且用来操作的c也是定好的，那么整棵树的这一位产生的花费就求出来了。如果我们以每个节点为根对于它的每一位都这么处理一次，那么问题不就解决了，我开始也是这么以为的，但是不改变代码框架的各种优化都试了之后仍然超时让我只能开始分析时间复杂度，dfs的时间复杂度好像是n，所以整体的时间复杂度高了，就超时了。那么就要来考虑优化，首先有一点能够确定，就是张图一定得遍历一遍，不然根本不知道图的情况。不能每个点都遍历，但是又要知道从每个点出发的遍历情况，那么我们就要考虑，能不能由一个点的情况去推其他点的情况，我们进行如下讨论：

我们从普遍的意义上来看一下，两个点p,q,p是父节点，且p处的结果已知，我们要得到q处的结果ansp。我们来看，

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

如果去掉p，q,那么就有两个子树，我们将左子树全部统一成p对结果的贡献假设是m1,将右子树全部统一成q的贡献假设是m2，那么p处的ansp=m1+m2+opq*sq;q处的ansq=m1+m2+opp*sp(opq是将q变成p的c，opp是将p变成q的c，它俩实际相等c=q^p),所以ansq=ansp-opq*sq+opp*sp=ansp-c*sq+c*sp,所以我们只要能得到子树大小即可，这个很好处理，我们在dfs的时候就可以顺便统计出sq，那么sq=n-sq.至此问题解决。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int h[200010],ne[400010],e[400010],idx,v[200010],dp[200010][30],n,s[200010];
int fa[200010];
int ans,p[200010];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int x,int f,int r)//r是根
{
	//dp表示&1的次数
	int vu=v[x];
	fa[x]=f;
	for(int i=0;i<20;i++)
	{
		if(x==f) dp[x][i]=0;
		else 
		{
			dp[x][i]=dp[f][i];
			if((vu&(1<<i))==(r&(1<<i))) //偶数次
			{
				if(dp[x][i]%2) dp[x][i]++;
			}
			else//奇数次
			{
				if(dp[x][i]%2==0) dp[x][i]++;
			}
		}
		ans += (long long)(1<<i)*dp[x][i];
	}
//	ans += (1ll<<b)*dp[x];
	s[x]=1;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j!=f)
		{
			s[x]+=dfs(j,x,r);//子节点本身及它的子节点
		}
	}
	return s[x];
}
void re(int x,int f)
{
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j!=f)
		{
			int q=v[x]^v[j];
			int l=n-s[j];
			p[j]=p[x]-q*s[j]+q*l;
			re(j,x);
		}
	}
}
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&n);
		idx=0;
		for(int i=1;i<=n;i++) h[i]=-1,scanf("%lld",&v[i]);
		for(int i=1;i<n;i++)
		{
			int a,b;
			scanf("%lld%lld",&a,&b);
			add(a,b),add(b,a);
		}
		ans=0;
		dfs(1,1,v[1]);
		printf("%lld ",ans);
		p[1]=ans;
		re(1,1);
		for(int i=2;i<=n;i++) printf("%lld ",p[i]);
		printf("\n");
	}
}

ps：这道题的核心是两个点，首先从一个节点出发的结果怎么算，这里我们是从二进制的角度去看每一位，将每一位的01都建一棵树，然后发现一个操作是影响后面的，那么后面的实际操作数就可以由前面的转移而来，我们每一次操作的c确定（因为只看一位，只有异或上1才是有效操作）然后在这一位上的所有操作对于结果的贡献就可以算出，然后将每一位都算出来，就可以得到以这个节点为根得到的结果。然后因为不能每个点都遍历一遍，所以我们要考虑怎么由已知到未知，这里的转化是去找已知的那个点与它的子节点的关系。我们通过将树断成两半，两半分别统一了，那么操作就在两半的根节点之间转化。可以推出我们想要的结果。

另外，当多种独立情况复合后的时间复杂度超时的时候，一定要考虑这些独立情况之间能不能相互转化。由已知推未知。