ACGO欢乐赛#40全题解！

dream_陆军展览

2025-02-09 22:14:45

发布于：江苏

11阅读

0回复

0点赞

T1
题目
2025年后的第一个闰年是2028年，直接输出即可。
代码如下：

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

T2
题目
由于数据范围很大，直接暴力是不现实的，因此我们需要找规律：

$4^1=4$ ，个位为 $4$ 。
$4^2=16$ ，个位为 $6$ 。
$4^3=64$ ，个位为 $4$ 。
$4^4=256$ ，个位为 $6$ 。

因此，不难看出，当 $n\bmod2=0$ 时，个位为 $6$ ，当 $n\bmod2=1$ 时，个位为 $4$ 。
代码如下：

#include<bits/stdc++.h>
using namespace std;
void solve()//多测函数
{
    int n;
    cin>>n;
    if(n%2==1)cout<<4<<endl;
    if(n%2==0)cout<<6<<endl;
    return ;
}
int main()
{
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

T3
题目
模拟即可，记得开 long long，时间复杂度为 $\mathrm{O} (n)$ 。

#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
int main()
{
    long long n,ans=1;cin>>n;
    for(int i=1;i<=n;i++)
    {
        ans*=114514;
        ans%=mod;
    }
    cout<<ans;
    return 0;
}

T4
题目
当然可以将每个数依次进行判断，得出质数表，这里讲一种比较高效的算法：埃氏筛法。将 $2$ 到 $n$ 之间的整数存在一个 bool 数组中，先全部标记为 true，从 $2$ 开始，把 $2$ 的倍数全部标记为 false，再往下循环，发现下一个质数是 $3$ ，再把 $3$ 的倍数全部标记为 false，再往下循环，发现下一个质数是 $5$ ，再把 $5$ 的倍数全部标记为 false，以此类推，便能把范围内的质数筛出来，过程中把质数存在数组中，便能得到第 $n$ 个质数。
经计算，第 $2025$ 个质数在 $20000$ 以内，只要把 $20000$ 以内的质数筛出来即可。
时间复杂度是一个常数，数量级为 $10^4$ 。
代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool ip[20005];
vector<int>prm;//存储质数
void f(int n)//埃氏筛函数，筛出n以内的质数
{
    ip[0]=ip[1]=0;
    for(int i=2;i<=n;i++)ip[i]=1;
    for(int i=2;i<=n;i++)
    {
        if(ip[i])
        {
            prm.push_back(i);
            if(i*i>n)continue;
            for(int j=i*i;j<=n;j+=i)ip[j]=0;
        }
    }
    return ;
}
signed main()
{
    f(20000);
    int n;cin>>n;
    cout<<prm[n-1];//因为vector的下标从0开始，所以应该访问prm[n-1]
    return 0;
}

T5
题目
记录“不快乐”的学生数量 $m$ ，如果是 $m$ 偶数，那么成对交换，如果 $m$ 是奇数，那么先将前 $m-1$ 个学生成对交换，再把最后一个学生进行一次合理的交换，最终的交换次数为 $\lfloor \frac{m+1}{2} \rfloor$ 。时间复杂度为 $\mathrm{O} (Tn)$ 。
代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1005],cnt;
void solve()//多测函数
{
    cin>>n;
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==i)cnt++;//记录“不快乐”的学生数量
    }
    cout<<(cnt+1)/2<<endl;//输出结果
    return ;
}
signed main()
{
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

T6
题目
我们知道，对于一个正整数 $m$ ，从 $m$ 开始，每次增加 $m$ ，所得的结果一定能被 $m$ 整除。因此可以得出，对于区间 $[1,r-l+1]$ 中的任意一个数，区间 $[l,r]$ 中一定能找到一个数是它的整数倍。所以在题目中，我们可以假定 $l=1$ ，这样一定能得到最大的满足条件的区间。所以将 $r$ 的值从 $1$ 开始循环即可。每次的时间复杂度接近 $\mathrm{O} (1)$ 。
代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,i;
void solve()
{
    cin>>n;
    for(i=1;;i++)if(n%i)break;
    cout<<i-1<<endl;
    return ;
}
signed main()
{
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论