[HBCPC2024] 2024 年湖北省大学生程序设计竞赛重现赛题解
发布时间
阅读量：
阅读量
比赛链接:HBCPC2024
还是和 @cyx20110930 组的队，只不过用我的号交的。（rk. 26）这次我也橙了 开心.jpg
因为 @cyx20110930 在车内时遇到了电力问题导致电脑电量即将耗尽。
因此他仅登录了一小时。
然而他意外创作了两道题目，并随口提到了两道题目的内容。
%%%
这个问题H也是一个不错的选择。它虽然看似简单但确实是一个很好的练习机会。然而由于我的编程基础尚浅技术功底较弱并且时间紧迫我还没来得及深入研究它。不过大家不妨试着自己动手解决一下吧！
安利一波 @cyx20110930 的题解。
题目意思
输入
，输出乘积最大的两个数
使得
。
思路
数学题，秒了。直接先算出
的值。然后为了让
最大，直接输出
和
即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int T;
cin>>T;
while(T--){
int x,y;
cin>>x>>y;
int gcd=__gcd(x,y);
int lcm=x*y/gcd;
cout<<lcm/gcd<<' '<<1<<endl;
}
return 0;
}
cpp
此题由 CYX 所写的。因此复制一份他的题解。
题目意思
在平面中存在若干点。
请问您能否利用这些点中的至少三点构成一个图形，并求其面积最小值？
若无法组成，则返回值为 -1。
思路
很明显最小的一定是三角形。
论证：对于任意给定的一个具有n条边的凸多边形来说，在其内部必然能够被分割为一个三角形和另一个具有n−1条边的凸多边形；因此形成的三角形必然具有较小的面积。
所以直接暴力枚举三角形用海伦公式求面积即可。
代码
孩子不判三点共线，多半是废了！
#include <bits/stdc++.h>
using namespace std;
struct node{
double x,y;
}po[1000005];
void solve(){
double ans=0x3f;
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>po[i].x>>po[i].y;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int z=j+1;z<=n;z++){
double sum=po[j].x*po[z].y-po[z].x*po[j].y+po[i].x*po[j].y-po[j].x*po[i].y-po[i].x*po[z].y+po[z].x*po[i].y;
sum=abs(sum);
if (sum != 0){
ans=min(ans,sum/2.0);
}
}
}
}
if (ans==0x3f){
cout<<-1<<endl;
}
else{
cout<<ans<<endl;
}
}
int main(){
int t;
while(t--){
solve();
}
}
cpp
签到。
题目意思
共有n位顾客每人可以选择购买b美元的Grilled Chicken Burger Set或a美元的Spicy Chicken Burger Set。其中有x位顾客选择了Grilled Chicken Burger Set，请计算他们总共花费了多少美元？
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int main(){
int T;
cin>>T;
while(T--){
int n,x,a,b;
cin>>n>>x>>a>>b;
cout<<(n-x)*a+x*b<<endl;
}
return 0;
}
cpp
原神，启动！ （我不玩原神）
题目意思
在棋局中，请询问黑方与白方每一步落子的情况，并统计每步棋盘上黑白双方共有多少个棋子被对方围堵。
思路
很容易，在每一步落子之后，在该棋子周围五个位置进行连接块处理。
代码
#include <bits/stdc++.h>
using namespace std;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int board[30][30],ans[10],n=19;
bool used[30][30];
void bfs(int x,int y){
int col=board[x][y];
queue<pair<int,int>> que;
vector<pair<int,int>> v;
que.push(make_pair(x,y));
used[x][y]=true;
bool ok=false;
while(!que.empty()){
auto [x,y]=que.front();
que.pop();
v.push_back(make_pair(x,y));
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1 || nx>n || ny<1 || ny>n)
continue;
if(board[nx][ny]==-1)
ok=true;
if(board[nx][ny]!=col || used[nx][ny])
continue;
que.push(make_pair(nx,ny));
used[nx][ny]=true;
}
}
if(!ok){
for(auto &[x,y]:v){
board[x][y]=-1;
ans[col]++;
}
}
return;
}
void solve(int col,vector<pair<int,int>> &v){
memset(used,0,sizeof(used));
for(auto &[x,y]:v){
if(x<1 || x>n || y<1 || y>n)
continue;
if(used[x][y])
continue;
if(board[x][y]!=col)
continue;
bfs(x,y);
}
for(auto &[x,y]:v){
if(x<1 || x>n || y<1 || y>n)
continue;
if(used[x][y])
continue;
if(board[x][y]!=1^col)
continue;
bfs(x,y);
}
return;
}
int main(){
memset(board,-1,sizeof(board));
int m;
cin>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
int col=i%2;
board[x][y]=col;
ans[1]=ans[0]=0;
vector<pair<int,int>> v;
for(int i=0;i<4;i++)
v.push_back(make_pair(x+dx[i],y+dy[i]));
v.push_back(make_pair(x,y));
solve(col^1,v);
cout<<ans[0]<<' '<<ans[1]<<endl;
}
return 0;
}
cpp
是 @cyx20110930 写的，所以跟我无关（bushi
他的题解:here
题目意思
有一个序列
，问对于所有 1 到 n 的排列
，算出的
... 的期望对 998244353 的取模。
思路
结论：平均数。
证明
记答案为
，
若 a 数组有 n 项，期望为
证毕！还是平均数。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
int qmi(int a,int b,int p){
int res=1;
while(b){
if(b&1) res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
int main(){
int n;
cin>>n;
int x,ans=0;
for(int i=1;i<=n;i++){
cin>>x;
ans+=x;
}
ans=ans%mod;
ans=ans*qmi(n,mod-2,mod)%mod;
cout<<ans;
}
cpp
题目意思
给定起点和终点，求起点到终点的最短路径，任意两点的路径为
思路
首先特判
，输出0。
假设
- 当
时，代价是
。
- 当
和
不互质是，可以
，代价为
。
- 当
和
互质时：中间经过的点必然都是质数。让经过的质数越小越好。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int lcm(int a,int b){
return a*b/__gcd(a,b);
}
void solve(){
int a,b;
cin>>a>>b;
if(a==b){
cout<<0<<endl;
return;
}
vector<int> A,B;
A.push_back(2);
B.push_back(2);
A.push_back(a);
B.push_back(b);
for(int i=2;i<=a/i;i++){
if(a%i==0){
int x=i,y=a/i;
if(x!=1)
A.push_back(x);
if(y!=1)
A.push_back(y);
}
}
for(int i=2;i<=b/i;i++){
if(b%i==0){
int x=i,y=b/i;
if(x!=1)
B.push_back(x);
if(y!=1)
B.push_back(y);
}
}
int ans = lcm(a,b);
for(auto &x:A){
int now=lcm(a,x)+lcm(b,x);
ans=min(ans,now);
for(auto &y:B){
int now1=lcm(a,x)+lcm(x,y)+lcm(y,b);
int now2=lcm(a,x)+lcm(x,2)+lcm(y,2)+lcm(y,b);
ans=min({ans,now1,now2});
}
}
for(auto &x:B){
int now=lcm(a,x)+lcm(b,x);
ans=min(ans,now);
for(auto &y:A){
int now1=lcm(a,x)+lcm(x,y)+lcm(y,b);
int now2=lcm(a,x)+lcm(x,2)+lcm(y,2)+lcm(y,b);
ans=min({ans,now1,now2});
}
}
cout<<ans<<endl;
return;
}
int main(){
int T;
cin>>T;
while(T--)
solve();
return 0;
}
cpp
友情提醒:不要Ctrl C+Ctrl V
全部评论 (0)
还没有任何评论哟~