2022-2-26 个人排位赛1

本文主要是介绍2022-2-26 个人排位赛1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2022-2-26 个人排位赛1

A An (Almost) Perfect Match

没读，不知道

B Good Coin Denomination

题意

给定一个上升序列，问这个序列是否满足每个数都是前一个数的两倍多。
第一个输入，多组样例数，每行先输入这个上升序列的个数，再输入上升序列的每个数。

输入

2
4 1 5 10 25
3 1 5 6

输出

Denominations: 1 5 10 25
Good coin denominations!Denominations: 1 5 6
Bad coin denominations!

Solution

直接暴力比大小即可

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
int t;
int n;
int a[20],b[20];
int main()
{cin>>t;while(t--){cin>>n;bool flag=true;for(int i=0;i<n;i++){cin>>a[i];if(i>0){if(a[i]*1.0/a[i-1]<2)flag=false;}}cout<<"Denominations:";for(int i=0;i<n;i++)cout<<" "<<a[i];cout<<endl;if(flag)cout<<"Good coin denominations!"<<endl;else cout<<"Bad coin denominations!"<<endl;cout<<endl;}return 0;
}

C Cameron’s Crazy Circles

题意

多组样例 t，给定直角三角形的直角边 L1，L2，先在直角三角形内画一个内切圆，再在之后接连画圆，之后的这些圆都与斜边、前一个圆、一条直角边相切。问所有圆的面积和与三角形的比值是多少？

输入

2
3 4
12 16

输出

Case #1: 0.7171Case #2: 0.7171

Solution

在这里插入图片描述

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f
const double pi=acos(-1);
int a,b;
int t;
int main()
{scanf("%d",&t);for(int cas=1;cas<=t;cas++){scanf("%d%d",&a,&b);double c=sqrt(a*a+b*b);double r=(a+b-c)/2.0;double degree=atan(1.0*a/b)/2.0;double h=(b-r)/cos(degree)-r;double r1=h*sin(degree)/(1+sin(degree));double h1=h-2*r1;double rate=pi*r1*r1/((h1+h)*tan(degree)*2*r1);double res=(pi*r*r+rate*(h*h*tan(degree)))/(a*b/2.0);printf("Case #%d: %.4f\n\n",cas,res);}return 0;
}

D Matrix Transformation

题意

给定一个 $\times C$ 的矩阵，对其中任意相邻的两个值进行同时加1 或减1 操作（其中相邻值的是水平线上相邻或竖直线上相邻），问能否将整个矩阵的值变为0,。

输入

输出

Case #1: YESCase #2: NOCase #3: NOCase #4: YESCase #5: NOCase #6: YES

Solution

先对矩阵的每一行进行处理，将除最后一列外的所有值都通过加减1操作变为0。
再对最后一列进行处理，使除最后一行外的所有值都通过加减1操作变为0。
最后根据矩阵右下角的值的结果输出YES和NO。

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
int t;
int n,m;
int a[35][35];
int main()
{scanf("%d",&t);for(int cas=1;cas<=t;cas++){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&a[i][j]);for(int i=0;i<n;i++){for(int j=1;j<m;j++)a[i][j]-=a[i][j-1];}for(int i=1;i<n;i++)a[i][m-1]-=a[i-1][m-1];if(a[n-1][m-1]==0)printf("Case #%d: YES\n",cas);else printf("Case #%d: NO\n",cas);printf("\n");}return 0;
}

E Cut the Cake!

题意

对一个蛋糕进行水平切开，将蛋糕分成两部分，问这两部分的周长分别为多少
多组样例，给定点数 V 和水平线位置Y，逆时针给出所有点坐标。

输入

输出

Case #1: 12.000 12.000Case #2: 25.690 35.302

Solution

在这里插入图片描述

