请输入文本
2025-07-28 11:43:08
发布于：湖南
为了让大家看到我 T5 的唐诗做法特地写出了这篇全题解
T1
个人难度：红中
由于是 ，所以考虑循环解决，用 代替 。
#include <iostream>
#include <cstdio>
using namespace std;
int a[4];
int n = 3, ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(int i = 1; i <= n; i++) cin >> a[i], ans += (a[i] == i);
cout << (ans >= 2 ? "YES" : "NO");
return 0;
}
时间复杂度 。
T2
个人难度：红上
笑点解析：第一次交交成 Python 了。好在编译错误不算罚时。
显然，我们只需要把每个数变成当前最大值就行了。
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[100005];
int n, mx, ans;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
ans += max(0ll, mx - a[i]);
mx = max(mx, a[i]);
}
cout << ans;
return 0;
}
时间复杂度 。
T3
个人难度：红下
跟我的 PY 说去吧。
- Python 的
str变量有lower和upper函数，可以将字母自动转小/大写。 - Python 也有三目运算符，它的形式是这样的：
a if b else c，其中b为条件，a为b成立的结果，c为b不成立的结果。
print('YES' if input().lower() == input().lower() else 'NO')
时间复杂度 。
T4
个人难度：红上
为了避免因为贪心变橙所以只有 个元素是吧，但是你 T2 都不装了这你还装啥。
依旧考虑循环解决。优先选卡牌的值最大的。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[5], n = 4, k;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> k;
int ans = 0;
for(int i = n; i; i--){
if(k >= a[i]) ans += a[i] * i, k -= a[i];
else ans += k * i, k = 0;
}
cout << ans;
return 0;
}
时间复杂度 。
T5
个人难度：黄中（假）
醋来咯。
冷知识， 宫格不一定是 宫格。它的长度和宽度的范围是 中的任意一个，但是在这题中恰好都是 罢了。
所以我们考虑如何快速求出在 中是否有这个 宫格。
这个，那个，不是暴力就行了吗？
你的____何在
二维字符串哈希
首先回顾一下一维字符串哈希。
例如一个数列 ，判断 是否为它的子段。
我们运用前缀和思想，令 （），。
然后呢，我们只需要判断是否存在一个正整数 使得 即可。显然当 时，符合条件。所以 为 的字段。
而二位字符串哈希就在一维的基础上加一维就行了。
这是矩阵 ，判断 是不是它的子矩阵。
我们首先按照一维字符串哈希的方法，给每一行都哈希一次，，。
然后再按照上面的方法一行一行比对就行了。
但是如果 宫格变了个形状，从 变成了 呢？这样的话就会运行 次，不能通过。
我们可以换个不一样的乘数 （如 ），然后再竖着做一遍哈希操作。
，。
然后呢？回忆一下二维前缀和是怎么查询的。
没错！我们只需要看看是否存在两个正整数 ，使 就行了。很显然，有一个符合条件的答案：。
这样子，我们就可以以 的时间查询所有子矩阵的哈希值，总时间复杂度为 ，与矩阵 的大小无关。
注意到当数据范围很大时这种办法会超过 int 等数据类型容纳的范围，所以我们实现的时候加个取模（自然溢出相当于对 取模）就能在 unsigned long long 范围内完成了。当然，乘数也不能用 了，因为他们有很明显的乘方关系，随便一组数据都会 WA。
注意：这种取模操作不能保证对于所有的数据都能 AC，只是正确率极高。因为有可能出题人构造数据使两个数的哈希值相同（也就是哈希冲突）。如果想降低被卡概率，可以改成随机乘数和模数，最好多开一个随机模数进行验证，这样错误概率可以忽略不计，并且目前还没有较为稳定的卡法。
//555不要卡我
//我直接自然溢出的
#include <iostream>
#include <cstdio>
#define int unsigned long long
using namespace std;
int a[1005][1005], b[1005][1005];
int h[1005][1005], h2[1005][1005];
int n1, m1, n2 = 3, m2 = 3;
//const int C1 = 10, C2 = 1000;
const int C1 = 131, C2 = 998244353;
//乱搞的乘数大家不要学
//C1 -> 行内部的，C2 -> 行之间的
int ksm1 = 1, ksm2 = 1;//预处理 C1^m2，C2^n2
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n1 >> m1;
for(int i = 1; i <= n2; i++) ksm2 *= C2;
for(int i = 1; i <= m2; i++) ksm1 *= C1;
for(int i = 1; i <= n1; i++){
for(int j = 1; j <= m1; j++){
cin >> a[i][j];
h[i][j] = h[i][j - 1] * C1 + a[i][j];
}
}
for(int i = 1; i <= n1; i++){
for(int j = 1; j <= m1; j++){
h[i][j] += h[i - 1][j] * C2;//哈希A矩阵
}
}
for(int i = 1; i <= n2; i++){
for(int j = 1; j <= m2; j++){
cin >> b[i][j];
h2[i][j] = h2[i][j - 1] * C1 + b[i][j];
}
}
for(int i = 1; i <= n2; i++){
for(int j = 1; j <= m2; j++){
h2[i][j] += h2[i - 1][j] * C2;//哈希B矩阵
}
}
for(int i = n2; i <= n1; i++){
for(int j = m2; j <= m1; j++){
if(h[i][j] - h[i - n2][j] * ksm2 - h[i][j - m2] * ksm1 + h[i - n2][j - m2] * ksm1 * ksm2 == h2[n2][m2]){//判断是否出现
cout << "YES\n";
return 0;
}
}
}
cout << "NO\n";
return 0;
}
时间复杂度 ，常数 。
看看能不能当上最优解（
T6
个人难度：橙下
进制转换罢了，直接复制远古代码就行。
#include <iostream>
#include <cstdio>
using namespace std;
string to_k(int k, int x){
if(x < k){
if(x >= 10) return string() + char(x - 10 + 'A');
else return string() + char(x + '0');
}
string cur = to_k(k, x / k);
int xx = x % k;
if(xx >= 10) return cur + char(xx - 10 + 'A');
else return cur + char(xx + '0');
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int a, b, r;
cin >> a >> b >> r;
string s1 = to_k(r, a), s2 = to_k(r, b);
cout << max(s1, s2);
return 0;
}
时间复杂度 。
有帮助，赞一个