当前位置： 首页 > news >正文

2024年春季学期《算法分析与设计》练习13

news 来源：原创 2024/9/30 16:32:01

A:菱形图案

题目描述

KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“*”组成的菱形图案。

输入

多组输入，一个整数（2~20）。

输出

针对每行输入，输出用“*”组成的菱形，每个“*”后面有一个空格。每输出一个菱形的后面需要空一行。

样例输入 Copy
2
3
4
样例输出 Copy
  * * * 
* * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * 
#include <bits/stdc++.h>
#define ll long long
#define MM 0x3f3f3f3f
using namespace std;
const int N = 1e5 + 5;
const int P = 131;
const int MOD=1e9+7;
void solve(){int n;while(cin>>n){for(int j=0;j<=n;j++){for(int i=j;i<n;i++)cout<<' ';for(int i=0;i<=j;i++)cout<<'*'<<' ';cout<<"\n";}for(int j=n;j>0;j--){for(int i=j;i<=n;i++)cout<<' ';for(int i=0;i<j;i++)cout<<'*'<<' ';cout<<"\n";}cout<<"\n";}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);solve();return 0;
}

 B:X星人的礼物

题目描述

六一儿童节到了，X星人宝宝收到了很多很多礼物。他决定把这些礼物装到自己的礼物箱中。为此，他准备了很多个型号相同的礼物箱，每个礼物箱能够装礼物的最大重量都是一样的。但是X星人宝宝不希望在一个礼物箱里面装太多礼物（可能担心礼物会被压坏吧），每个礼物箱最多只允许装2个礼物。
假设X星人宝宝收到了N个礼物，现在给出每一个礼物的重量和一个礼物箱的最大装载量，请你编写一个程序计算X星人宝宝最少要用多少个礼物箱才能够把所有的礼物都装完。

输入

单组输入。
每组两行，第1行输入两个正整数，分别表示礼物的数量N和每个礼物箱的最大装载量C，其中1<=N<=1000，1<=C<=100，两者之间用英文空格隔开。
第2行输入N个不超过100的正整数，分别表示每一个礼物的重量，两两之间用英文空格隔开。
输入保证最重的礼物的重量<=C。

输出

针对所输出的数据，输出将所有的礼物全部都装完所需的礼物箱的最少个数。

样例输入 Copy
5 80
20 70 40 30 10
样例输出 Copy
3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e3 +5;
const int M =1e9 +7;
const int inf =0x3fffffff;
int a[N];
void solve(){int n, m;cin >> n >> m;for (int i = 0; i < n; i++)cin >> a[i];sort(a, a + n);int l = 0, r = n - 1;int s = 0;while (l <= r){if (a[l] + a[r] <= m){l++;r--;}else{r--;}s++;}cout << s << "\n";
}
int main() {cin.tie(0)->sync_with_stdio(false);solve();return 0;
}

 C:隔离14天

题目描述

     如果实施更为严格的防控措施，一辆汽车上有一个确诊患者或者密切接触者，那么该汽车上所有的人都被认为是密切接触者，全部需要自行居家隔离或者集中隔离14天。
      现在假定编号为0的乘客冠状病毒核酸检验呈阳性，请编写一个程序统计需隔离的总人数（包括编号为0的乘客）。

输入
第1行的第1个数字n表示总人数，第2个数字m表示汽车数量；从第2行开始，接下来的m行表示每辆汽车的司乘人员总人数和人员编号（人员编号是一个固定值，可以对应于我们的身份证号码），每一行的第1个数字k表示该汽车的司乘人员总数，接下来的k个数字表示每一个人的编号。
输出
需要被隔离的总人数。
样例输入 Copy
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
样例输出 Copy
4

