UCF(2022暑期团队赛一)

B . Good Coin Denomination

大意：

给出 n 个序列，问每个序列是否满足 每个元素至少是前一个元素的两倍(除第一个元素外) 这个性质
直接 模拟 然后判断 即可

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+10;

int n,t;

int a[N];

bool solve()
{
    
	for(int i=2;i<=n;i++)
	{
    
		double k=(double)a[i]/(double)a[i-1];
		if(k<2) return 0;
	}
	return 1;
}

int main()
{
    
	cin>>t;
	
	while(t--)
	{
    
		cin>>n;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		if(solve()) puts("0");
		else puts("1");
	}
}

D . Matrix Transformation(状态压缩)

大意 ：

给出一个矩阵，可以使相邻的元素同时 加 1 或者 同时 减 1，问是否通过无限次操作使矩阵的每一个元素都变为 0

思路：

如果不对矩阵进行处理，矩阵可以转移的状态数太多太复杂，无从下手，我们可以通过两种操作把矩阵的非零元素右移到最后一列，即把矩阵的二维压缩成一，然后继续按照这个思路把这一列的元素压缩到一个点上，最后这个点不可与其他元素进行操作，这个点为 0 矩阵即可操作，这个点非 0 ，矩阵则不可变为 0 矩阵

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+10;

int t,n,m;

int a[51][51];

int main()
{
    
	cin>>t;
	
	while(t--)
	{
    
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
    
			for(int j=1;j<=m;j++)
			{
    
				scanf("%d",&a[i][j]);
				if(j>1)
				{
    
					a[i][j]-=a[i][j-1];
				}
			}
		}
		for(int i=2;i<=n;i++)
		{
    
			a[i][m]-=a[i-1][m];
		}
		
		if(!a[n][m]) puts("0");
		else puts("1");
		
	}
}

反思：

这个题从毫无头绪的状态转移不知从哪里开始，到逐渐的压缩一维，压缩到一个点，思路非常的好，积累下来

E，Cut the Cake! (平面几何)

大意 ：

给出一个多边形 用 直线 y = k 去截， 求截的的上下两部分的周长

思路

先算未被切开部分的边长，加上公共部分的边长 ，然后各自加上截下部分的长度

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+10;

int n,y;
int id[5];
struct node{
    
	double x,y;
}a[20],n1[5],d[3];

int cntn,cnts,t;


double sum1,sum2;//sum1 上 sum2 下

//计算两点间距离公式
double dis(double x1,double y1,double x2,double y2)
{
    
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

//计算 y = k 与图形交点切开部分的长度
void solve(double x1,double y1,double x2,double y2)
{
    
	double xx;

//根据已知两点求出直线方程带入纵坐标算出横坐标
//注意 x2=0 x1=x2 两种情况 ，很重要 ，分母不能为 0
	if(x2==0) xx=(y-y2)/((y1-y2)/x1);
	else
	if(x1==x2) xx=x1;
	else xx=(y-((y1-(x1/x2)*y2)/(1-x1/x2)))/((y1-y2)/(x1-x2));
	

	if(y1>y) sum1+=dis(xx,y,x1,y1);
	else sum2+=dis(xx,y,x1,y1);
	
	if(y2>y) sum1+=dis(xx,y,x2,y2);
	else sum2+=dis(xx,y,x2,y2);
	
	d[++cnts].x=xx;
	d[cnts].y=y;
		
}

int main()
{
    
	cin>>t;
	
	while(t--)
	{
    
		cin>>n>>y;
		
		cntn=0;cnts=0;
		sum1=sum2=0;
		for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
		
		//记录下被分割直线的两侧两个点
		for(int i=1;i<n;i++)
		{
    
			if(a[i].y>y&&a[i+1].y<y||a[i].y<y&&a[i+1].y>y)
			{
    
				n1[++cntn].x=a[i].x;
				n1[cntn].y=a[i].y;
				id[cntn]=i;
				n1[++cntn].x=a[i+1].x;
				n1[cntn].y=a[i+1].y;
				id[cntn]=i+1;
			}
		}
		
		if(a[n].y>y&&a[1].y<y||a[n].y<y&&a[1].y>y)
		{
    
			n1[++cntn].x=a[n].x;
			n1[cntn].y=a[n].y;
			id[cntn]=n;
			n1[++cntn].x=a[1].x;
			n1[cntn].y=a[1].y;
			id[cntn]=1;
		}
		
//根据找到的点依次计算未被分割部分的长度
		int idd1=id[2];
		int idd2;
		
		if(idd1==n) idd2=1;
		else idd2=idd1+1;
		
		
		while(idd1!=id[3])
		{
    
			
			if(a[idd1].y>y)
			sum1+=dis(a[idd1].x,a[idd1].y,a[idd2].x,a[idd2].y);
			else
			sum2+=dis(a[idd1].x,a[idd1].y,a[idd2].x,a[idd2].y);
			idd1++;
			if(idd1==n+1) idd1=1;
			idd2=idd1+1;
			if(idd1==n) idd2=1;
		}
		int idd3=id[4];
		int idd4;
		
		if(idd3==n) idd4=1;
		else idd4=idd3+1;
		
		while(idd3!=id[1])
		{
    
			if(a[idd3].y>y)
			sum1+=dis(a[idd3].x,a[idd3].y,a[idd4].x,a[idd4].y);
			else
			sum2+=dis(a[idd3].x,a[idd3].y,a[idd4].x,a[idd4].y);
			idd3++;
			if(idd3==n+1) idd3=1;
			idd4=idd3+1;
			if(idd3==n) idd4=1;
			
		}
		
//加上被分割部分的长度
		
		solve(a[id[1]].x,a[id[1]].y,a[id[2]].x,a[id[2]].y);
		solve(a[id[3]].x,a[id[3]].y,a[id[4]].x,a[id[4]].y);
//加上公共部分的长度
		sum1+=dis(d[1].x,d[1].y,d[2].x,d[2].y);
		sum2+=dis(d[1].x,d[1].y,d[2].x,d[2].y);
//按大小关系依次输出
		printf("%.3lf %.3lf\n",min(sum1,sum2),max(sum1,sum2));
		
	}
}
/* 1 3 5 0 10 0 0 10 0 */

反思

在求直线方程时注意 分母不为 0 是十分重要的条件，分母一定不能为 0
用 while 写循环时一定要注意循环条件的转换，很重要