第十七届黑龙江省大学生程序设计竞赛

不是张胖胖

已于 2022-05-19 09:50:34 修改

阅读量1.9k

点赞数 11

分类专栏： XCPC省赛文章标签：动态规划算法深度优先几何学

于 2022-05-18 23:40:47 首次发布

本文链接：https://blog.csdn.net/zppbugmaker/article/details/124853048

版权

XCPC省赛专栏收录该内容

4 篇文章

订阅专栏

文章目录

C.Tree Division
D.Collision Detector
G.Chevonne's Necklace

比赛链接

C.Tree Division

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

如果 $a_{i-1}\in A$ ， $a_i>a_{i-1}$ ， $d p [i] [0] = d p [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$ 则可以撞到
其中
$\cos\alpha=\frac{2*2}{O_1O_2} \\ \cos\beta=\frac{O_2O_2^{'}}{O_2O_3^{'}} \\ \cos\gamma=\frac{\overrightarrow{O_1O_2}·\overrightarrow{O_2O_3}}{|O_1O_2||O_2O_3|} \\ \cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta$

#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\leq n \leq2000)$ 个数字围成的环，环上的数字 $a_i(0\leq a_i \leq 2000)$ 表示可以顺时针正好删除接下来的包括自己的 $a_i$ 个数字， $1$ 只能删除自己， $0$ 不能选取。问最多能删除多少个数字，有多少种最多删除数量的方案？
思路：
如果可以选出 $k$ 个数字 $\sum a\leq 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");
}