​
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e3 +5;
const int M =1e9 +7;
const int inf =0x3fffffff;
int a[N];
int f[N];
int r[N];
void init(int n){for(int i=0;i<n;i++){f[i]=i;r[i]=1;}
}
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);
} 
void solve(){int n,m;cin>>n>>m;init(n);while(m--){int k;cin>>k;cin>>a[0];for(int i=1;i<k;i++){cin>>a[i];int x=find(a[i-1]);int y=find(a[i]);if(x!=y){f[x]=y;r[y]+=r[x];}}}cout<<r[f[0]]<<"\n";
}
int main() {cin.tie(0)->sync_with_stdio(false);solve();return 0;
}

 D:最小生成树（Kruskal）

题目描述

编程实现Kruskal算法，求图的最小生成树(MST)的权重。

输入

每组数据分为两个部分，第一部分为图的点数n，和边数m, 
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。 

输出

最小生成树的权重。

样例输入 Copy
3 3
0 1 10
0 2 15
1 2 50
样例输出 Copy
25
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e3 +5;
const int M =1e9 +7;
const int inf =0x3fffffff;
int n, m;
int p[N];
struct edge
{int a, b, c;bool operator<(const edge& W) const{return c < W.c;}
}e[N];
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}
void init()
{for (int i = 0; i < n; i++) p[i] = i;
}
void solve()
{while(cin>>n>>m){memset(e, 0, sizeof(edge) * N);for (int i = 0; i < m; i++){int a, b, c;cin>>a>>b>>c;e[i] = { a,b,c };}sort(e, e + m);init();int ans = 0;for (int i = 0; i < m; i++){int a = e[i].a, b = e[i].b, c = e[i].c;a = find(a), b = find(b);if (a != b){p[a] = b;ans += c;}}cout << ans << '\n';}}
int main() {cin.tie(0)->sync_with_stdio(false);solve();return 0;
}

 E:搭建电路

题目描述

明明迷上了一个搭建电路的游戏。
在游戏中，每次在两个电子元件之间增加一条有效电路（两个元件之间先前没有电路相连）都将获得相应的积分奖励。
已知电子元件数量n和部分电子元件之间的奖励积分值。如何构建一个有效电路将所有元件全部连接起来，并且可以得到最多的积分奖励。

输入

每组输入数据包含m+1行。
第1行输入两个正整数n和m，其中n表示电子元件数量（n<=100），m表示提供了m对电子元件之间的奖励积分值（m<=1000）。两个正整数之间用空格隔开。
第2行到第m+1行对应m对电子元件及其对应的奖励积分值，每一行包含三个正整数，第1个和第2个整数表示电子元件编号（从1开始），第3个整数表示两个元件之间搭建电路的奖励积分num(num<1e9)。整数之间用空格隔开。

输出

每组输出占1行，输出一个正整数，即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来，则输出“No solution.”。

样例输入 Copy
3 3
1 2 10
1 3 20
2 3 30
样例输出 Copy
50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e3 +5;
const int M =1e2 +7;
const int inf =0x3fffffff;
int p[M];
int n, m;
struct Edge
{int a, b, c;bool operator<(const Edge& Z)const{return c > Z.c;}
}edge[N];
void init()
{for (int i = 1; i <= n; i++) p[i] = i;
}
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}
void solve()
{while(cin>>n>>m){memset(edge, 0, sizeof(Edge) * N);for (int i = 0; i < m; i++){int a, b, c;cin>>a>>b>>c;edge[i] = { a,b,c };}sort(edge, edge + m);init();int cnt = 0, flag = 0;ll res = 0;for (int i = 0; i < m; i++){int a = edge[i].a, b = edge[i].b, c = edge[i].c;a = find(a), b = find(b);if (a != b){p[a] = b;res += c;cnt++;}if(cnt == n - 1){flag = 1;break;}}if (!flag) cout<<"No solution.\n";else cout<<res<<"\n";}}
int main() {cin.tie(0)->sync_with_stdio(false);solve();return 0;
}

 F:最小生成树（Prim）

题目描述

