挑战赛#17 官方题解

你好

2025-04-25 18:01:31

发布于：浙江

22阅读

0回复

0点赞

挑战赛#17 题解

T1 凤梨酥

本题考察分支结构，输入馅料含量和凤梨含量之后，按照给出的标准进行分支判断即可

#include <iostream>
#define N 100005
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  if(a >= 50 && b >= 30)  cout << 1;
  else if(a >= 50 && b >= 15 && b < 30) cout << 2;
  else cout << 3;
  cout << endl;
}

T2 买凤梨1

本题需要对于每一个给定的凤梨，检查重量是否在范围内，并且检查是否是回文数。检查回文数可以考虑将原数字按位拆形成一个前后颠倒的数字，并且与原数字进行比较。也可以直接将数字转换成字符串，使用reverse函数进行翻转。

#include<bits/stdc++.h>
using namespace std;

bool check(int x) {
    string s = to_string(x);
    string ss = s;
    reverse(s.begin(), s.end());
    return s == ss;

}

int main(){
   int n, k;
   cin >> n;
   
   int cnt = 0;
   for(int i = 1; i <= n; i++) {
        int x;
        cin >>x ;
        if(x < 500 || x > 10000) continue;
        if(check(x)) cnt++;
   }
   cout << cnt << endl;
}

T3 集训营

本题要求计算能够最长连续上课的时间是多久。

对于某一天来说，只有所有学生都在，才能上课。因此可以预处理一下每一天是否需要上课，样例代码中使用st数组来记录每一天是否可以上课，最后遍历一遍递推求最长的连续上课时间即可，时间复杂度为线性 $O(nm)$ 。

#include<bits/stdc++.h>
using namespace std;
int st[1010];
int n, m;
int main()
{
    for(int i = 1; i <= 1000; i++) st[i] = 1;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            if(x == 0) st[j] = 0; //不行
        }

    int len = 0;
    for(int i = 1; i <= m; i++) {
        if(st[i]) st[i] = st[i -1] + 1;
        len = max(len, st[i]);
    }
    cout << len << endl;

    return 0;
}

T4 摸鱼

本题中由于给定的常客光顾时间没有任何重叠，因为可以直接将访客来访时间段以pair或者结构体的形式存进数组，并且按照时间顺序排序。此时相邻两个常客造访时间中间的空闲阶段就可以摸鱼。摸鱼的次数为空闲时间长度 / 单次摸鱼时长，累加得到答案。

（第一个常客造访前的时间以及最后一个常客造访后的时间也都可以摸鱼，因此可以直接把时间点 $0$ 和 $L + 1$ 存进数组一起运算)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, L, a;
    cin >> n >> L >> a;
    int ans = 0;
    vector<pair<int, int>> c;
    c.push_back({0, 0});

    c.push_back({L + 1, L + 1});
    for(int i = 1; i <= n; i++) {
        int L, R;
        cin >> L >> R;
        c.push_back({L, R});

    }
    sort(c.begin(), c.end());
    for(int i = 1; i < c.size(); i++) {
        ans += (c[i].first - c[i - 1].second - 1) / a;
    }
    cout << ans << endl;


}

买凤梨2

对于本题的第一个操作，一本美食书推荐的甜度区间 ${L, R}$ , 那么需要让 ${L, R}$ 区间内每个甜度的被推荐数加 $1$ ，也就可以转换成一个区间加法的问题，可以使用差分操作进行 $O(1)$ 复杂度的区间加法，最后进行一遍前缀和操作，得到修改后的数组。

然后，对于所有被推荐数大于等于 $k$ 的甜度，都标记为 $1$ ，否则标记为 $0$ ，那么查询一个区间内有多少合适的温度，也就是查询区间内一共有多少个 $1$ , 也就是查询区间和。因此可以使用前缀和来进行快速查询。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10;
int c[N];
int n,k,q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        c[l]++;c[r+1]--;
    }
    for(int i=2;i<=200000;i++){
        c[i]+=c[i-1];
    }
    for(int i=1;i<=200000;i++){
        if(c[i]>=k){
            c[i]=1;
        }
        else{
            c[i]=0;
        }
    }
    for(int i=2;i<=200000;i++){
        c[i]+=c[i-1];
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<c[r]-c[l-1]<<'\n';
    }
}

T6 美丽子序列

数据结构，单调栈，二分

本题旨在解决两个紧密相关的核心问题：

合法区间的定位：针对数组中的每一个索引 i，需要找出距离 i 最近的索引 j，使得 arr[i] - arr[j] ≥ k。满足这一条件的 (i, j) 所构成的区间，即为合法区间。
合法区间的扩展：在确定了上述合法区间后，需要将这些局部的合法区间拓展至整个数组范围，构建满足条件的全局区间体系。

为解决第一个问题，可借助能高效维护区间信息的数据结构，如线段树、ST表等。具体实现时，通过枚举左端点，同时对右端点进行二分查找，以此确定区间内的最小值是否满足 arr[i] - arr[j] ≥ k 的条件。需特别注意，常规的二分线段树操作，时间复杂度会达到 $O(n\log^2 n)$ ，在大规模数据下极易超时。因此，建议采用线段树二分法，将时间复杂度优化至可接受范围。

对于第二个问题，同样可以采用类似的策略。通过枚举左端点，依据既定规则判断以该端点为起始的区间中，有多少包含此前确定的合法区间，从而实现合法区间从局部到整体的拓展。

时间复杂度 $O(n\log n)$

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;

#include <vector>
#include <cmath>
using namespace std;

class ST {
private:
    vector<vector<int> > st_mins;
    vector<int> log2;
public:
    ST(const vector<int> &nums) {
        int n = nums.size();
        log2.resize(n + 1);
        log2[1] = 0;
        for (int i = 2; i <= n; i++) {
            log2[i] = log2[i / 2] + 1;
        }
        int k = log2[n] + 1;
        st_mins.resize(n, vector<int>(k));
        for (int i = 0; i < n; i++) {
             st_mins[i][0] = nums[i];
        }

        for (int j = 1; j < k; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st_mins[i][j] = min(st_mins[i][j - 1], st_mins[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query_mins(int l, int r) {
        int j = log2[r - l + 1];
        return min(st_mins[l][j], st_mins[r - (1 << j) + 1][j]);
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    ST st(arr);
    vector<int> a_r(n + 1, n + 1);
    for (int i = 1; i < n; i++) {
        int want = arr[i] - k;
        int l = i + 1, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (st.query_mins(i, mid) <= want) r = mid;
            else l = mid + 1;
        };
        if (st.query_mins(i, r) <= want) {
            a_r[i] = r;
        }
//        cerr << a_r[i] << " ";
    }
//    cerr << endl;
    ST st1(a_r);
    long long sums = 0;
    for (int i = 1; i <= n; i++) {
        int l = i + 1, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (st1.query_mins(i, mid) <= mid) r = mid;
            else l = mid + 1;
        }
        // cerr << st1.query_mins(i, r) << " " << i << " " << r << endl;
        if (st1.query_mins(i, r) <= r) {
//            cerr << i << " " << r  <<" " << n - r + 1.md<< endl;
            sums += n - r + 1;
        }
    }
    cout << sums << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}