A Is it rated?
【题目链接】
原题链接：A – Is it rated?
【考点】
嵌套判断
【题目大意】
有两个分区，有不同的评分区间，给一个评分 r 和分区 x，判断是否在评分区间中。
【解析】
先判断在属于哪个分区，再判断是否在该分区评分区间中。
【难度】
GESP一级
【代码参考】
#include<bits/stdc++.h>
using namespace std;
int main(){
int r, x;
cin >> r >> x;
if(x == 1){
if(r >= 1600 && r <= 2999) cout << "Yes";
else cout << "No";
}
else{
if(r >= 1200 && r <= 2399) cout << "Yes";
else cout << "No";
}
return 0;
}
B Not All
【题目链接】
原题链接：B – Not All
【考点】
枚举，数组计数法
【题目大意】
给一段长度为 n 的序列 A 和一个正整数 m，你的目标是通过在 0 和 N 次之间执行此操作（包括两端）使以下条件为假：删除 A 的最后一个元素。条件： A 包含从 1 到 M 的所有整数。找到所需的最少操作次数。
【解析】
使用数组 cnt 标记每个数字出现次数，从后往前遍历数组 a，每次删除最后一个数，判断数组 cnt 下标 1~m 是否为0，有为0的则输出操作次数，否则继续删减。
【难度】
GESP三级
【代码参考】
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m, a[105], cnt[105], ans = 0, f = 1;
cin >> n >> m;
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n; i++){
cin >> a[i];
cnt[a[i]]++;
}
for(int i = n; i >= 1; i--){
for(int i = 1; i <= m; i++){
if(cnt[i] == 0){
f = 0;
break;
}
}
if(!f) break;
cnt[a[i]]--;
ans++;
}
cout << ans;
return 0;
}
C Sum of Product
【题目链接】
原题链接：C – Sum of Product
【考点】
前缀和
【题目大意】
给定一个长度为 N 的整数序列 A=(A1,A2,…,AN)，计算 
【解析】
可以优化为 Ai * （Ai+1 + Ai+2 …… + Aj + AN），那么就转化为Ai * Ai+1~N 的和。使用前缀和快速计算出区间和，减低时间复杂度。
【难度】
GESP四级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 +5;
long long a[N], pre[N], n;
long long ans;
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
//pre[1] = a[1];
for(int i = 1; i <= n; i++){
pre[i] = pre[i-1] + a[i];
}
for(int i = 1; i <= n; i++){
ans += a[i] * (pre[n] - pre[i]);
}
cout << ans;
} D Escape Route
【题目链接】
原题链接：D – Escape Route
【考点】
广度优先搜索BFS
【题目大意】
在每一块区域标记最近逃生出口的方向。
【解析】
以每个逃生出口为起点，使用多源 BFS 算法遍历能够到达的位置，并附上相反方向。
【难度】
GESP六级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, vis[N][N]; // vis数组记录是否已访问，-1表示未访问
char ma[N][N], ans[N][N]; // ma存储原始地图，ans存储标记后的地图
int dir[4][2] = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右、下、左、上四个方向
string g = "<^>v"; // 方向字符，注意顺序与dir数组的映射关系
struct node{
int x, y;
};
queue<node> q; // BFS队列
void bfs(){
while(!q.empty()){
node d = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int tx = d.x + dir[i][0], ty = d.y + dir[i][1]; // 计算新位置
// 判断是否越界或遇到墙壁
if(tx < 1 || ty < 1 || tx > n || ty > m || ma[tx][ty] == '#') continue;
if(vis[tx][ty] == -1){ // 如果未访问过
vis[tx][ty] = 0; // 标记为已访问
q.push({tx, ty}); // 加入队列
ans[tx][ty] = g[i]; // 记录方向字符（注意i与g的映射关系）
}
}
}
}
int main(){
cin >> n >> m;
memset(vis, -1, sizeof(vis)); // 初始化vis数组为-1（未访问）
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> ma[i][j];
if(ma[i][j] == 'E'){ // 将所有逃生出口作为BFS起点
q.push({i, j});
vis[i][j] = 0; // 标记为已访问
}
}
}
bfs(); // 执行多源BFS
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(ma[i][j] == '.') cout << ans[i][j]; // 输出标记后的方向
else cout << ma[i][j]; // 原样输出墙壁和逃生出口
}
cout << endl;
}
}E Fruit Lineup
【题目链接】
原题链接：E – Fruit Lineup
【考点】
枚举，组合数学，快速幂，逆元
【题目大意】
你有 A 个苹果，B 个橙子，C 个香蕉，和 D 个葡萄。需要将这些水果排成一行，同时满足以下条件： （1）所有苹果必须放在所有香蕉的左边。（2） 所有苹果必须放在所有葡萄的左边。 （3）所有橙子必须放在所有葡萄的左边。水果之间不可区分，即相同类型的水果视为完全一样。需要计算满足条件的排列方式数目，并将结果对 998244353 取模。
【解析】
组合数学基础：题目本质上是在满足特定位置约束的条件下，计算不同水果的排列方式。组合数学中的组合数（C (n, k)）是解决这类问题的关键。
条件分析：
苹果必须在香蕉和葡萄的左边 → 苹果的位置必须全部在最左边的连续位置。
橙子必须在葡萄的左边 → 橙子的位置必须全部在葡萄的左边。
枚举分割点：通过枚举苹果和香蕉之间的分割点 i，计算每种分割情况下的合法排列数。
组合数计算：利用预处理的阶乘和逆元数组，快速计算组合数。
逆元讲解：
逆元定义：若 a * b ≡ 1 (mod m)，则 b 是 a 的逆元，记作 a^−1 mod m。
费马小定理：当 m 是质数且 a 与 m 互质时，a^(m−1) ≡ 1 (mod m)，因此 a 的逆元为 a^(m−2) mod m。
【难度】
GESP八级
【代码参考】
#include <bits/stdc++.h>
using namespace std;
const long long N = 5e6 + 5, mod = 998244353;
long long a, b, c, d, f[N], i_f[N]; // 存储水果数量、阶乘和逆元数组
// 快速幂函数，计算 k^p % mod
int _pow(long long k, long long p){
long long res = 1;
while(p){
if(p & 1){ // 如果当前位为1
res = res * k % mod; // 累乘当前基数
}
k = k * k % mod; // 基数平方
p >>= 1; // 指数右移一位
}
return res;
}
// 计算组合数 C(n, m) % mod
long long F(long long n, long long m){
if(n < m || n < 0 || m < 0) return 0; // 处理非法情况
else{
return f[n] * i_f[m] % mod * i_f[n-m] % mod;
}
}
int main(){
cin >> a >> b >> c >> d;
long long n = a + b + c + d; // 计算水果总数
f[0] = 1; // 预处理阶乘数组
for(int i = 1; i <= n; i++){ // 递推计算阶乘
f[i] = f[i-1] * i % mod;
}
// 预处理逆元数组（逆元阶乘）
i_f[n] = _pow(f[n], mod - 2); // 计算n!的逆元
for(int i = n; i > 0; i--){ // 逆序递推计算每个数的逆元阶乘
i_f[i-1] = i_f[i] * i % mod;
}
long long ans = 0;
for(int i = 0; i <= b; i++){ // 枚举苹果和香蕉之间的分割点i
// F(i + C + D, C) 计算橙子、香蕉和葡萄的排列方式
// F(A - 1 + B - i, A - 1) 计算苹果和剩余香蕉的排列方式
ans = (ans + F(i + c + d, c) * F(a - 1 + b - i, a - 1)) % mod;
}
cout << ans;
return 0;
}
暂无评论内容