当前位置:网站首页>UCF(2022暑期团队赛一)
UCF(2022暑期团队赛一)
2022-07-06 05:11:00 【.Ashy.】
文章目录
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 写循环时一定要注意循环条件的转换,很重要
边栏推荐
- 你需要知道的 TCP 三次握手
- What are the advantages of the industry private network over the public network? What specific requirements can be met?
- GAMES202-WebGL中shader的编译和连接(了解向)
- Postman测试报告
- Class inheritance in yyds dry inventory C
- Modbus协议通信异常
- Bill Gates posted his 18-year-old resume and expected an annual salary of $12000 48 years ago
- Postman test report
- Idea one key guide package
- 集合详解之 Map + 面试题
猜你喜欢
Leetcode dynamic planning day 16
Postman assertion
Implementing fuzzy query with dataframe
Programmers' position in the Internet industry | daily anecdotes
Weng Kai C language third week 3.1 punch in
Microblogging hot search stock selection strategy
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
idea一键导包
麦斯克电子IPO被终止:曾拟募资8亿 河南资产是股东
Ora-01779: the column corresponding to the non key value saving table cannot be modified
随机推荐
趋势前沿 | 达摩院语音 AI 最新技术大全
Simple understanding of interpreters and compilers
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Postman manage test cases
Collection + interview questions
What are the advantages of the industry private network over the public network? What specific requirements can be met?
Idea one key guide package
Implementing fuzzy query with dataframe
MPLS experiment
Select knowledge points of structure
Nacos - TC Construction of High available seata (02)
2021 robocom world robot developer competition - undergraduate group (semi-finals)
TCP three handshakes you need to know
Summary of redis basic knowledge points
[lgr-109] Luogu may race II & windy round 6
Fuzzy -- basic application method of AFL
ORM aggregate query and native database operation
Sorting out the knowledge points of multicast and broadcasting
pix2pix:使用条件对抗网络的图像到图像转换