欢乐赛#40不正经题解
2025-02-10 12:29:44
发布于：广东
173阅读
0回复
0点赞
T1
显然，闰年的 月有 天。
通过枚举法我们可知下一个闰年的年份为 年，输出 。
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << 2028;
return 0;
}
时间复杂度：。
T2
我们可以先找规律，看看 个位与 的关系。
由于 ，所以我们可以在乘法的过程中取模。
#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;
}
结果发现：
当 是奇数时， 个位为 。
当 是偶数时， 个位为 。
所以本题代码如下：
#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;
}
时间复杂度：。
T3
枚举到 次幂即可。，记得开 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;
}
时间复杂度：。
T4
模拟题，枚举直至找到第 个质数即可。
#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;
}
}
}
时间复杂度：。
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;
}
时间复杂度：。
T6
显然当 $l=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;
}
时间复杂度：。
DS说的，我感觉这种题没必要
有帮助，赞一个