Codeforces Round #831 (Div. 1 + Div. 2)

A. Factorise N+M

题目链接：Dashboard - Codeforces Round #831 (Div. 1 + Div. 2) - Codeforces

样例输入： 

3
7
2
75619

样例输出：

2
7
47837

题意：给定一个质数，让我们输出一个质数使得这两个数相加为一个合数。

分析：很显然直接输出给定的质数即可，这样两个质数相加一定是一个偶数，而且不是2，所以肯定是一个合数。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		printf("%d\n",n);
	}
	return 0;
} 

B. Jumbo Extra Cheese 2

题目链接：Problem - B - Codeforces

样例输入： 

3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65

样例输出：

26
24
134

题意：给定一个n代表矩形数目，每个矩形给定一个长和高，我们可以对这个矩形进行旋转，然后让一边贴至数轴上，另一边与一个矩形的一条边重合，问这样最后拼成的多边形的周长最少是多少

分析：我们的目的就是尽可能地让两个矩形重合的边的长度最大，这样可以使得不被计算的长度最大，那么我们可以让每个矩形中长和高中的较大值作为高，然后把所有的矩形按照高度进行排序，然后依次拼接即可，最后发现周长就是所有矩形的长的和*2+矩形中的最大高*2.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int a,b;
		int mxh=0;
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&a,&b);
			if(a>b) swap(a,b);
			mxh=max(mxh,b);
			ans+=a*2;
		}
		printf("%lld\n",ans+mxh*2);
	}
	return 0;
}

C. Bricks and Bags

题目链接：Problem - C - Codeforces

样例输入： 

3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265

样例输出：

6
63
0

题意：给定一个n代表砖块数量，每个砖块有一个重量，现在有3个包，我们可以把每块砖块放至在3个包中的任何一个，但要保证每个包中最后至少要有一块砖块，一个人负责把砖块分配到每个包中，另一个人负责从每个包中分别取出一块砖块，不妨设取出的三块转的重量分别是wi,wj,wk，那么最后的结果就是|wi-wj|+|wj-wk|，现在分配砖块的人想要使得这个结果最小，而取砖块的人想要使得这个值最大，问这个值最少是多少。

分析：我们先对砖块进行排序，不难想到对于一个包中的砖块应该是重量最接近的一些砖块，只有这样才能使得后手操作后值的变化尽可能地小，因为这样无论取出哪一块砖的影响都不是特别大。比如我们按照重量拍排完序后的结果是w1,w2,……,wn,我们选择前i个放入第二个背包，然后将第i+1~n-1个砖块放入第一个背包，最后将第n个砖块单独放入第三个背包，这样显然结果等于|wi-wi+1|+|wi-wn|，我们只要遍历一遍取一次最大值即可。需要注意的一点是我们还应该倒序来一遍，因为有可能是重量最小的砖块单独放在三号包中。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		int ans=0;
		for(int i=1;i<n-1;i++)
			ans=max(ans,abs(a[i]-a[i+1])+abs(a[i]-a[n]));
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<n-1;i++)
			ans=max(ans,abs(a[i]-a[i+1])+abs(a[i]-a[n]));
		printf("%d\n",ans);
	}
	return 0;
}

D. Knowledge Cards

题目链接：Problem - D - Codeforces

样例输入：

4
3 3 6
3 6 4 1 2 5
3 3 10
1 2 3 4 5 6 7 8 9 10
5 4 4
2 1 3 4
3 4 10
10 4 9 3 5 6 8 2 7 1

样例输出：

YA
TIDAK
YA
YA

题意：给定一个n*m的方格网，一开始在(1,1)有k张卡片，每一张卡片有一个编号，是一个1~k的排列，我们要将这k张卡片全部移至(n,m)，而且要保证(n,m)处的卡片按照从下往上逐渐减小的顺序进行摆放，保证除了(1,1)和(n,m)之外的每个位置不能同时摆放两张卡片，而且我们只能从(1,1)进行取卡片，不能存卡片，只能向(n,m)进行存卡片，而不能取卡片。