通过图可以看出来，跟多边形与水平线的交点对答案的贡献是要对所有交点的x坐标进行排序后，两个两个进行减法操作。
其余的周长都是根据线段在Y上还是Y下分开进行计算。

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f
int x[20],y[20];
double dis(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
vector<double>e;
int main()
{int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){int n,k;scanf("%d%d",&n,&k);e.clear();double a=0,b=0;for(int i=0;i<n;i++){scanf("%d%d",&x[i],&y[i]);}x[n]=x[0];y[n]=y[0];for(int i=1;i<=n;i++){if((k-y[i-1])*(k-y[i])<0){double xx=1.0*(x[i]-x[i-1])*abs(k-y[i-1])/abs(y[i]-y[i-1]);xx+=x[i-1];e.push_back(xx);if(k<y[i-1])b+=dis(x[i-1],y[i-1],xx,k);else a+=dis(x[i-1],y[i-1],xx,k);if(k<y[i])b+=dis(x[i],y[i],xx,k);else a+=dis(x[i],y[i],xx,k);}else if(k==y[i-1]&&k==y[i]){e.push_back(x[i-1]);e.push_back(x[i]);}else if(k==y[i-1]){if(k<y[i])b+=dis(x[i],y[i],x[i-1],y[i-1]);else a+=dis(x[i],y[i],x[i-1],y[i-1]);e.push_back(x[i-1]);}else if(k==y[i]){if(k<y[i-1])b+=dis(x[i],y[i],x[i-1],y[i-1]);else a+=dis(x[i],y[i],x[i-1],y[i-1]);e.push_back(x[i]);}else if(k<y[i]&&k<y[i-1])b+=dis(x[i],y[i],x[i-1],y[i-1]);else a+=dis(x[i],y[i],x[i-1],y[i-1]);}if(e.size()>0){sort(e.begin(),e.end());for(int i=1;i<e.size();i+=2){a+=abs(e[i]-e[i-1]);b+=abs(e[i]-e[i-1]);}}if(a>b)swap(a,b);printf("Case #%d: %.3f %.3f\n\n",cas,a,b);}return 0;
}

F Camp Out

题意

多组样例，n个人要管理帐篷一周即168小时，现在把每天分成 6个时间段（12am-4am, 4am-8am, 8am-12pm, 12pm-4pm, 4pm-8pm, and 8pm-12am），每个时间段都要有三个人管理帐篷，且每个人管理帐篷的时间不超过80小时。问是否存在一个管理方案满足要求。

输入

2
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
6 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24
5 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24
4 1 0 24 2 0 24 3 0 24 4 0 24
4 1 0 24 2 0 24 3 0 24 4 0 23
1 1 0 24
2 1 10 12 2 3 7
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
7 1 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 1 7 0 1
7 1 1 2 2 1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 2
1 2 1 2
1 3 1 2
1 4 1 2
1 5 1 2
1 6 1 2
1 7 1 2
1 2 2 3
1 2 3 4

输出

Case #1: NOCase #2: YES

Solution

网络流建图。
判断最大流是否满足 $\times 168$
在这里插入图片描述

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f
int head[1005];
int cur[1005];
int deep[1005];
int cnt;
int n;
int S,T;
int vis[10][30];
struct Edge
{int to,w,next;
}edge[1005];
void init()
{memset(head,-1,sizeof head);cnt=0;
}
void add_edge(int u,int v,int w)
{edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
int dfs(int u,int flow)
{if(u==T)return flow;for(int &i=cur[u];i!=-1;i=edge[i].next){if(deep[edge[i].to]==deep[u]+1&&edge[i].w!=0){int d=dfs(edge[i].to,min(flow,edge[i].w));if(d>0){edge[i].w-=d;edge[i^1].w+=d;return d;}}}return 0;
}
int bfs()
{queue<int>q;while(!q.empty())q.pop();memset(deep,0,sizeof deep);deep[S]=1;q.push(S);do{int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){if(deep[edge[i].to]==0&&edge[i].w>0){deep[edge[i].to]=deep[u]+1;q.push(edge[i].to);if(edge[i].to==T)return 1;}}}while(!q.empty());if(deep[T]>0)return 1;return 0;
}
int Dinic()
{int ans=0;while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];while(int d=dfs(S,INF)){ans+=d;}}return ans;
}
int main()
{int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){init();S=1,T=54;for(int i=1;i<=10;i++){add_edge(S,i+1,80);add_edge(i+1,S,0);int n;scanf("%d",&n);memset(vis,0,sizeof vis);for(int j=0;j<n;j++){int d,s,e;scanf("%d%d%d",&d,&s,&e);for(int k=s+1;k<=e;k++)vis[d][k]=1;}for(int j=1;j<=7;j++){for(int k=0;k<6;k++){if(vis[j][k*4+1]+vis[j][k*4+2]+vis[j][k*4+3]+vis[j][k*4+4]>0)continue;add_edge(i+1,12+6*(j-1)+k,4);add_edge(12+6*(j-1)+k,i+1,4);}}}for(int i=12;i<=53;i++)add_edge(i,T,12),add_edge(T,i,0);int ans=Dinic();//cout<<ans<<endl;if(ans==3*168)printf("Case #%d: YES\n\n",cas);else printf("Case #%d: NO\n\n",cas);}return 0;
}

G Sorry About That, Chief!

题意

多组样例，给定一个数 n，判断 n是否是素数，或者其离最近的素数的距离是多少。

输入

输出

Input value: 23
Would you believe it; it is a prime!Input value: 25
Missed it by that much (2)!Input value: 22
Missed it by that much (1)!Input value: 10000
Missed it by that much (7)!

