首页 > 其他分享 >CF1037H Security题解

CF1037H Security题解

时间:2023-02-02 14:33:36浏览次数:42  
标签:ch return fa int 题解 len CF1037H np Security

根据字典序的定义,位置大的大于长度长的,长度长的大于长度短的。

所以我们贪心,先追求长度长的,再追求后面的位置大的,再追求前面的位置大的。

我们要一个能遍历子串的结构,就选 SAM 得了。

还有个限制:为 S[L...R] 的字串。正好 SAM 有个东西叫做 endpos,用线段树合并求一下就求出来了。

注意当当前字符串长度为 \(len\) 时,endpos 要有 S[L+len...R] 才行。因为 endpos统计的是结尾。

再提一嘴,要一直保证 endpos 的条件成立,不行就退出。否则会超时。

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mp make_pair
#define forp(i, a, b) for(int i = (a);i <= (b);i ++)
using namespace std;
const int maxn = 2e7 + 5;
int n;
string T;int L, R;
namespace linetree
{
    int ch[8000005][2], rt[200005], tot;
    void make(int p, int i)
    {
        rt[p] = ++ tot;int u = rt[p], l = 1, r = n;
        while(1)
        {
            int mid = l + r >> 1;
            if(l == r) break;
            (mid >= i) ? (r = mid, u = ch[u][0] = ++ tot) : (l = mid + 1, u = ch[u][1] = ++ tot);
        }
        // cout << l << ' ' << r << ' ' << i << ' ' << u << endl;
    }
    int merge(int u, int v, int len) {
        if (!u || !v) return u += v;
        int p = ++ tot;
        if (len != 1) ch[p][0] = merge(ch[u][0], ch[v][0], len + 1 >> 1), ch[p][1] = merge(ch[u][1], ch[v][1], len >> 1);
        return p;
    }
    int query(int p, int l, int r, int fl, int fr)
    {
        if(fl <= l && fr >= r) return 1;
        int mid = l + r >> 1, ans = 0;
        if(fl <= mid && ch[p][0]) ans |= query(ch[p][0], l, mid, fl, fr);
        if(fr >= mid + 1 && ch[p][1]) ans |= query(ch[p][1], mid + 1, r, fl, fr);
        return ans;
    }
}
int c[100005], fin;
namespace SAM
{
    struct point{ int ch[26], fa, len; }a[200005];
    int las = 1, tot = 1;
    ll f[200005];
    void add(int s, int i)
    {
        int p = las, np = las = ++ tot;f[np] = 1;
        linetree::make(np, i);
        a[np].len = a[p].len + 1;
        for(;p && a[p].ch[s] == 0;p = a[p].fa) a[p].ch[s] = np;
        if(p == 0){ a[np].fa = 1; return ; }
        int q = a[p].ch[s];
        if(a[q].len == a[p].len + 1){ a[np].fa = q; return ; }
        int nq = ++ tot;a[nq] = a[q];
        a[q].fa = a[np].fa = nq;
        a[nq].len = a[p].len + 1;
        for(;p && a[p].ch[s] == q;p = a[p].fa) a[p].ch[s] = nq;
    }
    bool run(int i, int u, int pd)
    {
        if(u == 0) return 0;
        if(linetree::query(linetree::rt[u], 1, n, L + (i - 1) - 1, R) == 0) return 0;
        if(pd == 1) return 1;
        if(i == T.size() + 1)
        {
            forp(j, 0, 25){ c[i] = j; if(run(i + 1, a[u].ch[j], 1)){ fin = i; return 1; } }
            return 0;
        }
        c[i] = T[i - 1] - 'a'; if(run(i + 1, a[u].ch[T[i - 1] - 'a'], 0)) return 1;
        forp(j, T[i - 1] - 'a' + 1, 25){ c[i] = j; if(run(i + 1, a[u].ch[j], 1)){fin = i; return 1;} }
        return 0;
    }
    vector<int> e[200005];
    void init(){ forp(i, 2, tot) e[a[i].fa].push_back(i); }
    void build(int u)
    {
        for(auto v : e[u])
        {
            build(v);
            linetree::rt[u] = linetree::merge(linetree::rt[u], linetree::rt[v], n);
        }
    }
}
signed main()
{
    freopen("text.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;
    cin >> s;
    n = s.size();
    forp(i, 1, s.size()) SAM::add(s[i - 1] - 'a', i);
    SAM::init();SAM::build(1);
    int q;
    cin >> q;
    // cout << "#### " << linetree::query(linetree::rt[4], 1, n, 3, 3) << endl;
    while(q --)
    {
        cin >> L >> R >> T;
        if(SAM::run(1, 1, 0))
        {
            // if(c[3] == 'm' - 'a' && c[2] == 'y' - 'a' && c[1] == 'o' - 'a' && fin == 3) cout << "#### " << T << endl;
            forp(i, 1, fin) cout << char(c[i] + 'a');
            cout << endl;
        }
        else cout << -1 << endl;
    }
    return 0;
}

标签:ch,return,fa,int,题解,len,CF1037H,np,Security
From: https://www.cnblogs.com/closureshop/p/17085909.html

相关文章

  • 关于“等保保护”最常见问题解答!
    等保全称信息安全等级保护,它是网络安全体系中非常重要的组成部分。但很多人对等保不够了解,所以小编特整理了这篇文章,希望对你们有帮助。1、等级保护是强制性的吗?可......
  • 【题解】CF1770F Koxia and Sequence
    有没有觉得其他题解的模二Lucas逆用太智慧了,有没有觉得这题的第一思路是直接拆位算每一位是否有贡献,而不是先满足和的限制列式?这里提供另外一个做法。方向不同,结果一样......
  • Codeforces Round #848 (Div. 2) A~F 题解
    A.FlipFlopSum能换\(-1,-1\)就换,不能能换\(1,-1\)或\(-1,1\)也可以,否则只能换\(1,1\)。B.TheForbiddenPermutation如果原序列一开始就是好的那就结束,否则......
  • 关于github上README.md图片显示不出来的问题解决办法
    关于github上README.md图片显示不出来的问题解决办法出现原因:如果你的README文件内显示图片的路径是正确的,那么很有可能是因为DNS被污染了所以导致显示不正常,即无法访问存放......
  • 【PER #1】捉迷藏 / Ptz2022 Day1.Kyoto U L 题解
    今天心血来潮想改一改pj的题,发现了这场easyround的A还没改……跟自己和解了,想了两天没想明白,说说大致思路。题目链接只考虑一组询问怎么做,先把\(v\)当作根,称......
  • Spring Security Form表单认证代码实例
    SpringSecurityForm表单认证SpringSecurity中,常见的认证方式可以分为HTTP层面和表单层面,如下:HTTP基本认证Form表单认证HTTP摘要认证SpringSecurityForm表单实......
  • i.MX6ULL - 问题解决:NFS挂载失败 - VFS: Unable to mount root fs on unknown-block(2
    i.IMX6ULL-问题解决:NFS挂载失败-VFS:Unabletomountrootfsonunknown-block(2,0)开发环境:移植的linux5.4.7.0ubuntu1804x64arm-linux-gnueabihf-gccv7.5NFS方式......
  • Qt | QListWidgetItem返回错误的背景颜色(始终返回颜色值为0)问题解决
    Qt|QListWidgetItem返回错误的背景颜色(始终返回颜色值为0)问题解决使用场景:程序使用QListWidget显示一个列表,这个列表具有点击选择和再次点击取消选择的功能,点击之后需要更......
  • SOJ1728 题解
    题意有一个长度为\(n\)的数列\(a_0,a_1,\dots,a_{n-1}\)以及一个长度为\(m\)的操作序列\((b_0,c_0),(b_1,c_1)\dots(b_{m-1},c_{m-1})\)。执行\(t\)次操作,第\(......
  • ARC 155 题解
    A目前见过的最阴间的A。寻找规律,发现最后的回文串一定是由若干个周期拼起来的。当周期长度为偶数时,\(S\)和\(S'\)可以各拿半个周期。于是kmp求出border,再判一下,但......