2021 GDCPC广东省大学生程序设计竞赛（正式赛）

2021 GDCPC广东省大学生程序设计竞赛（正式赛）

• A An Easy Problem（二分）
• D Double（贪心）
• G Good Game, GG
• I Industrial Nuclear Water（数学）
• J Jerry（bfs）
• L League of Legends（签到）

浅做一下gdcpc的题目

A An Easy Problem（二分）

题意，大概就是给定x,y,k，求i取1-x，j取1-y时ij第k大的指
题解：这题我用的是二分来解的，先枚举第k大的数p，然后就看看有多少个数比他小。怎么判断呢，这边讲一下原理，先举个例子，比6小的数中2的倍数的个数，很显然就是6/2，那么这里是ij的值，只需要枚举i,然后再通过p/i就知道比p小然后又是i的倍数的个数，就可以求出ij比p小的个数。当然，因为j范围是1-y，所以还要看y跟p/i谁更小。
原理会了，那么二分就是只用判断比p小的数是否是xy-k+1个就行了

#include
using namespace std;
#define ll long long
ll n,m,k;
bool check(ll x)
{ll res=0;for (int i=1;i<=n;i++){res+=min(m,x/i);}return res>=k;
}
int main()
{cin>>n>>m>>k;k=n*m-k+1;ll l=1,r=n*m;while(l<r){ll mid=l+r>>1;if (check(mid)) r=mid;else l=mid+1;}cout<<l<<endl;return 0;
}

D Double（贪心）

题意：大概就是说有n个人，每个人有一个战力值ai，然后在里面找出最后可能胜利到最后的人。至于比较，就是每个人只能跟相邻的人打，战力值大的人就能赢并且战力值会翻倍，而小的人就淘汰，相等的话就有50%的胜率（因为是求可能，所以直接当100%胜利就行了）。
题解：贪心，每个人跟左右两边比较，如果有比他小的就直接战力翻倍，看看能否赢到最后就行了

#include
using namespace std;
const int N=5e5+5;
#define ll long long
ll a[N];
ll maxa;
int cnt;
int b[N];
int main()
{int n;cin>>n;for (int i=0;i<n;i++) {cin>>a[i];maxa=max(a[i],maxa);}for (int i=0;i<n;i++){int j=i-1;int k=i+1;ll t=a[i];bool flag=true;while(flag){flag=false;if (j>=0 && a[j]<=t){t<<=1;j--;flag=true;}if (k<n && a[k]<=t){t<<=1;k++;flag=true;}if (t>=maxa) break;}if (j==-1 && k==n) b[cnt++]=i+1;else if (t>=maxa) b[cnt++]=i+1;}cout<<cnt<<endl;for (int i=0;i<cnt;i++) cout<<b[i]<<" ";return 0;
}

G Good Game, GG

题意：就是说有两个人搁这博弈，有n个数，A能将一个奇数分成两个正整数，或者将1删掉。B能将一个偶数分成两个正整数。两人都是用的最优解，谁先不能操作谁就输！
题解：首先先看看A的最优是怎么做。将一个奇数分成两个正整数的话，那就只能分成一个奇数和一个偶数，要对自己最有力那就是分成一个2和一个奇数。因为2只能再分成两个1，那就多了两个操作，而自己还有一个奇数能分。那么对于一个数x，A能够最多操作x/2+1次
B的最优就是将一个偶数分成两个偶数，那么就是最多操作x/2-1次
所以只需看看到最后谁的操作数最多。因为是A先，所以如果相等就是B赢

#include
using namespace std;
#define ll long long
int main()
{int T;cin>>T;while(T--){int n;cin>>n;ll cnt1=0,cnt2=0;for (int i=0;i<n;i++){ll x;cin>>x;if (x&1){cnt1+=x/2+1;}else cnt2+=x/2-1;}if (cnt1>cnt2) cout<<"Alice"<<endl;else cout<<"Bob"<<endl;}return 0;
}

I Industrial Nuclear Water（数学）

题意：有两个点（x,y,z）和六个面（因为是|X|所以是六个面），六个面是否将两个点分隔开
题意：判断六个面是否将两个点分隔开只需判断两个点是否在每个面的同一侧（这样就不会被分隔开）。先讲一下如何判断，在二维平面上判断两个点(a1,b1)(a2,b2)是否是在一条线(x²+y²=z)的同一侧，就要看看a1²+b1²和a2²+b2²跟z比较是否同时大于或同时小于或同时等于。换到三维也一样，只需判断a1²+b1²和a2²+b2²跟1000|c|的大小比较就行了

#include
using namespace std;
#define ll long long 
ll a[3],b[3];
bool func(ll a,ll b,ll c)
{return (ll)1000*a<=b*b+c*c;
}
int main()
{int T;cin>>T;while(T--){for (int i=0;i<3;i++) cin>>a[i];for (int j=0;j<3;j++) cin>>b[j];bool flag=true;for (int i=0;i<3;i++){if (func(a[0+i],a[(1+i)%3],a[(i+2)%3])!=func(b[0+i],b[(1+i)%3],b[(2+i)%3])){flag=false;break;}if (func(-1*a[0+i],a[(1+i)%3],a[(i+2)%3])!=func(-1*b[0+i],b[(1+i)%3],b[(2+i)%3])){flag=false;break;}}if (flag) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

J Jerry（bfs）

题意：有q次询问，每次给定一个数，对于数x可以进行的操作是减去一个完全平方数或者加上一个完全平方数（进行操作后的数不能小于0或大于1e5）
题解：直接用bfs搜出所有的最少操作即可

#include
using namespace std;
const int N=1e5+5;
int cnt;
int st[N],dist[N];
int a[N];
int q[N];
void inint()
{for (int i=1;i*i<=1e5;i++) a[cnt++]=i*i;
}
void bfs()
{int hh=0,tt=1;st[0]=1;q[hh]=0;while(hh<tt){int t=q[hh++];for (int i=0;i<cnt;i++){if (t+a[i]<=1e5 && !st[t+a[i]]){st[t+a[i]]=1;dist[t+a[i]]=dist[t]+1;q[tt++]=t+a[i];}if (t-a[i]>=0 && !st[t-a[i]]){st[t-a[i]]=1;dist[t-a[i]]=dist[t]+1;q[tt++]=t-a[i];}}}
}
int main()
{int T;inint();bfs();cin>>T;while(T--){int x;cin>>x;cout<<dist[x]<<endl;}return 0;
}

L League of Legends（签到）

题意：有三个人决斗，每一轮两人进行决斗，赢得可以和另一个人进行下一轮决斗。先输两局的人就淘汰。输出轮数期望
题解：只有两种情况，分别是211四轮或者21三轮。所以就是(4+3)/2=3.5

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！