参考题解:
A 题
题目 大意
现有 由 r,g,b,R,G,B 6 个字符所组成的 字符串 s, 问是否有
- 字符 r 是否出现在 R 前面
- 字符 g 是否出现在 G 前面
- 字符 b 是否出现在 G 前面
样例
略
时间复杂度 $O(n)$
C++ 代码
#include <bits/stdc++.h>
#define x first
#define y second
//#define IOS cout.tie(0), cin.tie(0)
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
int t;
int main(void)
{
cin >> t;
while(t --)
{
map<char, int> q;
string c;
cin >> c;
bool f = 1;
for(auto i : c)
{
if(i >= 'a' && i <= 'z')
{
char t = i - 'a' + 'A';
q[t] ++;
}
else if(!q[i])
{
f = 0;
break;
}
}
if(f) puts("YES");
else puts("NO");
}
return 0;
}
B 题
题目 大意
输出 n 个,满足 $p_i ≠ p_{i - 1} + p_{i - 2} ,3 <= i <= n$ 的数列
样例
略
算法 1 模拟(角度 dfs)
时间复杂度 $O(n!)$
C++ 代码
#include <bits/stdc++.h>
#define x first
#define y second
//#define IOS cout.tie(0), cin.tie(0)
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 110;
bool st[N];
int c[N];
int t;
int n;
bool dfs(int f)
{
if(f == n)
{
for(int i = 0; i < n; i ++)
cout << c[i] << " ";
cout << endl;
return 1;
}
for(int i = 1; i <= n; i ++)
{
if(f >= 2)
{
if(!st[i] && st[c[f - 1]] && st[c[f - 2]])
{
c[f] = i;
if(c[f - 2] + c[f - 1] != c[f])
{
st[i] = 1;
if(dfs(f + 1)) return 1;
st[i] = 0;
}
}
}
else
{
if(!st[i])
{
c[f] = i;
st[i] = 1;
if(dfs(f + 1)) return 1;
st[i] = 0;
}
}
}
return 0; // 不要忘了
}
int main(void)
{
cin >> t;
while(t --)
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
memset(st, 0, sizeof st);
memset(c, 0, sizeof c);
c[0] = i;
st[i] = 1;
dfs(1);
}
}
return 0;
}
算法 2 根据 倒序的 性质
时间复杂度 $O(n^2)$
C++ 代码
#include <bits/stdc++.h>
#define x first
#define y second
//#define IOS cout.tie(0), cin.tie(0)
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 110;
int main(void)
{
int t;
cin >> t;
while(t --)
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cout << i << " ";
for(int j = n; j >= 1; j --)
{
if(j != i)
{
cout << j << " ";
}
}
cout << endl;
}
}
return 0;
}
C 题
题目 大意
现给定长度 $n$ 的数列 $a$ 和 $x$ ,对于 $0 <= k <= n$ ,你需要将其中 $k$ 个元素加上 $x$ ,使得 $\underset{1 \leq l \leq r \leq n}\max{(\displaystyle \sum_{l = 1}^n \displaystyle \sum_{r = l + 1}^n \ a_l + … + a_r )}$
注意,子数组不一定要包括所有增加的元素。
输出 $k$ 个答案,分别对应 $k = 0…n $ 时,这个部分和的最大值。
样例
input
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4
output
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8
思路:
- cnt[i] 表示 a数组中 长度为 i 的区间和 的 最大值
- 然后枚举 k 个增加的元素,求 $max(cnt[i] + k*x), k <= i <= n$
时间复杂度 $O(n^2)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], cnt[N], s[N];
int t, INF = 0x3f3f3f3f;
int main(void)
{
cin >> t;
while(t --)
{
int n, x;
memset(cnt, -0x3f, sizeof cnt);
memset(s, 0, sizeof s);
cin >> n >> x;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
// 枚举所有长度为 l 区间的最小和
for(int l = 1; l <= n; l ++)
{
for(int j = 1; j + l - 1 <= n; j ++)
{
cnt[l] = max(cnt[l], s[j + l - 1] - s[j - 1]);
}
}
int ans = 0;
for(int k = 0; k <= n; k ++)
{
//ans = 0; 注意,子数组不一定要包括所有增加的元素。
for(int i = k; i <= n; i ++)
ans = max(ans, cnt[i] + k * x);
cout << ans << " ";
}
cout << endl;
}
}
D 题
题目 大意
一个覆盖问题
思路
从后往前想 + 快速幂
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll mod = 998244353;
int t;
int x[N], y[N];
int xx[N], yy[N];
ll ksm(ll a, ll b)
{
ll sum = 1;
while(b)
{
if(b & 1) sum = sum * a % mod;
a = a * a % mod;
b >>= 1;
}
return sum;
}
int main(void)
{
cin >> t;
while(t --)
{
memset(xx, 0, sizeof xx);
memset(yy, 0, sizeof yy);
int n, m, k, q;
cin >> n >> m >> k >> q;
for(int i = 1; i <= q; i ++)
{
cin >> x[i] >> y[i];
}
int xh = n, yh = m;
ll cnt = 0;
// 找到所有最后覆盖的区域
for(int i = q; i >= 1; i --)
{
if(!xx[x[i]] || !yy[y[i]])
{
cnt ++;
if(!xx[x[i]]) xh --, xx[x[i]] = 1;
if(!yy[y[i]]) yh --, yy[y[i]] = 1;
if(!yh || !xh) break;
}
}
cout << ksm(k, cnt) << endl;
}
return 0;
}
E 题
题目 大意
一个机器人在一个n*n的网格中,只能向右(R)或向下(D)走
再保证不能走出网格,且完成所有初始指令,指令可以增加,如D可以增加为DD、DDD,R可以增加为RR、RRR。
问最终最多可以经过多少格子
思路
找到x, y 方向最大的移动范围, 根据字符串中’D’或’R’ 来判断每行每列有多少个不能到达
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
void solve()
{
LL n;
string c;
cin >> n;
cin >> c;
LL td = 0, tr = 0;
LL l = c.size();
for(int i = 0; i < l; i ++)
{
if(c[i] == 'D') td ++;
else tr ++;
}
if(!td || !tr) {cout << n << endl; return ;}
LL x = 1, y = 1;
// x, y 可以扩展的最多的格子数
LL char_x = n - 1 - td, char_y = n - 1 - tr;
LL sum = 0;
// 此循环计算 所有不能经过的点
for(int i = 0; i < l; i ++)
{
if(c[i] == 'D')
{
if(y == 1) sum += n - 1;
else sum += n - y - char_y;
x ++;
}else
{
if(x == 1) sum += n - 1;
else sum += n - x - char_x;
y ++;
}
}
cout << n * n - sum << endl;
}
int main()
{
int t;
cin >> t;
while(t --)
{
solve();
}
return 0;
}