分析：通过华容道游戏我们可以知道，整个方格网中只要有1个空余的格子，我们就可以将任何一个格子移动到任何一个我们想要移动的位置，所以问题就转化为我们取到当前想要移动到(n,m)的卡片时整个方格网中的空余方格数是多少，如果大于2就可以，否则不行，大于2是因为我们将我们当前要取的数移动至一个空格子后空格子的数目会少1，而我们要保证移动过程中始终有一个空格子，这个很好求，直接用set记录一下当前占用空余方格的数即可，因为在i放入(n,m)之前，原来在i上面的而且值小于i的卡片全部都在空余方格中，所以我们只要统计一下这些数的数目即可。

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int N=2e5+10;
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=k;i++)
			scanf("%d",&a[i]);
		set<int>s;
		bool flag=true;
		int l=1;
		for(int i=k;i>=1;i--)
		{
			if(s.find(i)==s.end())
			{
				while(a[l]!=i) s.insert(a[l++]);
				l++;
				if(s.size()>(n*m-4))
				{
					flag=false;
					break;
				}
			}
			else
				s.erase(i);
		}
		if(flag) puts("YA");
		else puts("TIDAK");
	}
	return 0;
}

E. Hanging Hearts

题目链接：Problem - E - Codeforces

样例输入： 

6
1 2 1 4 2

样例输出：

4

题意：有一棵有n个节点的树，我们需要给这n个节点一个点权，这n个点的点权是位于1~n的，而且两两不同。我们现在有一个空的数组s，每次我们选择一个叶子节点x进行以下操作：

把这个节点的权值加入到s数组的末尾

如果这个节点的点权小于父亲节点的点权那么就将父亲节点的点权改为这个节点的点权

删除节点x

求最后操作完所有的节点后的s数组中的最长非递减子序列的最大长度。

分析：我们通过分析简单的一些例子可以发现，如果操作完这个子树中的所有非根节点，那么这棵树的根节点的权值就是该树中所有子节点的权值的最小值。

那么有了这个性质我们就不难得到一些其他的结论：

（1）最长非递降序列中不可能同时取当前结点以及当前结点的两个及以上的子节点

（2）如果不取当前节点则可以取当前节点的所有子节点

为什么会有这样的结论呢？

比如说1号节点有两个子节点2和3，那么我们假如先操作完以2为根的子树中的全部节点，那么1的节点的点权就变为1号节点和以2为根的子树中所有节点的点权的最小值，这个时候我们需要讨论以2号节点为根的子树中的全部节点的点权最小值与1号节点的点权和以3号节点为根的子树中的全部节点的点权最小值的关系，三者是两两不同的，不妨假设三者的权值分别为w1,w2,w3，假设w2w2,

但是我们可以先取w2，再取w3，这个时候就去掉了1号节点的所有子节点，但是1号节点就没办法再作为有效长度了，因为每棵子树所能形成的序列是独立的，所以我们每次使得一棵子树中的所有节点的初始权值连续即可，同理可以分析其他情况，由于分析方法类似，这里就不一一证明了。

知道了这些性质，我们直接进行树形DP即可：

f[i][0]表示不选当前子节点所能得到的最长长度

f[i][1]表示选当前子节点所能得到的最长长度

更新节点i的所有子节点j，有：

f[i][0]+=max(f[j][0],f[j][1])

f[i][1]=max(f[i][1],f[j][1]+1)

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int h[N],e[N],ne[N],idx;
int f[N][2];
/*
f[i][0]表示不选当前子节点所能得到的最长长度
f[i][1]表示选当前子节点所能得到的最长长度 
 
最长非递降序列中不可能同时取当前结点以及当前结点的两个及以上的子节点 
如果不取当前节点则可以取当前节点的所有子节点 
*/
void add(int x,int y)
{
	e[idx]=y;
	ne[idx]=h[x];
	h[x]=idx++;
}
void dfs(int x)
{
	f[x][0]=0;f[x][1]=1;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		dfs(j);
		f[x][0]+=max(f[j][0],f[j][1]);
		f[x][1]=max(f[x][1],f[j][1]+1);
	}
	return ;
} 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) h[i]=-1;
	for(int i=2;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		add(t,i);
	}
	dfs(1);
	printf("%d",max(f[1][0],f[1][1]));
	return 0;
}