SYNU 十一月周赛 Round I 题解

PS:这是Orange的个人题解，非出题人题解。

A. 完美字符串

这就是回文串的定义，判断是否是回文串即可。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// #define int long long
#define endl '\n'
#define all(_x) _x.begin(), _x.end()
#define matrix(_x, _y, _z) vector<vector<int>>(_x, vector<int>(_y, _z))
#define debug(_x) cout << #_x << '=' << _x << endl
using i64 = long long;
using i128 = __int128;
using pii = pair<int, int>;
using mat = vector<vector<int>>;
using u64 = unsigned long long;
constexpr int N = 2e5 + 10;
// dont use umap!!!

signed main()
{
    IOS;
    int n;
    cin >> n;
    string s;
    cin >> s;
    auto ss = s;
    reverse(all(ss));
    if(s == ss) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

B. 图书馆查询

共两种操作，操作一查询某个位置是否有人，操作二释放这个人，可以用一个map或者数组来记录位置，有人为1否则为0，根据是否有人来处理操作1和2即可。

signed main()
{
    IOS;
    int n;
    cin >> n;
    map<int, int> vis;
    while(n --)
    {
        int c, op;
        cin >> c >> op;
        if(op == 1)
        {
            if(vis[c]) cout << "NO\n";
            else 
            {
                vis[c] = 1;
                cout << "YES\n";
            }
        }
        else
        {
            vis[c] = 0;
        }
    }
    return 0;
}

C. 挡沙壁easy

注意到n很小，可以按题意模拟，一共模拟n轮，每次标记哪些在第几轮被删掉就行。

signed main()
{
    IOS;
    int n;
    cin >> n;
    vector<int> a(n + 1), vis(n + 1);
    vector<vector<int>> ans(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        int now = -1;
        for(int j = 1; j <= n; j ++)
        {
            if(vis[j]) continue; // 之前已经被删过了，跳过
            if(a[j] > now)
            {
                now = a[j];
                vis[j] = i;
                ans[i].push_back(a[j]);
            }
        }
    }
    cout << *max_element(vis.begin() + 1, vis.begin() + n + 1) << '\n';
    for(auto x : ans)
    {
        if(x.size())
        {
            for(auto y : x)
            {
                cout << y << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

D. 挡沙壁hard

n很大，模拟显然不行，考虑优化。

不妨注意到样例：

他们每个位置被删掉的轮数：

很显然，对于 $x$，当 $x$ 前面有高于 $x$ 的沙丘时， $x$ 在本轮就不会被删掉，因此考虑 $x$ 前面所有高于 $x$ 的沙丘中最后一个被删除的，当它被删除后， $x$ 才会被删除。以上，可以考虑进行递推：

记 $f[x]$ 表示 $x$ 被删除的轮数，则能得到如下转移：

而前面的这个结构显然需要特殊的数据结构来维护，考虑对 $x$ 的排名为下标，对 $f[i]$ 建立线段树，每次查询 $\max_{a_i > x} f[i]$ 其实就是在线段树上查询区间 $[rank[x], n]$，查询之后更新 $f[x]$ 的值，再更新线段树的对应位置 $rank[x]$ 即可。

求 $rank[x]$ 可以用离散化之类的方法做到。

struct Discre
{
    vector<int> all;
    void insert(int _) { all.push_back(_); }
    void insert(vector<int> p) { all.insert(all.end(), p.begin(), p.end()); }
    void insert(int *p, int len) { all.insert(all.end(), p, p + len); }
    Discre(vector<int> p) { all = vector<int>(p); }
    Discre(int *p, int len) { all = vector<int>(p, p + len); }
    Discre() {}
    void init() { sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); }
    int index(int p) { return lower_bound(all.begin(), all.end(), p) - all.begin(); }
    int size() { return all.size(); }
    int operator[](int idx) { return all[idx]; }
};

struct Info
{
    int x;
    Info(i64 n = 0)
    {
        x = n;
    }
    friend Info operator+(Info a, Info b)
    {
        Info c;
        c.x = max(a.x, b.x);
        return c;
    }
};

struct segmentTree
{
    #define Lson(u) (u << 1)
    #define Rson(u) (u << 1 | 1)
    int N; // N = n + 1
    vector<int> L, R;
    vector<Info> ar;
    vector<Info> node;
    segmentTree(int n) : N(n + 1), L(4 * N), R(4 * N), node(4 * N) // range 1~n
    {
        ar = vector<Info>(N);
        build(1, 1, n);
        ar.clear();
    }   
    segmentTree(vector<Info> &a) : ar(a), N(a.size()), L(4 * N), R(4 * N), node(4 * N) // a.size = n + 1, range 1~n
    {
        build(1, 1, a.size() - 1);
        ar.clear();
    } 
    void build(int u,int l,int r)
    {
        L[u] = l, R[u] = r;
        if(l == r)
        {
            node[u] = ar[r];
            return;
        }
        int mid = l + r >> 1;
        build(Lson(u), l, mid);
        build(Rson(u), mid + 1, r);
        node[u] = node[Lson(u)] + node[Rson(u)];
    }
    Info query(int u, int l, int r)
    {
        assert(l <= r);
        assert(l >= 1);
        assert(r < N);
        if(l <= L[u] and R[u] <= r)
            return node[u];
        int mid = L[u] + R[u] >> 1;
        if(r <= mid) return query(Lson(u), l, r);
        else if(l > mid) return query(Rson(u), l, r);
        else return query(Lson(u), l, r) + query(Rson(u), l, r);
    }
    Info query(int l, int r) {return query(1, l, r);}
    void modify(int u,int pos, Info v)
    {
        assert(pos >= 1);
        assert(pos < N);
        if(L[u] == R[u] and L[u] == pos) 
        {
            node[u] = v;
            return;
        }
        int mid = L[u] + R[u] >> 1;
        if(pos <= mid) modify(Lson(u), pos, v);
        else modify(Rson(u), pos, v);
        node[u] = node[Lson(u)] + node[Rson(u)];
    }
    void modify(int pos, Info v) { modify(1, pos, v); }
    template<class F>
    int findfirst(int u,int l,int r,F &&check)
    {
        if(l > R[u] or r < L[u]) return -1;
        if(!check(node[u])) return -1;
        if(L[u] == R[u]) return L[u];
        int mid = L[u] + R[u] >> 1;
        int res = findfirst(Lson(u), l, r, check);
        if(~res) return res;
        return findfirst(Rson(u), l, r, check);
    }
    template<class F>
    int findfirst(int l,int r,F &&check) {return findfirst(1, l, r, check);}
    template<class F>
    int findlast(int u,int l,int r,F &&check)
    {
        if(l > R[u] or r < L[u]) return -1;
        if(!check(node[u])) return -1;
        if(L[u] == R[u]) return L[u];
        int mid = L[u] + R[u] >> 1;
        int res = findfirst(Rson(u), l, r, check);
        if(~res) return res;
        return findfirst(Lson(u), l, r, check);
    }
    template<class F>
    int findlast(int l,int r,F &&check) {return findlast(1, l, r, check);}
    #undef Lson(u)
    #undef Rson(u)
};

signed main()
{
    IOS;
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> ans(n + 1);
    Discre dis;
    for(int i = 1; i <= n; i ++) cin >> a[i], dis.insert(a[i]);
    dis.init(); // 离散化
    segmentTree sgtr(n);
    int ans1 = 0;
    for(int i = 1; i <= n; i ++)
    {
        auto x = dis.index(a[i]) + 1; // 求 a_i 的排名
        auto qry = sgtr.query(x, n).x; // 查询区间
        int res = qry ? qry + 1 : 1; // 如果qry为0，则说明前面没有比x高的沙丘，f[i]=1，否则f[i]=qry+1
        ans1 = max(ans1, res); // 记录最大轮数
        ans[res].push_back(a[i]);
        sgtr.modify(x, res); // 更新线段树的对应位置
    }
    cout << ans1 << '\n';
    for(auto x : ans)
    {
        if(x.size())
        {
            for(auto y : x)
            {
                cout << y << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}