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");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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");
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

反思：

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

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
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

反思

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