周赛题解

完美字符串

思路：

回文串不解释

参考代码：

• C++

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    string s; 
    cin>>n;
    cin>>s;
    bool is= true;
    for (int i=0;i<n/2;i++) {
        if (s[i]!=s[n-1-i]) {
            is=false;
            break;
        }
    }
    if (is) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

图书馆查询

思路：

问题理解：

需要设计一个图书馆座位预约系统

两种操作：预约座位（op=1）和释放座位（op=2）

座位号范围：0-50000

操作总数最多50万次

核心逻辑：

预约座位：检查座位是否已被占用

如果空闲 → 标记为占用，返回"YES"

如果已被占用 → 返回"NO"

释放座位：直接将座位标记为空闲状态 暴力模拟利用循环模拟上一次加以判断

参考代码：

• C++

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<bool> o(50001, false);
    for (int i=0;i<n;i++) {
        int c,op;
        cin>>c>>op;       
        if (op==1){ 
            if (o[c]) {
                cout<<"NO"<<endl;
            } else {
                o[c]=true;
                cout << "YES" << endl;
            }
        } else if(op==2) {
            o[c]=false;
        }
    }
    return 0;
}

挡沙壁easy

思路：

代码逻辑是： 每一轮找出所有比前面最大值大的沙壁（即单调递增序列） 把这些沙壁作为本轮失效的 剩下的沙壁进入下一轮 重复直到没有沙壁

参考代码：

• C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<vector<int>> r;
    vector<int> c=a;
    while(!c.empty()){
        vector<int> m;
        vector<int> t;
        int x=0;
        for(int i=0;i<c.size();i++){
            int h=c[i];
            if(h>x){
                m.push_back(h);
                x=h;
            }else{
                t.push_back(h);
            }
        }
        r.push_back(m);
        c=t;
    }
    cout<<r.size()<<endl;
    for(int i=0;i<r.size();i++){
        for(int j=0;j<r[i].size();j++){
            if(j>0)cout<<" ";
            cout<<r[i][j];
        }
        cout<<endl;
    }
    return 0;
}

挡沙壁hard

思路：

使用数组 t 来维护每个轮次的最小末尾值 对于每个沙壁高度 a[i]，在 t 中二分查找第一个小于 a[i] 的位置 如果找不到（p==-1），说明需要新开一轮，r[i]记录该沙壁所在的轮次 如果找到，替换 t[p] 的值，r[i] 记录轮次 p 最后根据 r[i] 将沙壁分组输出 本题核心思路 这个问题本质上是一个序列分层问题，可以用贪心 + 二分的方法高效解决。 问题转化 把沙壁工作过程转化为： 需要将原序列划分成若干递增子序列 每个子序列中的元素必须严格大于前面所有元素（在该子序列中） 要求最小划分数 关键观察 每轮工作就是在找一个递增子序列 轮数 = 最长递减子序列的长度 可以用贪心策略：每来一个新的沙壁，放在第一个末尾值小于它的轮次中

参考代码：

• C++

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0;i<n;i++) {
        cin>>a[i];
    }
    vector<int> t;
    vector<int> r(n);
    for (int i=0;i<n;i++) {
        int l=0,h=t.size()-1,p=-1;
        while (l<=h){
            int m=(l+h)/2;
            if (t[m]<a[i]) {
                p=m;
                h=m-1;
            } else{
                l=m+1;
            }
        }
        if (p==-1) {
            r[i]=t.size();
            t.push_back(a[i]);
        } else{
            r[i]=p;
            t[p]=a[i];
        }
    }

    int k=t.size();
    vector<vector<int>>s(k);
    for (int i=0;i<n;i++) {
        s[r[i]].push_back(a[i]);
    }
    cout<<k<<endl;
    for (int i=0;i<k;i++) {
        for (int j=0;j<s[i].size();j++) {
            if (j > 0) 
            cout<<" ";
            cout<<s[i][j];
        }
        cout<<endl;
    }
    return 0;
}