使用Prim算法求图的最小生成树(MST)

输入

每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

输出

最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置）

样例输入 Copy
3 3
0 1 10
0 2 15
1 2 50
样例输出 Copy
0 1 10
0 2 15
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =5e2 +5;
const int M =1e5 +7;
const int inf =0x3fffffff;
int n,m,res;    
int a,b,c;
int g[N][N],backup[N],dist[N];
bool st[N],stt[N][N];
struct edge
{int a,b,c;bool operator<(const edge& W)const{if(a==W.a) return b<W.b;return a<W.a;}
}edges[M];
void prim()
{res=0;for(int i=0;i<n;i++){int t=-1;for(int j=0;j<n;j++) if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;st[t]=true;if(i) if(stt[backup[t]][t]) edges[res++]={backup[t],t,dist[t]};else edges[res++]={t,backup[t],dist[t]};for(int j=0;j<n;j++) if(!st[j]&&dist[j]>g[t][j]) {dist[j]=g[t][j];backup[j]=t;}}sort(edges,edges+res);for(int i=0;i<res;i++) {a=edges[i].a,b=edges[i].b,c=edges[i].c;cout<<a<<' '<<b<<' '<<c<<'\n';}  
}
void solve()
{while(cin>>n>>m){memset(g,0x3f,sizeof g);memset(dist,0x3f,sizeof dist);memset(st,false,sizeof st);while(m--){cin>>a>>b>>c;stt[a][b]=true;g[a][b]=g[b][a]=min(g[a][b],c); }prim();}
}
int main() {cin.tie(0)->sync_with_stdio(false);solve();return 0;
}

 G:台球碰撞

题目描述

在平面直角坐标系下，台球桌是一个左下角在(0,0)，右上角在(L,W)的矩形。有一个球心在(x,y)，半径为R的圆形母球放在台球桌上（整个球都在台球桌内）。受撞击后，球沿极角为a的射线（即：x正半轴逆时针旋转到此射线的角度为a）飞出，每次碰到球桌时均发生完全弹性碰撞（球的速率不变，反射角等于入射角）。

如果球的速率为v，s个时间单位之后球心在什么地方？

输入

输入文件最多包含25组测试数据，每个数据仅一行，包含8个正整数L,W,x,y,R,a,v,s（100<=L,W<=105,1<=R<=5, R<=x<=L-R, R<=y<=W-R, 0<=a<360, 1<=v,s<=105），含义见题目描述。L=W=x=y=R=a=v=s=0表示输入结束，你的程序不应当处理这一行。

输出

对于每组数据，输出仅一行，包含两个实数x, y，表明球心坐标为(x,y)。x和y应四舍五入保留两位小数。

样例输入 Copy
100 100 80 10 5 90 2 23
110 100 70 10 5 180 1 9999
0 0 0 0 0 0 0 0
样例输出 Copy

80.00 56.00
71.00 10.00
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =5e2 +5;
const int M =1e5 +7;
const int inf =0x3fffffff;
const double pi = acos(-1.0);
double L,W,x,y,R,a,v;
int s,t; 
double vx,vy;
void solve()
{while(cin>>L>>W>>x>>y>>R>>a>>v>>s&&L+W+x+y+R+a+v+s){vy=v*sin(a*pi/180),vx=v*cos(a*pi/180);t=0;while(t!=s){x+=vx;y+=vy;while(x-R<0||x+R>L||y-R<0||y+R>W){if(x-R<0) x=2*R-x,vx=-vx;if(x+R>L) x=2*L-2*R-x,vx=-vx;if(y-R<0) y=2*R-y,vy=-vy;if(y+R>W) y=2*W-2*R-y,vy=-vy;}t++;}printf("%.2lf %.2lf\n",x,y);}
}
int main() {cin.tie(0)->sync_with_stdio(false);solve();return 0;
}

 H:战场的数目(还不会)

