【补档】红中带蓝的挑战赛17
2025-04-21 23:13:05
发布于：广东
47阅读
0回复
0点赞
要我说，这会挑战赛真的是
大体说一下：这次挑战赛难度不高，没使用到什么高阶算法，下面的表是答题知识点
题目 知识点
1 分支结构
2 回文数串
3 预处理+模拟
4 结构体排序
5 前缀和
6 双指针
接下来我来详细解释一下题目
第一题
题意分析：很明显，这是一道简单的分支结构
思路：将一级二级三级凤梨酥依次判断，不要忘了要用else
代码
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
if(n>=50&&m>=30)cout<<1;//一级凤梨酥
else if(n>=50&&m>=15)cout<<2;//二级凤梨酥
else if(n<50||m<15)cout<<3;//三级凤梨酥
return 0;
}
第二题
题意分析：找到重量（i）是回文数的凤梨，注意：范围要在500g−10000g之间我写代码时就有这个错误
思路：在数组中找到重量适合的凤梨，在判断凤梨的重量是否为回文数，是则cnt++；
代码：
#include<bits/stdc++.h>
using namespace std;
bool hw(int n){//判断回文数
int n1=n,n2=0;
while(n>0) {
n2=n2*10+n%10;
n/=10;
}
return n1==n2;
}
int main(){
int n;
cin>>n;
int cnt=0;
for(int i=1;i<=n;i++){
int pa;
cin>>pa;
if(pa>=500&&pa<=10000){//重量合适
if(hw(pa)){//判断回文数
cnt++;//统计凤梨
}
}
}
cout<<cnt;
return 0;
}
第三题
题意分析：当这一列所有元素都为1时，可以上课，最多连续上几天
思路：先做好预处理，把能上的都标记出来，然后求最长子串的长度（标记可以用bool vis[1000010]）
代码：
#include <iostream>
using namespace std;
int a[501][501];
int d[501];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[j][i];
for (int i = 1; i <= m; i++) {//预处理
d[i] = 1;
for (int j = 1; j <= n; j++) {//标记上课天数
if (a[i][j] == 0){
d[i] = 0;
break;
}
}
}
int ans = 0, cnt = 0;
for (int i = 1; i <= m; i++) {//最长子串的长度
if (d[i]) {
cnt++;
if (cnt > ans) ans = cnt;
} else {
cnt = 0;
}
}
cout << ans;
return 0;
}
第四题
题意分析：主人公只可以在没有客人的时候摸鱼
思路：使用结构体，设come和leave，那n+1.c-n.l(-1)/a，因为时间点和时间段的差异，注意：这种方法需要总工+1，因为T是时间点
代码：
#include<bits/stdc++.h>
using namespace std;
struct node{//come、leave结构体定义
int l,r;
}a[101];
bool cmp(node x,node y){
return x.l<y.l;
}
int main()
{
int n,T,t;
cin>>n>>T>>t;
for(int i=1;i<=n;i++)
{
cin>>a[i].l>>a[i].r;
}
sort(a+1,a+n+1,cmp);//结构体排序
int ans=0;
for(int i=1;i<n;i++)
{
ans=ans+(a[i+1].l-a[i].r-1)/t;//摸鱼时间
}
ans=ans+(T-a[n].r)/t+((a[1].l-1)/t);//因为没算最后元素和下班的时间，所以要加上
cout<<ans;
return 0;
}
第五题
题意分析：在【l，r】区间找到合适的k
思路：把输入的数组差分一下，然后计算每个甜度的推荐次数，标记合适的甜度，数组存好，查找就行了（由于数组较多，我会注释他们是干什么的）
#include <iostream>
using namespace std;
const int MAX = 200010;
int d[MAX]; // 差分数组
int pre[MAX]; // 前缀和数组#include<bits/stdc++.h>
int cnt[MAX]; // 满足条件的计数
int sum[MAX]; // 前缀和
int main() {
int n, k, q;
cin >> n >> k >> q;
// 输入区间并处理差分数组
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
d[l]++;
if (r + 1 < MAX) d[r + 1]--;
}
// 计算每个甜度的推荐次数
for (int i = 1; i < MAX; i++) {
pre[i] = pre[i - 1] + d[i];
}
// 标记满足条件的甜度
for (int i = 1; i < MAX; i++) {
cnt[i] = (pre[i] >= k) ? 1 : 0;
}
// 计算前缀和
for (int i = 1; i < MAX; i++) {
sum[i] = sum[i - 1] + cnt[i];
}
// 处理查询
while (q--) {
int l, r;
cin >> l >> r;
cout << sum[r] - sum[l - 1] << "\n";
}
return 0;
}
第六题
题意分析：数组中存在一对整数 [i,j]满足Ai-Aj>=k,就是美丽的，求美丽的连续子序列的个数
思路：既然是有i，j两个元素，还在移动，说明使用了双指针，那么我们就可以定义双向队列，使用双指针思想，循环遍历就行
//题解是帮助，不是答案，接下来这道题请有读者自己解答
//请在代码中的注释部分添加代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
ll total = /*指针总数*/;
ll not_beautiful = 0;
deque<int> dq;
for (int r = 0, l = 0; r < n; ++r) {
while (/*dp非空&&dp尾<=Ar*/) {
dq.pop_back();
}
dq.push_back(r);
while (!dq.empty() && a[dq.front()] - a[r] >= k) {
l = dq.front() + 1;
dq.pop_front();
}
//not_beautiful加中指针
}
cout << /*你觉得该填什么呢*/ << "\n";
return 0;
}
有帮助，赞一个