ACGO#44欢乐赛题解

yaonainai

2025-04-07 19:10:31

发布于：浙江

16阅读

0回复

0点赞

分析：难度大致为全红，思路比较好想

T1

两种方法：

1.开动脑筋想最多“O"

据题意，数字 8 中有 2 个 "O"，是最多的，所以只要每位都放8即可，答案是88

#include<bits/stdc++.h>
using namespace std;
int main()
{ 
   	cout<<88<<endl;
    return 0;
}

2.暴力枚举1~99

依次判断即可,但较为麻烦

#include<bits/stdc++.h>
using namespace std;
long long a[20]={0,0,0,0,1,0,1,0,2,1};
long long work(long long x)
{
    int x1=x%10,x2=x/10;
    return a[x1]+a[x2];
}
long long ans,maxx;
int main()
{ 
    for(int i=1;i<=99;i++)
       	if(work(i)>maxx)
        {
            maxx=work(i);
            ans=i;
        }
   	cout<<ans<<endl;
    return 0;
}

T2

循环，判断是前一个数的约数就将答案+1

#include<bits/stdc++.h>
using namespace std;
long long ans,a[100001],n;
int main()
{ 
    cin>>n;
    cin>>a[1];
    for(int i=2;i<=n;i++)
    {
        cin>>a[i];
        if(a[i-1]%a[i]==0)
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}

T3

只需将每个数相加，减去m后再乘20即可

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,sum;
int main()
{ 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    while(n--)
    {
        sum=0;
        for(int i=1;i<=m;i++)
        {
            cin>>x;
            sum+=20*(x-1);
        }
        cout<<sum<<" ";
    }
    return 0;
}

T4

注意：读入字符串要用 $getline$ 函数

记录遇到的空格数量为 $num$ ，循环判断每个字符是否是空格。若是，则输出 $char(num+65)$ 并$(num+1)%26 $；否则输出原先的字符
注：num+65是因为'A'的ascall码是65

#include<bits/stdc++.h>
using namespace std;
string s;
long long num=0;
int main()
{ 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    getline(cin,s);
    for(int i=0;i<s.size();i++)
		if(s[i]==' ')
        {
            cout<<char(num+65);
            num=(num+1)%26;
        }
    	else
            cout<<s[i];
    return 0;
}

T5

记录一下a[]中1和-1的个数，在进行判断。
1.如果 $r-l+1$ 是奇数，则无论如何都无法满足和为0，输出"sad"
2.如果1的个数或-1的个数小于 $\frac{r-l+1}{2}$ ,则也无法满足，输出"sad"
3.否则输出“happy”

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[200001],x1,x2;
int main()
{ 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x==1)
            x1++;
        else
            x2++;
    }
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        if((r-l+1)%2!=0||x1<(r-l+1)/2||x2<(r-l+1)/2)
            cout<<"sad"<<endl;
        else
            cout<<"happy"<<endl;
    }
    return 0;
}

T6

考察排序的知识和进制转换的知识

1.进制转换

不断将要转换的数取÷8的余数存入ans，再将此数÷8，以此类推

2.排序

1.先按照 $B_i$ 的最低位从大到小排序
2.如果最低位的数一样，那么就按照 $B_i$ 进行从小到大排序
详见cmp函数

#include<bits/stdc++.h>
using namespace std;
long long n,x,b[200001];
bool cmp(long long x1,long long x2)
{
    if(x1%10==x2%10) return x1<x2;
    return (x1%10)>(x2%10);
}
int main()
{ 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;        
        long long sum=0,num=0;
        while(x!=0)
        {
            sum+=pow(10,num)*(x%8);
            num++;
            x/=8;
        }
        b[i]=sum;
    }
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++)
        cout<<b[i]<<" ";
    return 0;
}