题目描述
在上题中，假设战场的图形周长为p，一共有多少种可能的战场？
例如，p<8时没有符合要求的战场，p=8时有2种战场：

p=10有9种战场：

要求输出方案总数模987654321的值。
输入

输入文件最多包含25组测试数据，每个数据仅包含一行，有一个整数p（1<=p<=109），表示战场的图形周长。p=0表示输入结束，你的程序不应当处理这一行。

输出

对于每组数据，输出仅一行，即满足条件的战场总数除以987654321的余数。

样例输入 Copy
7
8
9
10
0
样例输出 Copy
0
2
0
9

相关文章：

  • opencv中的图像操作
  • 端口占用多：UE4/UE5像素流送云推流时如何优化端口使用？
  • mac无法读取windows分区怎么办 苹果硬盘怎么读取
  • Android SDK版本号与API Level 的对应关系
  • ctfshow-web入门-命令执行（web53-web55）
  • 数据结构：手撕代码——顺序表
  • 【Java】解决Java报错：IllegalArgumentException
  • 【QT】记录一次QT程序发布exe过程
  • 硬盘几个关键指标你一定要知道！
  • 程序固化——FPGA学习笔记6
  • vscode插件开发之 - menu配置
  • ffmpeg的部署踩坑及简单使用方式
  • Linux排查问题常用命令
  • C语言详解（文件操作）1
  • ARM的异常处理
  • 《深入 React 技术栈》
  • Android系统模拟器绘制实现概述
  • es6要点
  • JAVA多线程机制解析-volatilesynchronized
  • MaxCompute访问TableStore(OTS) 数据
  • Promise初体验
  • puppeteer stop redirect 的正确姿势及 net::ERR_FAILED 的解决
  • Python学习笔记 字符串拼接
  • scrapy学习之路4(itemloder的使用)
  • windows-nginx-https-本地配置
  • 分享自己折腾多时的一套 vue 组件 --we-vue
  • 码农张的Bug人生 - 见面之礼
  • 爬虫进阶 -- 神级程序员：让你的爬虫就像人类的用户行为！
  • 如何将自己的网站分享到QQ空间，微信，微博等等
  • 问:在指定的JSON数据中（最外层是数组）根据指定条件拿到匹配到的结果
  • 详解移动APP与web APP的区别
  • 在electron中实现跨域请求，无需更改服务器端设置
  • raise 与 raise ... from 的区别
  • ​ 轻量应用服务器：亚马逊云科技打造全球领先的云计算解决方案
  • ​Benvista PhotoZoom Pro 9.0.4新功能介绍
  • #传输# #传输数据判断#
  • $.ajax中的eval及dataType
  • （7）摄像机和云台
  • （day 2）JavaScript学习笔记（基础之变量、常量和注释）
  • (Spark3.2.0)Spark SQL 初探： 使用大数据分析2000万KF数据
  • （附源码）spring boot球鞋文化交流论坛 毕业设计 141436
  • （四）stm32之通信协议
  • （学习日记）2024.02.29：UCOSIII第二节
  • （一）80c52学习之旅-起始篇
  • （一）项目实践-利用Appdesigner制作目标跟踪仿真软件
  • （已解决）vue+element-ui实现个人中心，仿照原神
  • (转)C#调用WebService 基础
  • （转）原始图像数据和PDF中的图像数据
  • .MyFile@waifu.club.wis.mkp勒索病毒数据怎么处理|数据解密恢复
  • .net core 依赖注入的基本用发
  • .NET Core6.0 MVC+layui+SqlSugar 简单增删改查
  • .net php 通信,flash与asp/php/asp.net通信的方法
  • .net 程序发生了一个不可捕获的异常
  • .NET 实现 NTFS 文件系统的硬链接 mklink /J（Junction）
  • .NET3.5下用Lambda简化跨线程访问窗体控件,避免繁复的delegate,Invoke(转)