欢乐赛#40全题解
2025-02-11 13:09:54
发布于：北京
欢乐赛#40全题解
题目分析
本题要求找出 2025 年之后的下一个闰年年份。闰年的判断规则是：能被 4 整除但不能被 100 整除的年份为闰年，此外能被 400 整除的年份也是闰年。
解题思路
我们可以从 2026 年开始逐年检查，直到找到符合闰年规则的年份为止。
代码实现
#include <iostream>
using namespace std;
// 判断是否为闰年的函数
bool year(int year) {
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
int main() {
// 从2026年开始检查
int Year = 2026;
while (!year(Year)) {
// 如果不是闰年，年份加1继续检查
Year++;
}
// 输出找到的闰年年份
cout << Year << endl;
return 0;
}
代码解释
year函数：
该函数用于判断一个年份是否为闰年。根据闰年的判断规则，能被 4 整除但不能被 100 整除的年份为闰年，此外能被 400 整除的年份也是闰年。函数返回一个布尔值，表示该年份是否为闰年。
main函数：
初始化Year为 2026，表示从 2026 年开始检查。使用while循环，只要Year不是闰年，就将Year加 1 继续检查。当找到闰年时，循环结束，输出该闰年的年份。
复杂度分析
时间复杂度 最坏情况下，需要检查多个年份才能找到下一个闰年，时间复杂度为 O(n) ，其中n是需要检查的年份数。
空间复杂度 只使用了常数级的额外空间，空间复杂度为 O(1)。
题目分析
本题要求求出114514的n次方的个位数字
解题思路
根据题目描述，我们可以观察到个位数字的循环规律。具体来说，我们只需要关注114514的个位数字，即4的幂次方的个位数字变化规律。
首先，我们观察4的幂次方的个位数字：
4^1 = 4，个位数字是4
4^2 = 16，个位数字是6
4^3 = 64，个位数字是4
4^4 = 256，个位数字是6
我们可以看到，4的幂次方的个位数字在4和6之间循环。因此，我们可以得出结论：
当n是奇数时，4的n次方的个位数字是4
当n是偶数时，4的n次方的个位数字是6
基于这个规律，我们可以编写一个简单的程序来解决这个问题。程序的逻辑如下：
读取输入的测试数据组数T。
对于每一组测试数据，读取整数n。
根据n的奇偶性，输出4或6。
代码实现
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
if (n % 2 == 1) {
cout << 4 << endl;
} else {
cout << 6 << endl;
}
}
return 0;
}
代码解释
#include <iostream> 包含输入输出流库。
using namespace std; 使用标准命名空间。
int main() 主函数。
int T; cin >> T; 读取测试数据组数T。
while (T--) 循环T次，处理每一组测试数据。
long long n; cin >> n; 读取整数n。
if (n % 2 == 1) 判断n是否为奇数。
cout << 4 << endl; 如果n是奇数，输出4。
else 否则。
cout << 6 << endl; 如果n是偶数，输出6。
return 0; 程序结束。
复杂度分析
时间复杂度 O(T) ，其中T是测试数据组数。
空间复杂度 O(1) ，只使用了常数级的额外空间。
题目分析
题目要求计算114514的n次方取模998244353的值。
解题思路
根据题目描述，我们需要处理大整数的幂运算并取模，这通常涉及到快速幂算法以提高效率。
快速幂算法
快速幂算法可以在 O(log n) 的时间复杂度内计算a的n次方mod m。其基本思想是将指数n转换为二进制表示，然后根据二进制位上的值来决定是否将当前的幂次结果乘到最终结果中。
算法步骤
初始化：设结果为 1，底数为a。
循环：当n>0时，执行以下操作：
如果n的最低位为 1，则将当前的底数乘到结果中，并对m取模。
将底数平方，并对m取模。
将n右移一位（相当于除以 2）。
输出结果：最终的结果即为a的n次方 mod m。
代码实现
#include <iostream>
using namespace std;
typedef long long ll;
ll fast(ll base, ll exp, ll mod) {
ll result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 == 1) { // 如果exp的最低位是1
result = (result * base) % mod;
}
base = (base * base) % mod; // 平方底数
exp >>= 1; // 右移exp
}
return result;
}
int main() {
ll n;
cin >> n;
ll base = 114514;
ll mod = 998244353;
cout << fast(base, n, mod);
return 0;
}
代码解释
输入 从标准输入读取一个整数n
快速幂计算：使用 fast 函数计算114514的n次方 mod 998244353
输出：将计算结果输出到标准输出。
复杂度分析
时间复杂度 O(log n) ，因为每次循环中n都会减半。
空间复杂度 O(1) ，只使用了常数级的额外空间。
题目描述
给一个数n,求第n个质数是多少？
解题思路
质数判断 首先，我们需要一个函数来判断一个数是否为质数。质数是指只能被1和自身整除的数。为了提高效率，我们只需要检查到该数的平方根即可。
寻找第n个质数 从2开始，逐个检查每个数是否为质数，直到找到第n个质数为止。
代码实现
#include <iostream>
#include <cmath>
using namespace std;
// 判断一个数是否为质数
bool ip(int num) {
if (num <= 1) return false;
if (num == 2) return true; // 2是质数
if (num % 2 == 0) return false; // 偶数不是质数（除了2）
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) return false;
}
return true;
}
// 找到第n个质数
int np(int n) {
int count = 0;
int num = 2; // 从2开始判断
while (count < n) {
if (ip(num)) {
count++;
}
num++;
}
return num - 1;
}
int main() {
int n;
cin >> n;
cout << np(n) << endl;
return 0;
}
代码解释
ip函数
如果输入的数小于等于1，则不是质数。
如果输入的数是2，则是质数。
如果输入的数是偶数且不等于2，则不是质数。
对于大于2的奇数，检查从3到其平方根之间的所有奇数是否能整除该数。如果有能整除的，则不是质数。
np函数
初始化计数器count为0，表示已找到的质数个数。
从2开始逐个检查每个数是否为质数。
如果找到一个质数，则计数器加1。
当计数器等于n时，返回当前的数减1（因为循环结束后num会多加1）。
main函数
读取输入的整数n。
调用np函数找到第n个质数并输出。
题目理解
我们需要将所有学生的座位号 a[i] 调整成与学号 i 不相等，且要求交换次数最少。由于 a 是 1 到 n 的全排列，我们可以利用排列的性质来解决这个问题。
解题思路
我们可以将问题转化为 排列的错位排列（Derangement） 问题。错位排列是指排列中没有任何一个元素出现在其原始位置。我们的目标是通过最少的交换次数，将给定的排列 a 调整为一个错位排列。
错位排列的性质
如果排列 a 已经是错位排列（即 a[i] != i 对所有 i），则不需要任何交换。
否则，我们需要通过交换将排列调整为错位排列。
最少交换次数
如果排列中有 k 个元素在正确的位置（即 a[i] == i），那么最少需要 ceil(k / 2) 次交换。
这是因为每次交换可以修复两个错误的位置。
算法步骤
统计错误位置
遍历排列 a，统计有多少个元素满足 a[i] == i。
计算最少交换次数
如果错误位置的数量为 k，则最少交换次数为 ceil(k / 2)。
代码实现
#include <iostream>
#include <vector>
using namespace std;
int swaps(vector<int>& a, int n) {
int ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] == i + 1) { // 注意：学号从 1 开始，数组下标从 0 开始
ans++;
}
}
return (ans + 1) / 2; // ceil(ans / 2)
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << swaps(a, n) << endl;
}
return 0;
}
代码解释
函数 swaps
遍历排列 a，统计有多少个元素满足 a[i] == i + 1（因为学号从 1 开始，数组下标从 0 开始）。
返回 ceil(ans/ 2)，即 (ans+ 1) / 2。
主函数 main
读取测试用例的数量 T。
对于每个测试用例，读取 n 和数组 a。
调用 swaps函数并输出结果。
复杂度分析
时间复杂度 遍历排列 a 一次，时间复杂度为 O(n)。总体时间复杂度为 O(n)。
空间复杂度 只使用了常数级别的额外空间，空间复杂度为 O(1)。
题目理解
我们需要找到一个区间 [l, r]，使得对于区间内的每一个整数 i，n 都是 i 的倍数。换句话说，区间内的每一个数都是 n 的因子。我们的目标是找到满足这个条件的最长区间，并输出其长度。
解题思路
理解条件 对于区间 [l, r] 中的每一个 i，n % i == 0。这意味着 i 必须是 n 的因子。
最长区间 我们需要找到一个最长的连续区间，使得区间内的所有数都是 n 的因子。
因子性质 n 的因子是成对出现的。例如，如果 i 是 n 的因子，那么 n / i 也是 n 的因子。
区间选择 最长的区间应该是从 1 开始，因为 1 是所有整数的因子。然后我们逐步增加 r，直到 r 不再是 n 的因子。
算法步骤
初始化 从 l = 1 开始，逐步增加 r，直到 r 不再是 n 的因子。
计算区间长度 区间的长度就是 r - l + 1。
输出结果 对于每个测试用例，输出最长区间的长度。
代码实现
#include <iostream>
using namespace std;
long long find(long long n) {
long long l = 1;
long long r = 1;
while (n % r == 0) {
r++;
}
return r - 1;
}
int main() {
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
cout << find(n) << endl;
}
return 0;
}
代码解释
函数 find
初始化 l 和 r 为 1。
使用 while 循环逐步增加 r，直到 n % r != 0。
返回 r - 1，即最长区间的长度。
主函数 main
读取测试用例的数量 T。
对于每个测试用例，读取 n 并调用 find函数。
输出结果。
复杂度分析
时间复杂度 对于每个测试用例，find函数的时间复杂度是 O(r)，其中 r 是 n 的最大因子。由于 r 最大为 n，所以最坏情况下时间复杂度为 O(n)。但由于 n 可以达到10的18次方，这个算法在实际应用中可能不够高效。
空间复杂度 只使用了常数级别的额外空间，空间复杂度为 O(1)。
优化思路
对于大数 n，直接遍历 1 到 n 的因子会导致时间复杂度过高。可以考虑以下优化
因子分解 通过因子分解 n，找到所有因子，然后找到最长的连续因子区间。
数学性质 利用因子的数学性质，减少不必要的计算。
优化后的代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> get(long long n) {
vector<long long> f;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
f.push_back(i);
if (i != n / i) {
f.push_back(n / i);
}
}
}
sort(f.begin(), f.end());
return f;
}
long long find(long long n) {
vector<long long> f = get(n);
long long maxx = 1;
long long ans = 1;
for (size_t i = 1; i < f.size(); i++) {
if (f[i] == f[i-1] + 1) {
ans++;
maxx = max(maxx, ans);
} else {
ans = 1;
}
}
return maxx;
}
int main() {
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
cout << find(n) << endl;
}
return 0;
}
优化后的代码解释
函数 get
通过遍历 1 到 sqrt(n)，找到 n 的所有因子。
将因子排序后返回。
函数 find：
获取 n 的所有因子。
遍历因子数组，找到最长的连续因子区间。
主函数 main
读取测试用例的数量 T。
对于每个测试用例，读取 n 并调用 find函数。
输出结果。
优化后的复杂度分析
时间复杂度 因子分解的时间复杂度为 O(sqrt(n))，排序的时间复杂度为 O(k log k)，其中 k 是因子的数量。总体时间复杂度为 O(sqrt(n) + k log k)。
空间复杂度 存储因子的空间复杂度为 O(k)，其中 k 是因子的数量。
总结
通过优化，我们能够更高效地找到最长的因子区间，特别是在处理大数 n 时，优化后的算法能够显著减少计算时间。
有帮助，赞一个