2022年春季学期《算法分析与设计》练习12
XP的素数
题目描述
XP最近对素数很痴迷，特别是那些特殊的素数，其中有一类素数被称为孪生素数。其定义如下：如果一个数k是素数，k+2也是素数，那么k和k+2成为一对孪生素数。请计算一个给定区间m和n（0<m<n）中孪生素数对的个数。
输入
单组输入数据
m n
(0<m<n<1000)
输出
请输出一行结果:区间[m,n]中孪生素数对的个数
样例输入
1 999
样例输出
35
#include <bits/stdc++.h>
using namespace std;
int judge(int n)
{
int isprime=1;
for(int i=2; i<n; ++i)
{
if(n%i==0)
{
isprime=0;
break;
}
}
if(n==1){
return 0;
}
if(isprime==1)
{
return 1;
}
else
{
return 0;
}
}
int main()
{
int m,n;
while(cin>>m>>n)
{
int ans=0;
for(int i=m; i<=n; i++)
{
if(judge(i)&&judge(i+2))
{
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
XP的点滴
题目描述
XP一不留神感冒了，于是跑到校医院打点滴。打点滴真是无聊啊，他看到盐水一滴一滴地滴下来，突然想到一个问题：如果盐水有规律地滴下，先滴一滴，停一下；然后滴二滴，停一下；再滴三滴，停一下…，假设这瓶盐水一共有n毫升，每一滴是y毫升，每一滴需要的时间是一秒（假设最后一滴不到y毫升，需花费的时间也算一秒），停一下的时间也是一秒。请问XP多久能挂完这瓶盐水呢？
输入
单组输入数据
n y (0<n,y<=1000)
输出
输出一行结果
样例输入
10 1
样例输出
13
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,y;
while(cin>>n>>y)
{
int ans=0;
if(n%y==0){
ans+=n/y;
}else{
ans+=n/y+1;
}
int sum=0,count1=0;
for(int i=1;; i++)
{
if(sum<n)
{
sum+=i*y;
count1++;
}else{
ans--;
break;
}
}
ans+=count1;
cout<<ans<<endl;
}
return 0;
}
安置路灯
题目描述
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.'表示, 不需要照亮的障碍物格子用’X’表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有’.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含'.'和'X'。
输出
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。
样例输入
2
3
.X.
11
...XX....XX
样例输出
1
3
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str;
int t,n;
cin>>t;
for(int i=1; i<=t; i++)
{
cin>>n>>str;
int sum=0,j=0;
while(j<n)
{
if(str[j]=='.')
{
sum++;
j+=3;
}
else
{
j++;
}
}
cout<<sum<<endl;
}
return 0;
}
X星人的福利
题目描述
马上就要过年啦！X星球决定给每个人发一份福利，不过这份福利需要排队去X星设置在各个地方的福利发放点领取，福利据说是一个神秘大礼包。
由于每个人在2021年为X星做出的贡献不一样，因此福利包中的礼物也不一样，领取福利所需要的时间也不一样。
现在有N个X星人到达了某一个福利发放点，很遗憾这个福利发放点只有一位工作人员在发放福利包，现在已知每个X星人领取福利包所需要时间（不包括排队等待时间，单位：分钟）。
为了让所有人的平均等待时间最少，需要你设计一个算法来安排领取顺序，请编写程序输出最少平均等待时间（单位：分钟），结果四舍五入保留两位小数。
输入
单组输入，每组输入包含两行。
第1行输入一个正整数N，表示等待领取福利包的X星人的数量（N<=1000）。
第2行输入N个正整数，分别对应N个X星人每人领取福利包所需时间（单位：分钟），每个X星人的领取时间均不会超过100分钟。
输出
输出最少平均等待时间（单位：分钟），结果四舍五入保留两位小数。
样例输入
4
4 3 1 4
样例输出
3.25
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
int a[1005];
while(cin>>N){
for(int i=0;i<N;i++){
cin>>a[i];
}
sort(a,a+N);
int count1=0;
double sum=0;
for(int i=0;i<N;i++){
sum+=count1;
count1+=a[i];
}
double avg;
avg=sum/N;
printf("%.2f\n",avg);
}
return 0;
}
XP的小视频
题目描述
XP的表哥为他推荐了一些学习计算机编程的小视频，这些视频的播放时间长短不完全相同。现在给定一段时间，你能告诉XP他最多可以看多少个视频吗？每个视频的播放时间和给定的总时间均用分钟为单位。
输入
单组输入数据
第一行为m n
m为给定时间长度（分钟）(0<n,m<=1000)
n表示视频个数
接下来是n个整数代表每个视频的播放时间(每个视频播放时间为不超过1000的正整数)
输出
输出一个整数代表XP最多可以看的视频数。
样例输入
84 6
65 46 18 76 79 3
样例输出
3
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int w;
}p[1005];
bool cmp(Node a,Node b)
{
return a.w<b.w;
}
int main()
{
int m,n;
while(cin>>m>>n)
{
int count1=0;
for(int i=0; i<n; i++)
{
cin>>p[i].w;
}
sort(p,p+n,cmp);
for(int j=0; j<n; j++)
{
if(m>=p[j].w)
{
m-=p[j].w;
count1++;
}
}
cout<<count1<<endl;
}
return 0;
}
最小生成树（Prim）
题目描述
使用Prim算法求图的最小生成树(MST)
输入
每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。
输出
最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置）
样例输入
3 3
0 1 10
0 2 15
1 2 50
样例输出
0 1 10
0 2 15
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100
#define INF 100000;
long long G[MAXN][MAXN];
struct Node
{
int x,y,z;
} a[1005],p[1005];
bool cmp(Node a,Node b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
void init(int n)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
G[i][j]=INF;
}
}
}
void print(int n)
{
int closeset[n+1]= {0};
int lowcost[n+1];
int used[n+1];
int flag=0;
for(int i=0; i<n; i++)
{
lowcost[i]=G[0][i];
closeset[i]=0;
used[i]=0;
}
used[0]=1;
for(int i=1; i<n; i++)
{
int j=0;
for(int k=0; k<n; k++)
if(!used[k]&&(lowcost[k]<lowcost[j]))
j=k;
a[flag].x=closeset[j];
a[flag].y=j;
a[flag].z=lowcost[j];
flag++;
used[j]=1;
for(int k=1; k<n; k++)
{
if((!used[k])&&(G[j][k]<lowcost[k]))
{
lowcost[k]=G[j][k];
closeset[k]=j;
}
}
}
int temp;
sort(a,a+flag,cmp);
for(int k=0; k<flag; k++)
{
temp=0;
for(int i=0; i<n; i++)
{
if( a[k].x==p[i].x&&a[k].y==p[i].y)
{
temp=1;
break;
}
}
if(temp)
{
printf("%d %d %d\n",a[k].x,a[k].y,a[k].z);
}
else
{
printf("%d %d %d\n",a[k].y,a[k].x,a[k].z);
}
}
}
int main()
{
int n,m;
while(cin>>n>>m)
{
init(n);
int a1,b1,c1;
for(int k=0; k<m; k++)
{
cin>>a1>>b1>>c1;
G[a1][b1]=c1;
G[b1][a1]=c1;
p[k].x=a1;
p[k].y=b1;
p[k].z=c1;
}
print(n);
}
return 0;
}
寻找最大数
题目描述
给出一个正整数N，每次可以移动2个相邻数位上的数字，最多移动K次，得到一个新的正整数。求这个新的正整数的最大值。
输入
输入一个正整数N和K，输出新的正整数。例如：N=1990，K=1，输出9190；N=101，K=0，输出101；N= 9090000078001234，K= 6，输出9907000008001234。
输出
输出新的数字
样例输入
1990 1
101 0
9090000078001234 6
样例输出
9190
101
9907000008001234
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str;
int t,K;
while(cin>>str>>K)
{
int m=str.length();
for(int i=0; i<m; i++)
{
if(K==0){
break;
}
t=i;
for(int j=i+1; j<=i+K; j++)
{
if(str[t]<str[j])
{
t=j;
}
if(j>=m){
break;
}
}
for(int j=t;j>i;j--){
swap(str[j],str[j-1]);
}
K=K-(t-i);
}
cout<<str<<endl;
}
return 0;
}
病毒
题目描述
你有一个日志文件，里面记录着各种系统事件的详细信息。自然的，事件的时间戳按照严格递增顺序排列（不会有两个事件在完全相同的时刻发生）。
遗憾的是，你的系统被病毒感染了，日志文件中混入了病毒生成的随机伪事件（但真实事件的相对顺序保持不变）。备份的日志文件也被感染了，但由于病毒采用的随机感染方法，主日志文件和备份日志文件在感染后可能会变得不一样。
给出被感染的主日志和备份日志，求真实事件序列的最长可能长度。
输入
输入第一行为数据组数T (T<=100)。每组数据包含两行，分别描述感染后的主日志和备份日志。每个日志文件的格式相同，均为一个整数n (1<=n<=1000)（代表感染后的事件总数）和n 个不超过100,000的正整数（表示感染后各事件的时间戳）。注意，感染后可能会出现时间戳完全相同的事件。
输出
对于每组数据，输出真实事件序列的最长可能长度。
样例输入
1
9 1 4 2 6 3 8 5 9 1
6 2 7 6 3 5 1
样例输出
3
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],dp[200010];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int N;
while(cin>>N)
{
while(N--)
{
memset(dp,0,sizeof(dp));
int n,m;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i];
}
cin>>m;
for(int i=0; i<m; i++)
{
cin>>b[i];
}
for(int i=0; i<n; i++)
{
int maxx=0;
for(int j=0; j<m; j++)
{
if(a[i]>b[j])
{
maxx=max(maxx,dp[j]);
}
else if(a[i]==b[j])
{
dp[j]=maxx+1;
}
}
}
sort(dp,dp+m,cmp);
cout<<dp[0]<<endl;
}
}
return 0;
}