Solution

素数筛一下（裸题）。

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
int t,n;
const int N=1e4+10;
int prime[10015];
int vis[10015];
int cnt=0;
int main()
{vis[1]=1;for(int i=2;i<=N;i++){if(!vis[i])prime[cnt++]=i;for(int j=0;j<cnt&&1ll*i*prime[j]<=N;j++){vis[i*prime[j]]=1;if(i%prime[j]==0)break;}}scanf("%d",&t);while(t--){scanf("%d",&n);printf("Input value: %d\n",n);if(!vis[n])printf("Would you believe it; it is a prime!\n");else{int pos=lower_bound(prime,prime+cnt,n)-prime;int d=INF;if(pos<cnt)d=prime[pos]-n;if(pos>0)d=min(d,n-prime[pos-1]);printf("Missed it by that much (%d)!\n",d);}printf("\n");}return 0;
}

H Knight Moves – Gold Edition

题意

多组样例，问在一个 $\times N$ 的棋盘中，能否从(R1，C1)走到(R2，C2)，并且只能以下方式走，比如从(A，B)能走到，(A-2,B -1), (A-2, B+1), (A+2,
B-1), (A+2, B+1), (A-1, B-2), (A+1,B-2), (A-1, B+2) or (A+1, B+2)这几个点。题目保证一定能走到，问最少走几步。

输入

2
5 1 1 2 3
5 1 1 2 2

输出

Case #1: 1Case #2: 4

Solution

搜索裸题。

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f
int dx[]={-2,-2,2,2,-1,-1,1,1},dy[]={1,-1,1,-1,2,-2,2,-2};
int d[50][50];
int n,sx,sy,tx,ty;
void bfs()
{memset(d,INF,sizeof(d));d[sx][sy]=0;queue<P>q;q.push(P(sx,sy));while(!q.empty()){P p=q.front();q.pop();if(d[tx][ty]!=INF)return;for(int i=0;i<8;i++){int x=p.first+dx[i];int y=p.second+dy[i];if(x<1||x>n||y<1||y>n)continue;if(d[x][y]<d[p.first][p.second]+1)continue;d[x][y]=d[p.first][p.second]+1;q.push(P(x,y));}}
}
int main()
{int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){scanf("%d%d%d%d%d",&n,&sx,&sy,&tx,&ty);bfs();printf("Case #%d: %d\n\n",cas,d[tx][ty]);}return 0;
}

I Knight Moves – Black Edition

不会

J A Prickly Problem – Gold Edition

题意

K题数据简单版。

K A Prickly Problem – Black Edition

题意

给定一颗仙人掌，里面只有简单环，问能形成多少棵生成树。

输入

输出

Case #1: 3Case #2: 9Case #3: 1

Solution

套生成树板子即可。

但是我用了另一种方法。
答案其实就是将所有简单环的边数相乘。
如何计算每个环的边数，使用LCA的性质，边数就是depth[x]+depth[y]-2*depth[lca]+1

代码

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f
const int N=5e4+5;
const int mod=1007;
int n,m;
int f[N];
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
vector<int>e[N];
vector<P>g;
int u,v;
int res;
int depth[N];
int fa[N][20];
void bfs()
{for(int i=0;i<=n;i++)depth[i]=INF;queue<int>q;q.push(1);depth[1]=1;depth[0]=0;while(!q.empty()){int t=q.front();q.pop();for(auto to:e[t]){if(depth[to]>depth[t]+1){depth[to]=depth[t]+1;q.push(to);fa[to][0]=t;for(int j=1;j<=19;j++){fa[to][j]=fa[fa[to][j-1]][j-1];}}}}
}
int lca(int x,int y)
{if(depth[x]<depth[y])swap(x,y);for(int i=19;i>=0;i--){if(depth[fa[x][i]]>=depth[y])x=fa[x][i];}if(x==y)return x;for(int i=19;i>=0;i--){if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];
}
int main()
{int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){scanf("%d%d",&n,&m);res=1;g.clear();for(int i=1;i<=n;i++){f[i]=i;e[i].clear();}for(int i=0;i<m;i++){scanf("%d%d",&u,&v);int x=Find(u),y=Find(v);if(x==y){g.push_back(P(u,v));}else{f[x]=y;e[u].push_back(v);e[v].push_back(u);}}bfs();for(auto p:g){u=p.first;v=p.second;int Lca=lca(u,v);//cout<<u<<' '<<v<<' '<<Lca<<endl;//cout<<depth[u]<<' '<<depth[v]<<' '<<depth[Lca]<<endl;res=res*(depth[u]+depth[v]-2*depth[Lca]+1)%mod;}printf("Case #%d: %d\n\n",cas,res);}return 0;
}