[数据结构与算法]第十七届黑龙江省大学生程序设计竞赛

C.Tree Division

题意：
有一颗$n(1\le n\le 10^5)$个节点的树，树上每个位置都有一个值$a_i$，将树上的节点分入$A,B$两个集合，要求以$1$为根节点的树，能否使集合$A$在树链上递增，集合$B$在树链上递减。
思路：
考虑如果在单个直线数组上进行这个问题怎么办。
如果我们可以在每次将一个数字放入任意个集合后，都可以知道两个集合里最后放入的数字的大小，那么我们就可以用动态规划来维护。
将第$i$个数字放入$A$集合，此时集合$A$的最后一项显然为$a_i$，如果用$dp[i][0]$表示$B$集合最后一项的位置，问题显然就得到了解决。
由于$B$数组递减，在我们知道$a_i$被放入了集合$A$，且有合理的构造后，前$i?1$项具体如何分配对我们来说已经不重要，我们只想贪心的让集合$B$的最后一项尽可能的大。
于是$dp$转移如下：

• 如果$a_{i?1}\in A$，$a_i>a_{i?1}$，$dp[i][0]=dp[i?1][0]$
• 如果$a_{i?1}\in A$，$a_i<a_{i?1}$，无解
• 如果$a_{i?1}\in B$，$a_i>dp[i?1][1]$，$dp[i][0]=a_{i?1}$
• 如果$a_{i?1}\in B$，$a_i<dp[i?1][1]$，无解

对于放入$B$集合的情况与上同理。
现在问题回到树上，只需要将每条树链都视为一个数组即可。
请注意：不要使用先序遍历，因为树上节点有多个分叉，直接转移可能会错误的将一个节点用两种情况分别计算。
为了避免这种情况，使用后续遍历，一个节点最多只有一个父节点，就解决了上述问题

#include<bits/stdc++.h>
#define pb push_back
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=1e5+7;
int n,a[maxn],f[maxn][2];
vector<int>v[maxn];
void dfs(int u,int fa)
{
	f[u][1]=inf;f[u][0]=-inf;
	for(int i:v[u])
	{
		if(i==fa) continue;
		dfs(i,u);
		int t1;
		//放进集合A
		//a[i]被放在集合A中
		if(a[u]<=a[i]) t1=f[i][0];
		else t1=inf;
		//a[i]被放在集合B中
		if(a[u]<=f[i][1]) t1=min(t1,a[i]);
		else t1=min(t1,inf);
		f[u][0]=max(f[u][0],t1);
		
		//放进集合B
		//a[i]被放在集合B中
		if(a[u]>=a[i]) t1=f[i][1];
		else t1=-inf;
		//a[i]被放在集合A中
		if(a[u]>=f[i][0]) t1=max(t1,a[i]);
		else t1=max(t1,-inf);
		f[u][1]=min(f[u][1],t1);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		v[a].pb(b);v[b].pb(a);
	}
	dfs(1,-1);
	if(f[1][0]!=inf || f[1][1]!=-inf)
	{
		puts("YES");
	}
	else puts("NO");
}

D.Collision Detector

题意：
三个小球，在平面上视为$3$个半径为$1$的圆$O_1,O_2,O_3$，现在小球$O_1$有任意方向的初速度，如果它能够碰到小球$O_2$，$O_2$则会因为碰撞有垂直于$O_1,O_2$切线方向的速度，给你三个求得坐标$x,y$，问是否有可能使$O_2$碰撞到$O_3$
思路：

如果$\alpha +\beta \ge \gamma$则可以撞到
其中
$$\begin{gathered} \cos \alpha =\frac{2?2}{O_1{O}_2} \\ \cos \beta =\frac{O_2{O}_2^{{}^{\prime }}}{O_2{O}_3^{{}^{\prime }}} \\ \cos \gamma =\frac{O_1{O}_2?O_2{O}_3}{|O_1{O}_2||O_2{O}_3|} \\ \cos (\alpha +\beta )=\cos \alpha \cos \beta ?\sin \alpha \sin \beta \end{gathered}$$

#include<bits/stdc++.h>
using namespace std;
struct Vector
{
	double x,y;
};
double muti(Vector a,Vector b)
{
	return a.x*b.x+a.y*b.y;
}
double eps=1e-8;
int main()
{
	 int T;
    scanf("%d",&T);
    while(T--)
    {
        double x1,y1,x2,y2,x3,y3;
        cin>>x1>>y1>>x2>>y2>>x3>>y3;
        double dis12=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
		double dis23=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
		double d1=sqrt(dis23*dis23-4),d2=sqrt(dis12*dis12-4);
		double cosa=2/dis12,cosb=d1/dis23,sina=d2/dis12,sinb=2/dis23;
		Vector ab={x2-x1,y2-y1},bc={x3-x2,y3-y2};
		double cosc=muti(ab,bc)/dis12/dis23;
		double cosab=cosa*cosb-sina*sinb;
		if(cosc-cosab>eps) puts("yes");
		else puts("no");
    }
}

G.Chevonne’s Necklace

题意：
给你$n(1\le n\le 2000)$个数字围成的环，环上的数字$a_i(0\le a_i\le 2000)$表示可以顺时针正好删除接下来的包括自己的$a_i$个数字，$1$只能删除自己，$0$不能选取。问最多能删除多少个数字，有多少种最多删除数量的方案？
思路：
如果可以选出$k$个数字$\sum a\le n$，那么根据鸽巢原理，一定有一种顺序可以互不影响，完美的带走$\sum a$个数字。
所以接下来只要一个$01$背包统计方案数即可。

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2005;
int n,c[maxn],c1[maxn],f[maxn][maxn];
int mod=998244353;
signed main()
{
	scanf("%lld",&n);
	int cnt=0;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&c[i]);
		if(c[i])
		{
			c1[++cnt]=c[i];
		}
	}
	f[0][0]=1;
	for(int i=1;i<=cnt;i++)
	{
		for(int j=0;j<=n;j++)
		{
			f[i][j]=f[i-1][j];
			if(j>=c1[i]) f[i][j]+=f[i-1][j-c1[i]];
			f[i][j]%=mod;
		}
	}
	for(int i=n;i>=1;i--)
	{
		if(f[cnt][i])
		{
			printf("%lld %lld",i,f[cnt][i]);return 0;
		}
	}
	puts("0 0");
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系