UCF (2022 summer team competition I)

B . Good Coin Denomination

Carelessness ：

give n A sequence of , Ask whether each sequence meets Each element is at least twice as big as the previous one ( Apart from the first element ) This nature
direct simulation And then determine that will do

#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( State compression )

Carelessness ：

Give a matrix , You can make adjacent elements at the same time Add 1 perhaps meanwhile reduce 1, Ask whether every element of the matrix is changed into 0

Ideas ：

If the matrix is not processed , There are too many and complex states that a matrix can transfer , Do not know how to start , We can move the non-zero elements of the matrix to the right to the last column through two operations , That is, compress the two-dimensional matrix into one , Then continue to compress the elements of this column to a point according to this idea , This last point cannot be operated with other elements , This point is 0 Matrix can be operated , This point is not 0 , The matrix cannot be changed into 0 matrix

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

reflection ：

This problem starts from the state transition without a clue, and I don't know where to start , To gradually compress one dimension , Compress to a point , Very good idea , Accumulate

E,Cut the Cake! ( Plane geometry )

Carelessness ：

Give a polygon use A straight line y = k To cut off , Find the circumference of the upper and lower parts of the cut

Ideas

First calculate the side length of the uncut part , Plus the side length of the public part , Then add the length of the cut part

#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  On  sum2  Next 

// The formula for calculating the distance between two points 
double dis(double x1,double y1,double x2,double y2)
{
    
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

// Calculation  y = k  The length of the cut part at the intersection with the figure 
void solve(double x1,double y1,double x2,double y2)
{
    
	double xx;

// According to the known two points, calculate the linear equation, bring in the ordinate, and calculate the abscissa 
// Be careful  x2=0 x1=x2  Two cases  , Very important  , The denominator cannot be  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);
		
		// Record two points on both sides of the split line 
		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;
		}
		
// Calculate the length of the undivided part in turn according to the found points 
		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;
			
		}
		
// Add the length of the divided part 
		
		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);
// Add the length of the public part 
		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);
// Output in order of size 
		printf("%.3lf %.3lf\n",min(sum1,sum2),max(sum1,sum2));
		
	}
}
/* 1 3 5 0 10 0 0 10 0 */

reflection

Pay attention to The denominator is not 0 Is a very important condition , The denominator must not be 0
use while When writing a loop, you must pay attention to the conversion of loop conditions , Very important