欢乐赛#40题解
2025-02-14 12:33:14
发布于：北京
85阅读
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:
这一题因为 最大可以达到 ，所以如果直接计算就会TLE，所以我们就要用基础的数学知识进行推理。
首先我们要知道 的最后一位和 的最后一位是一样的。也就是说我们进行推理的时候可以计算 。
那么我们开始进行推理：
，最后一位是 。
，最后一位是 。
，最后一位是 。
，最后一位是 。
我们发现，第一轮为，第二轮为，第三轮为，第4轮为……
在为奇数时，最后一位是 ；在为偶数时，最后一位是 ；
我们就可以写出如下代码：
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:
这一题因为 最大可以达到 ，如果直接计算 再取模，数值会非常大，计算会非常慢。所以我们要使用快速幂[1]进行计算。
我们使用如下步骤进行计算：
首先设定初始值 ，。
其次通过二进制拆解指数 ，如果当前位为 1，则将 乘上当前的底数 并与 取模；
然后每次将 平方，同时对 再次进行取模，使得数值不会过大；
最后将 右移一位，继续计算，直到 。
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)
有帮助，赞一个