欢乐赛#40题解

yanghongzheng

2025-02-14 12:33:14

发布于：北京

87阅读

0回复

0点赞

前言：

这篇文章有一些脚注，这些脚注是为了帮助理解一些词汇。

正文：

T1:

这是一道很水的题，只要用C++中的cout语句或Python中的print()函数即可。

C++代码：

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

Python代码：

print(2028)

T2:

这一题因为 $n$ 最大可以达到 $10^9$ ，所以如果直接计算就会TLE，所以我们就要用基础的数学知识进行推理。
首先我们要知道 $114514^n$ 的最后一位和 $4^n$ 的最后一位是一样的。也就是说我们进行推理的时候可以计算 $4^n$ 。
那么我们开始进行推理：
$4^1=4$ ，最后一位是 $4$ 。
$4^2=16$ ，最后一位是 $6$ 。
$4^3=64$ ，最后一位是 $4$ 。
$4^4=256$ ，最后一位是 $6$ 。
我们发现，第一轮为 $4$ ，第二轮为 $6$ ，第三轮为 $4$ ，第4轮为 $6$ ……
在 $n$ 为奇数时，最后一位是 $4$ ；在 $n$ 为偶数时，最后一位是 $6$ ；
我们就可以写出如下代码：

C++代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n;
    cin >> t;
    for(int i=0;i<t;i++){
        cin >> n;
        if(n%2==1){
            cout << 4 << endl;
        }else{
            cout << 6 << endl;
        }
    }
    return 0;
}

Python代码：

t = int(input())
for i in range(t):
    n = int(input())
    if n % 2 == 1:
        print(4)
    else:
        print(6)

T3:

这一题因为 $n$ 最大可以达到 $10^6$ ，如果直接计算 $114514^n$ 再取模，数值会非常大，计算会非常慢。所以我们要使用快速幂^[1]进行计算。

我们使用如下步骤进行计算：
首先设定初始值 $s = 1$ ， $d = 114514$ 。
其次通过二进制拆解指数 $n$ ，如果当前位为 1，则将 $s$ 乘上当前的底数 $d$ 并与 $998244353$ 取模；
然后每次将 $d$ 平方，同时对 $998244353$ 再次进行取模，使得数值不会过大；
最后将 $n$ 右移一位，继续计算，直到 $n = 0$ 。

C++代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    long long s = 1, d = 114514;
    while(n > 0){
        if(n % 2 == 1){
            s *= d;
            s %= 998244353;
        }
        d *= d;
        d %= 998244353;
        n /= 2;
    }
    cout << s;
    return 0;
}

Python代码：

n = int(input())
s = 1
d = 114514
while n > 0:
    if n % 2 == 1:
        s *= d
        s %= 998244353
    d **= 2
    d %= 998244353
    n //= 2
print(s)

T4:

这道题要求我们求出第n个质数^[2]。

也就是说我们只要从2开始逐个判断每个数是否为质数，就可以找到第n个质数。

C++代码：

#include<bits/stdc++.h>
using namespace std;
bool is_prime(int n){
    if(n == 1) return false;
    for(int i = 2;i < n;i++){
        if(n % i == 0) return false;
    }
    return true;
}
int main(){
    int n;
    cin >> n;
    int i = 0;
    int p[100010];
    int cnt = 0;
    
    while(cnt < n){
        i++;
        if(is_prime(i)){
            p[cnt] = i;
            cnt++;
        }
    }
    
    cout << p[n - 1];
    return 0;
}

Python 代码：

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,n):
        if n % i == 0:
            return False
    return True
n = int(input())
i = 0
p = []
while len(p) < n:
    i += 1
    if is_prime(i):
        p.append(i)
print(p[n-1])

T5:

由于座位号是1到n的全排列，我们只需要关注那些座位号与学号相同的学生，记其数量为cnt。
每次交换可同时调整两个学生，因此最优策略是将这些学生成对交换。
最终交换次数最少为(cnt + 1) / 2。

C++代码：

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

Python代码：

t = int(input())
for i in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    cnt = 0
    for j in range(n):
        if l[j] == j + 1:
            cnt += 1
    print((cnt + 1) // 2)

T6:

我们可以在题目中固定 l=1，这样可以保证得到满足条件的最长区间。
也就是说，只需要从 1 开始遍历可能的 r 值即可。

C++代码：

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

Python代码：

t = int(input())
for i in range(t):
    n = int(input())
    j = 1
    while j <= n:
        if n % j != 0:
            break
        j += 1
    print(j - 1)