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

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

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

• 如果 a i − 1 ∈ A a_{i-1}in A ai−1​∈A， a i > a i − 1 a_i>a_{i-1} ai​>ai−1​， d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] dp[i][0]=dp[i-1][0] dp[i][0]=dp[i−1][0]
• 如果 a i − 1 ∈ A a_{i-1}in A ai−1​∈A， a i < a i − 1 a_iai​
• 如果 a i − 1 ∈ B a_{i-1}in B ai−1​∈B， a i > d p [ i − 1 ] [ 1 ] a_i>dp[i-1][1] ai​>dp[i−1][1]， d p [ i ] [ 0 ] = a i − 1 dp[i][0]=a_{i-1} dp[i][0]=ai−1​
• 如果 a i − 1 ∈ B a_{i-1}in B ai−1​∈B， a i < d p [ i − 1 ] [ 1 ] a_i

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

#include
#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];
vectorv[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
		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");
}

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

如果 α + β ≥ γ alpha+betage gamma α+β≥γ则可以撞到
其中
cos ⁡ α = 2 ∗ 2 O 1 O 2 cos ⁡ β = O 2 O 2 ′ O 2 O 3 ′ cos ⁡ γ = O 1 O 2 → ⋅ O 2 O 3 → ∣ O 1 O 2 ∣ ∣ O 2 O 3 ∣ cos ⁡ ( α + β ) = cos ⁡ α cos ⁡ β − sin ⁡ α sin ⁡ β cosalpha=frac{2*2}{O_1O_2} \ cosbeta=frac{O_2O_2^{'}}{O_2O_3^{'}} \ cosgamma=frac{overrightarrow{O_1O_2}·overrightarrow{O_2O_3}}{|O_1O_2||O_2O_3|} \ cos(alpha+beta)=cosalphacosbeta-sinalphasinbeta cosα=O1​O2​2∗2​cosβ=O2​O3′​O2​O2′​​cosγ=∣O1​O2​∣∣O2​O3​∣O1​O2​ ​⋅O2​O3​ ​​cos(α+β)=cosαcosβ−sinαsinβ

#include
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");
    }
}

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

#include
#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");
}