ACM实训冲刺第二十二天

本文主要是介绍ACM实训冲刺第二十二天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【碎碎念】今天学习ACM时间有点紧，只有30分钟，能写到哪算哪吧

人见人爱A^B（数值运算与字符串处理）

这段代码实现的是模幂运算，具体说是计算 A^Bmod1000 的值。模幂运算是一种在计算机科学和密码学中常用的算法，特别是用于处理大整数的幂运算时，通过取模可以控制结果的大小，减少计算量和避免整数溢出。

该算法采用了循环（for 循环）来实现指数 B 次的乘法操作，并在每次乘法后都对结果取模 1000，这是快速幂算法的一个简化版本

#include<stdio.h>
#include<math.h>
int main(){int A;int B;int C=1;while(scanf("%d %d",&A,&B) && A!=0,B!=0){for(int i=0;i<B;i++){C=(C*A)%1000;}printf("%d\n",C%1000);C=1;}return 0;
}

Tokitsukaze and All Zero Sequence （数据处理与逻辑判断）

这段代码属于“数据处理与逻辑判断”题型。代码的主要功能是处理输入的数据（整数序列），并根据一定的逻辑规则判断和计算输出结果。

具体来说，程序首先读取一个整数 t，表示有 t 组测试数据。对于每组数据，程序执行以下操作：

读取一个整数 n，表示接下来要输入的整数序列长度。
读取 n 个整数并存储在数组 a 中，同时使用另一个数组记录每个数字出现的次数。
判断数组中的元素是否有重复（通过标记变量 flag），以及是否包含数字0。
根据以下逻辑输出结果：
如果数组中有数字0，则输出序列中非0数字的个数。
如果没有数字0且所有数字都是唯一的，则输出当前序列长度加1，意味着可以在序列末尾添加一个新数字保持唯一性。
如果有重复数字（不论是否含0），则输出当前序列长度，因为已经不满足所有数字唯一的要求。

#include<stdio.h>
int main(){int t;scanf("%d",&t);for(int i=0;i<t;i++){int n;int flag=0;int ch;int a[101]={0};scanf("%d",&n) ;for(int j=0;j<n;j++){scanf("%d",&ch);a[ch]++;if(a[ch]>1)flag=1;}if(a[0]>0){printf("%d\n",n-a[0]);}else{if(flag==0)printf("%d\n",n+1);if(flag==1)printf("%d\n",n);}}return 0;
}

Aggressive cows（二分查找）

这段代码实现的是一个二分查找（Binary Search）算法的应用问题，具体是解决“最长连续子序列的最小间距”问题的一个变种。给定一个整数数组和一个整数 c，要求找到一个最小的间距 m，使得在数组中能选出 c 个不重叠的连续子序列，每个子序列中的元素之间的间距至少为 m。

代码流程如下：

输入序列长度 n 和需要放置的位置数量 c。
读取 n 个整数到数组 a 中，并对数组进行排序。
定义二分搜索的范围为数组中的最小值 l 到最大值 r。
在二分搜索的过程中，使用函数 fun() 判断以当前中点 mid 作为间距时，能否找到至少 c 个符合条件的位置。如果可以，则说明答案至少为 mid，并且在 mid 的右侧继续搜索；如果不满足条件，则在mid 的左侧搜索。
最终得到的ans 即为所求的最小间距。

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,c;
int a[100005];
bool fun(int m) {int cnt=1,cur=0,next=1;while(next<n){next++;if(a[next]-a[cur]>=m){cnt++;cur=next;}}if(cnt>=c) return true;else return false;
}int main(){scanf("%d%d",&n,&c);for(int i=0;i<n;i++){scanf("%d",&a[i]);}int l=a[0],r=a[n-1];int ans=0;sort(a,a+n);while(l<=r){        int mid=(l+r)/2;if(fun(mid)){ans=mid;l=mid+1;}else{r=mid-1;}}printf("%d",ans);return 0;
}

题型统计

练习题名称	数学计算与序列求和	数值运算与字符串处理	频率统计题	数据处理与逻辑判断	0-1背包问题	最大覆盖半径	二分查找
SUM Problem	√
A+B problem		√
Anton and letters			√
Sum of digits		√
寒冰王座				√
Charm Bracelet					√
Vanya and Lanterns						√
Anton and Danik		√
人见人爱A^B		√
Tokitsukaze and All Zero Sequence				√
Aggressive cows							√