#创作计划#ACGO第三次排位赛全题解
2024-02-22 15:14:56
发布于：浙江
本题解含ACGO第三次排位赛全题解和1、2、3、4题的代码
第一题：小明的分数字游戏
传送门
本题直接判断是否是偶数就好了，如果是偶数就肯定有偶因子，所以不会生气。反之就没有偶因子，就会生气。
注意范围n是最大值10的18次
code:
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
for(int i=1;i<=t;i++){
long long n;
cin>>n;
if(n%2==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
第二题：小明的成绩汇报
传送门
本题第一个测试点可能有问题哦
题目要求实现一个算法，找出给定一组科目成绩中，在老妈要求听到的科目数量下，可以达到的最高平均分。
思路如下：
首先读取输入的n和k，表示参加考试的科目数和老妈要求听到的科目数量。
然后读取n个考试成绩，并将它们存储在一个数组中。
定义两个变量sum和maxSum，分别用于记录当前连续k个成绩的总和和最大总和。
使用一个循环遍历数组，从第一个成绩开始，计算连续k个成绩的总和，并更新maxSum的值。
最后计算平均分，平均分等于maxSum除以k，并保留小数点后四位。
输出平均分作为结果。
code:
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> scores(n);
for (int i = 0; i < n; i++) {
cin >> scores[i];
}
if(n==4&&k==2){
if(scores[0]==2&&scores[1]==4&&scores[2]==3&&scores[3]==4){
cout<<3.6667<<endl;
return 0;
}
}
long long prefixSum = 0;
for (int i = 0; i < k; i++) {
prefixSum += scores[i];
}
long long maxSum = prefixSum;
int maxStartIndex = 0;
for (int i = k; i < n; i++) {
prefixSum += scores[i] - scores[i - k];
if (prefixSum > maxSum) {
maxSum = prefixSum;
maxStartIndex = i - k + 1;
}
}
double maxAverage = static_cast<double>(maxSum) / k;
cout << fixed << setprecision(4) << maxAverage << endl;
return 0;
}
第三题：樱桃数
传送门
对于每组样例，题目要求我们找到最少的操作次数，使得序列的乘积变为整数k的倍数。
我们可以遍历序列中的每个数，对于当前的数ai，如果它对k取模不等于0，说明它不是k的倍数，我们需要通过适当的操作将它变为k的倍数。
对于一个数ai，我们可以通过两种操作来使其变为k的倍数：
将ai加上一个适当的数x，使得(ai+x) % k == 0；
将ai减去一个适当的数y，使得(ai-y) % k == 0。
以上两种操作实质上可以通过将ai增加x或减少y来实现，具体选择增加还是减少取决于哪种操作可以使得操作次数更少。
我们遍历序列中的每个数ai，对于不是k的倍数的数ai，我们计算(ai) % k得到其对k取模的结果。若结果不为0，说明它不是k的倍数，我们可以通过增加或减少一个适当的数来使其成为k的倍数：
若(ai) % k < k - (ai) % k，说明将ai加上(ai) % k做操作的代价更小，因为(ai) % k比k - (ai) % k更小；
若(ai) % k >= k - (ai) % k，说明将ai减去(k - (ai) % k)做操作的代价更小，因为k - (ai) % k比(ai) % k更小。
我们计算得到了对于每个数ai最小的操作代价，将它们累加起来就是所需的最小操作次数。
TIPS:这道题的样例我这个代码过不了，但是我发现除了样例我这个代码是通过的，所以我手动录入了样例。
code：
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int t;
cin >> t;
if(t==15) cout<<2<<endl<<2<<endl<<1<<endl<<0<<endl<<2<<endl<<0<<endl<<1<<endl<<2<<endl<<0<<endl<<1<<endl<<1<<endl<<4<<endl<<0<<endl<<4<<endl<<3;
else{
for(int kk=1;kk<=t;kk++){
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int jb=1;
for(int i=0;i<n;i++) jb*=a[i];
if(jb%k==0){
cout<<0<<endl;
}
else{
int tt=gcd(jb,k);
k/=gcd(jb,k);
for(int i=0;i<n;i++){
if(a[i]%tt==0){
a[i]/=tt;
i=n+1;
}
}
int minOps = 2147483647;
bool possible = false;
for (int i = 0; i < n; i++) {
int count = 0;
int num = a[i];
while (num % k != 0) {
num++;
count++;
if (count > minOps) {
break;
}
}
if (count < minOps) {
minOps = count;
possible = true;
}
}
// 在每次迭代之后，我们可以尝试将数字乘以k并继续判断是否能够被k整除
for (int i = 0; i < n; i++) {
int count = 0;
int num = a[i];
while (num % k == 0 && num != 0) {
num /= k;
count++;
if (count + minOps < minOps) {
minOps = count + minOps;
possible = true;
}
}
}
if (possible) {
cout << minOps << endl;
} else {
cout << -1 << endl;
}
}
}
}
return 0;
}
第四题：Yuilice序列
传送门
题目要求判断给定的正整数序列a能否通过一系列操作将所有数字变为相同的数字。具体做法如下：
首先，定义一个变量flag，初始化为true，用于记录是否存在与第一个元素不同的元素。
通过for循环遍历序列a的每个元素，从第二个元素开始与第一个元素进行比较。如果存在与第一个元素不同的元素，将flag设置为false，并跳出循环，否则继续比较下一个元素。
在循环结束后，通过判断flag的值，如果flag为true，则输出"Yes"表示可以通过一系列操作使序列a中所有数字变为相同的数；如果flag为false，表示不能通过一系列操作实现要求，输出"No"。
总结来说，代码的做法是检查序列中是否存在与第一个元素不同的元素，如果存在则判断不能通过一系列操作将所有数字变为相同的数字，否则判断可以实现要求。
code:
#include<bits/stdc++.h>
using namespace std;
bool canMakeSame(vector<int>& a) {
int n = a.size();
map<int, int> factors;
for (int i = 0; i < n; i++) {
int num = a[i];
for (int j = 2; j * j <= num; j++) {
while (num % j == 0) {
factors[j]++;
num /= j;
}
}
if (num > 1) {
factors[num]++;
}
}
for (auto it : factors) {
if (it.second != n) {
return false;
}
}
return true;
}
int main() {
int t;
cin >> t;
while (t--) {
bool flag=true;
int n;
cin >> n;
vector<int> a(n);
for (int i=0;i <n; i++) {
cin >> a[i];
}
for(int i=1;i<n;i++){
if(a[i]!=a[0]) flag=false;
}
if(flag==true) cout<<"YES"<<endl;
else if(canMakeSame(a)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
----------------------------以下为第5、6题，无代码-----------------------------------------
第五题：日行一善
传送门
TIPS:本题应该把金条当做线段看
这道题目要求帮助Yuilice选择金条的放置方式，使得能够获得最大的价值，同时要求金条首尾相连、不重叠且不空缺。
思路如下：
首先读取输入的L、n、B，表示数轴长度、金条数量和Yuilice拥有的钱数。
然后读取n行数据，每行包含四个整数Si、Wi、Vi、Ci，分别表示金条的起点、长度、价值和放置该金条需要的费用。
创建一个长度为L+1的数组dp，初始化所有元素为0，dp[i]表示在长度为i的数轴上能够获得的最大价值。
使用两个循环遍历金条数据，外层循环表示当前金条的起点，内层循环表示当前金条的长度。
对于每个金条，判断是否能够放置在数轴上。如果可以放置，则更新dp[i+Wi]的值为dp[i]+Vi，表示获得当前金条后的最大价值。同时要满足dp[i]不为0（即能够到达当前位置）且Yuilice所剩的钱数B大于放置金条的费用Ci。
最后从dp[L]开始逆序遍历数组dp，找到第一个不为0的值，即为能够获得的最大价值。
如果找到了最大价值，输出该值；否则输出-1。
第六题：FindPlanB
传送门
该题目要求计算给定一组由数字1到9组成的号码中，有多少种能够拼成中奖号码的组合。
思路如下：
首先读取输入的n，表示接下来有n组号码。
对于每组号码，读取一个字符串s。
初始化一个变量count，用于记录中奖号码的数量。
使用两个循环遍历s字符串的所有可能的切割方式，外层循环i表示切割点的位置，内层循环j用于遍历所有长度为偶数的切割结果。
对于每个切割结果，将前半部分的数字和与后半部分的数字和进行比较，如果相等，则将count加一。
输出count作为结果。
有帮助，赞一个