欢乐赛#40不正经题解

‮队团加不）童帅_者仇复

2025-02-10 12:29:44

发布于：广东

169阅读

0回复

0点赞

T1

显然，闰年的 $2$ 月有 $29$ 天。

通过枚举法我们可知下一个闰年的年份为 $2028$ 年，输出 $2028$ 。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cout << 2028;

	return 0;
}

时间复杂度： $O(1)$ 。

T2

我们可以先找规律，看看 $114514^N$ 个位与 $N$ 的关系。

由于 $AB\mod C=((A\mod C)\times B)\mod C$ ，所以我们可以在乘法的过程中取模。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int cur = 1;
	for(int i = 1;; i++){
		cur *= 114514;//计算114514的i次幂
		cur %= 10;//取个位
		cout << cur << '\n';
	}
	

	return 0;
}

结果发现：

当 $N$ 是奇数时， $114514^N$ 个位为 $4$ 。

当 $N$ 是偶数时， $114514^N$ 个位为 $6$ 。

所以本题代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		if(n % 2 == 0) cout << "6\n";
		else cout << "4\n";
	}
	

	return 0;
}

时间复杂度： $O(T)$ 。

T3

枚举到 $N$ 次幂即可。 $998244352\times 114514\gt 2^{31}-1$ ，记得开 long long。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	long long cur = 1;
	for(int i = 1; i <= n; i++){
		cur *= 114514;//计算i次幂
		cur %= 998244353;
	}
	cout << cur;
	

	return 0;
}

时间复杂度： $O(N)$ 。

T4

模拟题，枚举直至找到第 $N$ 个质数即可。

#include <iostream>
#include <cstdio>
using namespace std;
bool check(int n){//判断是不是质数
	if(n < 2) return 0;
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0) return 0;
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i = 2, ct = 0; ct < n; i++){
		if(check(i)) ct++;
		if(ct == n){//如果恰好是第N个质数就输出
			cout << i << '\n';
			return 0;
		}
	}
}

时间复杂度： $O(N\ln N\sqrt{N\ln N})$ 。

T5

记录下不“快乐”的学生，两两交换不“快乐的学生”让他们“快乐”。

如果最后还剩一个，那让他和任意一个学号不等于他的座位号并且座位号不等于他的学号的人交换，可以证明存在这样的学生。

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
void solve(){
	int n, ct = 0;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], ct += (a[i] == i);//记录下学生人数
	cout << ct / 2 + ct % 2 << '\n';//交换
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(TN)$ 。

T6

~~显然当 $l=1$ 时有最长的区间。这里空白处太小了，写不下证明。~~

设 $N$ 最小的不能整除的正整数为 $M$ 。

$\because$ 当 $N$ 能整除一个数时，它一定能整除这个数的所有的因子，

又 $\because$ 每相邻 $M$ 个数内必定有一个数是 $M$ 的倍数（对 $M$ 取余可知），

$\therefore$ 最长的区间长度一定不超过 $M-1$ 。

那么，我们能不能构造一个长度为 $M-1$ 的区间呢？

显然 $[1,M)$ 就是一个合法的区间。

故答案为 $M-1$ 。

#include <iostream>
#include <cstdio>
using namespace std;
void solve(){
	long long n, i = 1;
	cin >> n;
	for(; n % i == 0; i++);
	cout << i - 1 << '\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}