头像

yxc的小迷妹

$$\href{https://www.acwing.com/blog/content/28192/}{\Huge\color{blue}{题解主页}}$$$${青涩の醉挽清风Team}$$




离线:13分钟前


最近来访(2213)
用户头像
ohhhdddentist
用户头像
Finn2009
用户头像
ice-bear
用户头像
洛白さん
用户头像
辣鸡号航母
用户头像
Dionysus.
用户头像
lmzOuO
用户头像
bcwing
用户头像
2717782356
用户头像
StarLi9ht
用户头像
回归.AC_Boy
用户头像
chessman666666
用户头像
hnsqls
用户头像
violet_garden
用户头像
JiuCherish
用户头像
sealt
用户头像
acwing_96177
用户头像
goodlucktoyou
用户头像
Holden_Caulfield
用户头像
yangxiufeng


class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        sort(input.begin(),input.end());
        input.erase(input.begin() + k,input.end());
        return input;
    }
};



<─求赞

对于 k=0 的情形,显然我们可以直接做树哈希。鉴于网上的相当多的树哈希写法都是有问题的,这里给出一个正确性较好的树哈希写法:动态地给每种子树分配一个编号(具体实现时可以开一个从哈希值到编号的map),然后对于每个点,将其所有子树的编号(而非哈希值)取出,排序后进行序列哈希。为减少碰撞,底数取得比 2n 大且使用双模数即可。

然后考虑 k>0 的结果:我们记chk(x,y,k)表示 T1 中以 x 为根的子树能否在删除不超过 k 个点的前提下与T2 T2 中以 y 为根的子树同构。注意这个 k 是必要的,不一定等于二者的子树大小之差,这有助于我们以后剪枝。对于原问题,只需求chk(T1.root,T2.root,|T1|-|T2|)即可。

我们考虑怎样求chk(x,y,k):首先是一些平凡的情形:如果 y 为空,则只需判断 x 的子树大小是否不超过 k ;如果 x 的子树与 y 的子树同构,显然结果为true。如果 x 子树大小比 y 小,或 x 子树大小比 y 大超过 k ,或 x 的儿子数量比 y少,显然为false。

然后递归地比较 x 与 y 的所有孩子:注意到这一过程实际上是 x 与 y 的孩子两两匹配的过程。假设有两个孩子是同构的,显然可以贪心地匹配;否则,每一个 x 的未匹配上的孩子都需要删除至少一个点才能跟 y 的某个孩子(也可能为空)匹配上,因此没匹配上的 x 孩子数量不能超过 k,下设这一数量为s;接下来,在 y 的没匹配上的孩子中补一些空孩子使其数量等于 s ,然后暴力枚举 x 和 y 的每个没匹配上的孩子,分别设为 u 和 v ,递归到chk(u,v,k-s+1)(注意这里的 k−s+1 便是考虑到了每个没匹配上的孩子都至少要删一个点这个性质)。最后做一个二分图匹配即可(由于 k 很小,也可以用暴力dfs或霍尔定理代替)。

这看起来是一个最坏${O(n^2)}$的大暴力,实际上我们可以看到, chk函数中这个限制 k 起到了很好的剪枝作用,可以证明:每个 T1 中的节点至多参与 ${2^k}$次chk过程(证明过程略)。再算上每个点处的二分图匹配过程,可得总的复杂度上界为${O(n2^{k}k^{3})}$,当然由于这个上界实际上远远跑不满,因此程序跑得飞快。

AC代码


#include<bits/stdc++.h>
#define gc getchar()
#define pc putchar
#define li long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<li,li>
using namespace std;
inline li read(){
    li x = 0;
    int y = 0,c = gc;
    while(c < '0' || c > '9') y = c,c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc;
    return y == '-' ? -x : x;
}
inline void prt(li x){
    if(x >= 10) prt(x / 10);
    pc(x % 10 + '0');
}
inline void print(li x){
    if(x < 0) pc('-'),x = -x;
    prt(x);
}
int t,k,cnt;
const int mo1 = 998244853,mo2 = 1004353809,ds = 19491001;
unordered_map<li,int> hsb;
int ft1,ft2,ft3;
pii st1[100010],st2[100010],st3[100010];
struct tree{
    int n,rt,fa[100010],fsts[100010],nxt[100010],sz[100010],ez[100010];
    int zl[100010];
    inline void dfs(int q){
        sz[q] = 1;
        for(int i = fsts[q];i;i = nxt[i]){
            dfs(i);
            sz[q] += sz[i];++ez[q];
        } 
        ft3 = 0;for(int i = fsts[q];i;i = nxt[i]) st3[++ft3] = mp(zl[i],i);
        sort(st3 + 1,st3 + ft3 + 1);
        fsts[q] = 0;
        for(int i = ft3;i;--i) nxt[st3[i].se] = fsts[q],fsts[q] = st3[i].se;
        li hs1 = 0,hs2 = 0;
        for(int i = 1;i <= ft3;++i){
            hs1 = (hs1 * ds + st3[i].fi) % mo1;
            hs2 = (hs2 * ds + st3[i].fi) % mo2;
        } 
        li hs = hs1 * mo2 + hs2;
        if(hsb.find(hs) == hsb.end()) hsb[hs] = ++cnt;
        zl[q] = hsb[hs];
    }
    inline void init(){
        memset(fa,0,n * 4 + 16);memset(fsts,0,n * 4 + 16);
        memset(nxt,0,n * 4 + 16);memset(sz,0,n * 4 + 16);
        memset(ez,0,n * 4 + 16);memset(zl,0,n * 4 + 16);
        n = read();
        rt = 0;
        for(int i = 1;i <= n;++i){
            if(i == 1) fa[i] = -1;
            else fa[i] = i >> 1;
            fa[i] = read();
            if(fa[i] == -1) rt = i;
            else nxt[i] = fsts[fa[i]],fsts[fa[i]] = i;
        }
        dfs(rt);
    }
}t1,t2;
bool vis1[100010],vis2[100010];
int wei[50];
inline bool ck(vector<int> biao){
    int m = biao.size();
    for(int i = 0;i < (1 << m);++i){
        int o = 0;
        for(int j = 0;j < m;++j) if(i & (1 << j)) o |= biao[j];
        if(wei[i] > wei[o]) return 0;
    }
    return 1;
}
inline bool chk(int p1,int p2,int k){
    if(!p1) return !p2;
    if(!p2) return t1.sz[p1] <= k; 
    if(t1.sz[p1] < t2.sz[p2] || t1.sz[p1] > t2.sz[p2] + k || t1.ez[p1] < t2.ez[p2]) return 0;
    if(t1.zl[p1] == t2.zl[p2]) return 1;
    if(!k) return 0;
    ft1 = ft2 = 0;
    for(int i = t1.fsts[p1];i;i = t1.nxt[i]) st1[++ft1] = mp(t1.zl[i],i),vis1[ft1] = 0;
    for(int i = t2.fsts[p2];i;i = t2.nxt[i]) st2[++ft2] = mp(t2.zl[i],i),vis2[ft2] = 0;
    int i = 1,j = 1,tot = 0;
    while(i <= ft1){
        while(j <= ft2 && st1[i].fi > st2[j].fi) ++j;
        if(j <= ft2 && st1[i].fi == st2[j].fi) ++tot,vis1[i++] = 1,vis2[j++] = 1;
        else ++i;
    }
    if(tot == ft1) return 1;
    int mm = ft1 - tot;
    if(mm > k) return 0;
    vector<int> q1,q2,q3;q1.clear();q2.clear();q3.clear();
    for(i = 1;i <= ft1;++i) if(!vis1[i]) q1.pb(st1[i].se);
    for(i = 1;i <= ft2;++i) if(!vis2[i]) q2.pb(st2[i].se);
    while(q2.size() < mm) q2.pb(0);
    q3.resize(mm);
    for(i = 0;i < mm;++i)
        for(j = 0;j < mm;++j) 
            if(chk(q1[i],q2[j],k - mm + 1)) q3[i] |= 1 << j;
    return ck(q3);
}
int main(){
    int i,j;
    for(i = 1;i < 32;++i) wei[i] = wei[i >> 1] + (i & 1);
    read();t = read();k = read();
    while(t--){
        hsb.clear();cnt = 0;
        t1.init();t2.init();
        puts(chk(t1.rt,t2.rt,k) ? "Yes" : "No");
    }
    return 0;
}






5D924308-CC4C-42AE-9DAB-448D07DBCDDD.jpeg

#include<bits/stdc++.h>
#define gc getchar()
#define pc putchar
#define li long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define md int mid = l + r >> 1
#define ls q << 1
#define rs q << 1 | 1
#define ln ls,l,mid
#define rn rs,mid + 1,r
using namespace std;
inline li read(){
    li x = 0;
    int y = 0,c = gc;
    while(c < '0' || c > '9') y = c,c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc;
    return y == '-' ? -x : x;
}
inline void prt(li x){
    if(x >= 10) prt(x / 10);
    pc(x % 10 + '0');
}
inline void print(li x){
    if(x < 0) pc('-'),x = -x;
    prt(x);
}
int T,n,m,cnt;
struct node{
    int l,r,q,v;
}a[1000010];
inline bool operator < (node q,node w){
    if(q.v != w.v) return q.v < w.v;
    if(q.q != w.q) return q.q < w.q;
    if(q.l != w.l) return q.l < w.l;
    return q.r < w.r;
}
pii t[4000010];
int c[4000010];
inline void init(int q,int l,int r){
    c[q] = 0;
    if(l == r){
        t[q] = mp(1,l);
        return;
    }
    md;
    init(ln);init(rn);
    t[q] = min(t[ls],t[rs]);
}
inline void ud(int q,int l,int r,int x){
    if(!x) return;
    t[q].fi = x;t[q].se = l;
    c[q] = x;
}
inline void ps(int q,int l,int r){
    md;
    ud(ln,c[q]);ud(rn,c[q]);
    c[q] = 0;
}
inline void xg(int q,int l,int r,int al,int ar,int x){
    if(al > ar) return;
    if(l >= al && r <= ar){
        ud(q,l,r,x);
        return;
    }
    ps(q,l,r);md;
    if(mid >= al) xg(ln,al,ar,x);
    if(mid < ar) xg(rn,al,ar,x);
    t[q] = min(t[ls],t[rs]);
}
inline pii cx(int q,int l,int r,int al,int ar){
    if(al > ar) return mp(-1,-1);
    if(l >= al && r <= ar) return t[q];
    ps(q,l,r);md;
    if(mid < al) return cx(rn,al,ar);
    if(mid >= ar) return cx(ln,al,ar);
    return min(cx(ln,al,ar),cx(rn,al,ar));
}
int as[1000010];
inline void dfs(int q,int l,int r){
    if(l == r){
        as[l] = t[q].fi;
        t[q] = mp(0,l);c[q] = 0;
        return;
    }
    ps(q,l,r);t[q] = mp(0,l);c[q] = 0;
    md;dfs(ln);dfs(rn);
}
inline pii operator + (pii q,pii w){
    return q.fi < w.fi ? q : w;
}
inline void ps2(int q){
    t[ls].fi += c[q];c[ls] += c[q];
    t[rs].fi += c[q];c[rs] += c[q];
    c[q] = 0;
}
inline void xg2(int q,int l,int r,int al,int ar,int x){
    if(al > ar) return;
    if(l >= al && r <= ar){
        t[q].fi += x;c[q] += x;
        return;
    }
    ps2(q);md;
    if(mid >= al) xg2(ln,al,ar,x);
    if(mid < ar) xg2(rn,al,ar,x);
    t[q] = t[ls] + t[rs];
}
inline pii cx2(int q,int l,int r,int al,int ar){
    if(al > ar) return mp(-1,-1);
    if(l >= al && r <= ar) return t[q];
    ps2(q);md;
    if(mid < al) return cx2(rn,al,ar);
    if(mid >= ar) return cx2(ln,al,ar);
    return cx2(ln,al,ar) + cx2(rn,al,ar);
}
int p[1000010];
inline void xg(int q){
    for(int i = q;i <= n;i += i & -i) ++p[i];
}
inline int cx(int q){
    int as = 0;
    for(int i = q;i;i -= i & -i) as += p[i];
    return as; 
}
inline li chk(){
    li ans = 0;
    memset(p,0,n * 4 + 8);
    for(int i = 1;i <= n;++i){
        ans += i - 1 - cx(as[i]);
        xg(as[i]);
    }
    return ans;
}
vector<node> b[1000010];
int mn[1000010];
int main(){
    int i,j;
    T = read();
    while(T--){
        n = read();m = read();
        for(i = 1;i <= m;++i){
            a[i].l = read();a[i].r = read();a[i].v = read();a[i].q = 0;
        }
        sort(a + 1,a + m + 1);
        int lst = -1;cnt = 0;
        for(i = 1;i <= m;++i){
            if(a[i].v != lst) ++cnt;
            lst = a[i].v;a[i].v = cnt;
        }
        init(1,1,n);
        for(i = 1;i <= m;++i) xg(1,1,n,a[i].l,a[i].r,a[i].v);
        bool fg = 0;
        for(i = 1;i <= m;++i){
            pii o = cx(1,1,n,a[i].l,a[i].r);
            if(o.fi != a[i].v){
                fg = 1;break;
            }
            a[i].q = o.se;
        }
        if(fg){
            puts("-1");
            continue;
        }
        dfs(1,1,n);
        for(i = 1;i <= n;++i) b[i].clear();
        for(i = 1;i <= m;++i) b[a[i].r].pb(a[i]);
        for(i = 1;i <= cnt;++i) mn[i] = 0;
        for(i = 1;i <= n;++i) xg2(1,1,n,1,as[i] - 1,1);
        for(i = n;i;--i){
            xg2(1,1,n,1,as[i] - 1,-1);
            for(j = 0;j < b[i].size();++j) mn[b[i][j].v] = max(mn[b[i][j].v],b[i][j].q);
            int o = as[i];
            if(i != mn[as[i]]) as[i] = cx2(1,1,n,as[i],n).se;
            if(as[i] == o) mn[as[i]] = 0; 
            xg2(1,1,n,as[i] + 1,n,1);
        }
        print(chk());pc('\n');
    }
    return 0;
}






<-求赞

分 A ≥ 0 , A < 0 , B ≥ 0 , B < 0, 几种情况讨论,于是需要维护
A ≥ 0 最大值,最小值
A < 0 最大值,最小值
B ≥ 0 最大值,最小值
B < 0 最大值,最小值
使用八棵线段树即可,没有什么思维深度。(当然也有六个ST表的,没有什么区别)

最后再根据5种不同情况制定相应策略即可,分别是:

${以A(即甲)为主导:\begin{cases}A有非负数,B无负数\\A有负数,B无非负数\end{cases}}$

${以B(即乙)为主导:\begin{cases}B有非负数,A无非负数\\B有负数,A无负数\end{cases}}$

A,B非负数,负数兼备。

AC代码


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5,BZ=-1e9-1;
int n,m,q;
struct qh{
    LL a[N],tr[N<<2];
    int bz;
    #define M (l+r>>1)
    #define ls (id<<1)
    #define rs (ls|1)
    void pushup(int bz,int id){
        if(tr[ls]==BZ&&tr[rs]==BZ) tr[id]=BZ;
        else if(tr[ls]!=BZ&&tr[rs]!=BZ) tr[id]=bz==1?max(tr[ls],tr[rs]):min(tr[ls],tr[rs]);
        else if(tr[ls]==BZ) tr[id]=tr[rs];
        else if(tr[rs]==BZ) tr[id]=tr[ls];
        return ;
    }
    void build(int id,int l,int r){
        if(l==r){tr[id]=a[l];return ;}
        build(ls,l,M);build(rs,M+1,r);
        pushup(bz,id);
    }
    LL queryn(int id,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tr[id];
        LL mn=1e10;
        if(x<=M){
            LL q=queryn(ls,l,M,x,y);
            if(q!=BZ) mn=min(mn,q);
        }
        if(M<y){
            LL q=queryn(rs,M+1,r,x,y);
            if(q!=BZ) mn=min(mn,q);
        }
        return mn;
    }
    LL queryx(int id,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tr[id];
        LL mx=BZ;
        if(x<=M){
            LL q=queryx(ls,l,M,x,y);
            if(q!=BZ) mx=max(mx,q);
        }
        if(M<y){
            LL q=queryx(rs,M+1,r,x,y);
            if(q!=BZ) mx=max(mx,q);
        }
        return mx;
    }
}axz,anz,bxz,bnz,axf,anf,bxf,bnf;
inline int Rd(){
    int s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}
int main(){
    // freopen("game4.in","r",stdin);
    // freopen("game.out","w",stdout);
    n=Rd();m=Rd();q=Rd();
    axz.bz=bxz.bz=1;axf.bz=bxf.bz=1;
    anz.bz=bnz.bz=2;anf.bz=bnf.bz=2;
    for(int i=1,x;i<=n;i++) x=Rd(),axz.a[i]=anz.a[i]=(x>=0?x:BZ), axf.a[i]=anf.a[i]=(x<0?x:BZ);
    for(int i=1,x;i<=m;i++) x=Rd(),bxz.a[i]=bnz.a[i]=(x>=0?x:BZ),bxf.a[i]=bnf.a[i]=(x<0?x:BZ);
    axz.build(1,1,n);anz.build(1,1,n);bxz.build(1,1,m);bnz.build(1,1,m);axf.build(1,1,n);anf.build(1,1,n);bxf.build(1,1,m);bnf.build(1,1,m);
    while (q--){
        int l1=Rd(),r1=Rd(),l2=Rd(),r2=Rd();
        LL Axz=axz.queryx(1,1,n,l1,r1),Axf=axf.queryx(1,1,n,l1,r1),Anz=anz.queryn(1,1,n,l1,r1),Anf=anf.queryn(1,1,n,l1,r1),Bxz=bxz.queryx(1,1,m,l2,r2),Bxf=bxf.queryx(1,1,m,l2,r2),Bnz=bnz.queryn(1,1,m,l2,r2),Bnf=bnf.queryn(1,1,m,l2,r2);
        LL A=0,B=0;
        // printf("%lld %lld %lld %lld %lld %lld %lld %lld\n",Axz,Axf,Anz,Anf,Bxz,Bxf,Bnz,Bnf);
        if(Axz!=BZ&&Bxf==BZ) A=Axz,B=Bnz;
        else if(Axf!=BZ&&Bxz==BZ) A=Anf,B=Bxf;
        else if(Bxf!=BZ&&Axf==BZ) A=Anz,B=Bnf;
        else if(Bxz!=BZ&&Axz==BZ) A=Axf,B=Bxz;
        else{
            if(Axf*Bxz>Anz*Bnf) A=Axf,B=Bxz;
            else A=Anz,B=Bnf;
        }
        printf("%lld\n",A*B);
    }
    return 0;
}







#include<bits/stdc++.h>
using namespace std;
long long n,x=5;
int main(){
    scanf("%lld",&n);
    while(n-x>0){
        n-=x;
        x+=x;
    }
    for(int i=1;i<=5;i++){
        if(n<=(x/5)*i){
            printf("%c",'a'+i-1);
            return 0;
        }
    }
    return 0;
}



<-求赞

79E82E9F-0899-44EB-9A03-9091368285E0.jpeg
8C1DBDE8-66A8-4D49-B1FC-B5F40B6E8D65.jpeg
记录s(原来的号码)中0~9的个数,然后从0开始贪心(贪最小字典序),每算出一种答案比较一次,以防出现非最优解的情况

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

string fin,s,tmp;
int n,k,i,j,t,ans1,ans,a[10];

void change(string &s,int x,int y) {
    int i;
    if (x>y)
        for(int i=0; i<n; i++)
            if(s[i]==x+'0') {
                t--;
                s[i]=y+'0';
                ans1+=abs(y-x);
                if(!t)
                    break;
            }
    if(x<y)
        for(int i=n-1; i>=0; i--)
            if(s[i]==x+'0') {
                t--;
                s[i]=y+'0';
                ans1+=abs(y-x);
                if(!t)
                    break;
            }
}

int main() {
    scanf("%d%d",&n,&k);
    cin>>s;
    for(int i=0; i<n; i++)
        a[s[i]-'0']++;
    ans=int(1e9);
    fin=s;
    for(int i=0; i<10; i++) {
        t=k-a[i],ans1=0;
        tmp=s;
        if (t>0)
            for(int j=1; j<=9; j++) {
                if(i+j<10)
                    change(tmp,i+j,i);
                if(!t)
                    break;
                if(i-j>=0)
                    change(tmp,i-j,i);
                if(!t)
                    break;
            }
        if(ans1<ans) {
            ans=ans1;
            fin=tmp;
        } else if(ans1==ans&&tmp<fin)
            fin=tmp;
        /*printf("%d\n",ans);
        cout<<fin<<endl;*/
    }
    printf("%d\n",ans);
    cout<<fin<<endl;
    return 0;
}




新鲜事 原文

有人玩saber吗?



由于我直接把4758题的代码拿过来就过了,所以这里只放一下代码和上一道题我的题解的链接

↘↓↓↓↓↓↙

详解

↗↑↑↑↑↑↖

AC代码


#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 10;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
const int MAXN = 100010;
//rnk从0开始
//sa从1开始,因为最后一个字符(最小的)排在第0位
//height从1开始,因为表示的是sa[i - 1]和sa[i]
//倍增算法 O(nlogn)
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
//Suffix函数的参数m代表字符串中字符的取值范围,是基数排序的一个参数,如果原序列都是字母可以直接取128,如果原序列本身都是整数的话,则m可以取比最大的整数大1的值
//待排序的字符串放在r数组中,从r[0]到r[n-1],长度为n
//为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小
//同上,为了函数操作的方便,约定除r[n-1]外所有的r[i]都大于0,r[n-1]=0
//函数结束后,结果放在sa数组中,从sa[0]到sa[n-1]
void Suffix(int *r, int *sa, int n, int m)
{
    int i, j, k, *x = wa, *y = wb, *t;
    //对长度为1的字符串排序
    //一般来说,在字符串的题目中,r的最大值不会很大,所以这里使用了基数排序
    //如果r的最大值很大,那么把这段代码改成快速排序
    for(i = 0; i < m; ++i) ws_[i] = 0;
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;//统计字符的个数
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];//统计不大于字符i的字符个数
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;//计算字符排名
    //基数排序
    //x数组保存的值相当于是rank值
    for(j = 1, k = 1; k < n; j *= 2, m = k)
    {
        //j是当前字符串的长度,数组y保存的是对第二关键字排序的结果
        //第二关键字排序
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;//第二关键字为0的排在前面
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;//长度为j的子串sa[i]应该是长度为2 * j的子串sa[i] - j的后缀(第二关键字),对所有的长度为2 * j的子串根据第二关键字来排序
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];//提取第一关键字
        //按第一关键字排序 (原理同对长度为1的字符串排序)
        for(i = 0; i < m; ++i) ws_[i] = 0;
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];//按第一关键字,计算出了长度为2 * j的子串排名情况
        //此时数组x是长度为j的子串的排名情况,数组y仍是根据第二关键字排序后的结果
        //计算长度为2 * j的子串的排名情况,保存到数组x
        t = x;
        x = y;
        y = t;
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
        //若长度为2 * j的子串sa[i]与sa[i - 1]完全相同,则他们有相同的排名
    }
}
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
void calheight(int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
}
char s[MAXN];
int main()
{
    int t,n,i;
    LL ans;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%s",s);
        n=strlen(s);
        for(i=0;i<n;i++)
            r[i]=s[i];
        r[i]=0;
        Suffix(r,sa,n+1,128);
        calheight(r,sa,n);
        for(i=1;i<=n;i++)
            ans+=n-sa[i]-height[i];
        printf("%lld\n",ans);
    }
    return 0;
}



<─求赞

Problem Description


Given a string, we need to find the total number of its distinct substrings.

Input


T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000

Output


For each test case output one number saying the number of distinct substrings.

Sample Input


2
CCCCC
ABABA

Sample Output


5
9

Hint


Explanation for the testcase with string ABABA: 
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA
Thus, total number of distinct substrings is 9.

Problem Idea


【题意】
给你一个字符串,我们需要找出该字符串中不相同子串的数目
【类型】
后缀数组[不相同的子串的个数]
【分析】
本题是一道裸的后缀数组题
“不相同的子串的个数”解法(摘自罗穗骞的国家集训队论文):
每个子串一定是某个后缀的前缀, 那么原问题等价于求所有后缀之间的不相同的前缀的个数。如果所有的后缀按照 suffix(sa[1]), suffix(sa[2]),
suffix(sa[3]), …… ,suffix(sa[n])的顺序计算, 不难发现, 对于每一次新加进来的后缀 suffix(sa[k]),它将产生 n-sa[k]+1 个新的前缀。但是其中有
height[k]个是和前面的字符串的前缀是相同的。所以suffix(sa[k])将“ 贡献”出n-sa[k]+1- height[k]个不同的子串。累加后便是原问题的答案。这个做法的时间复杂度为O(n)。
ps:字符串是从下标0开始存储的,故每一次新加进来的后缀 suffix(sa[k]),它将产生 n-sa[k]-height[k] 个新的前缀
另外,此题有个坑点,题目并没有说字符串仅包含大写字母,所以,在求解的过程中,我们可以当做ASCII码表中的所有字符都会出现,所以在求后缀数组sa[]时,最大值设置为128即可

Source Code


#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 10;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
const int MAXN = 100010;
//rnk从0开始
//sa从1开始,因为最后一个字符(最小的)排在第0位
//height从1开始,因为表示的是sa[i - 1]和sa[i]
//倍增算法 O(nlogn)
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
//Suffix函数的参数m代表字符串中字符的取值范围,是基数排序的一个参数,如果原序列都是字母可以直接取128,如果原序列本身都是整数的话,则m可以取比最大的整数大1的值
//待排序的字符串放在r数组中,从r[0]到r[n-1],长度为n
//为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小
//同上,为了函数操作的方便,约定除r[n-1]外所有的r[i]都大于0,r[n-1]=0
//函数结束后,结果放在sa数组中,从sa[0]到sa[n-1]
void Suffix(int *r, int *sa, int n, int m)
{
    int i, j, k, *x = wa, *y = wb, *t;
    //对长度为1的字符串排序
    //一般来说,在字符串的题目中,r的最大值不会很大,所以这里使用了基数排序
    //如果r的最大值很大,那么把这段代码改成快速排序
    for(i = 0; i < m; ++i) ws_[i] = 0;
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;//统计字符的个数
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];//统计不大于字符i的字符个数
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;//计算字符排名
    //基数排序
    //x数组保存的值相当于是rank值
    for(j = 1, k = 1; k < n; j *= 2, m = k)
    {
        //j是当前字符串的长度,数组y保存的是对第二关键字排序的结果
        //第二关键字排序
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;//第二关键字为0的排在前面
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;//长度为j的子串sa[i]应该是长度为2 * j的子串sa[i] - j的后缀(第二关键字),对所有的长度为2 * j的子串根据第二关键字来排序
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];//提取第一关键字
        //按第一关键字排序 (原理同对长度为1的字符串排序)
        for(i = 0; i < m; ++i) ws_[i] = 0;
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];//按第一关键字,计算出了长度为2 * j的子串排名情况
        //此时数组x是长度为j的子串的排名情况,数组y仍是根据第二关键字排序后的结果
        //计算长度为2 * j的子串的排名情况,保存到数组x
        t = x;
        x = y;
        y = t;
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
        //若长度为2 * j的子串sa[i]与sa[i - 1]完全相同,则他们有相同的排名
    }
}
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
void calheight(int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
}
char s[MAXN];
int main()
{
    int t,n,i;
    LL ans;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%s",s);
        n=strlen(s);
        for(i=0;i<n;i++)
            r[i]=s[i];
        r[i]=0;
        Suffix(r,sa,n+1,128);
        calheight(r,sa,n);
        for(i=1;i<=n;i++)
            ans+=n-sa[i]-height[i];
        printf("%lld\n",ans);
    }
    return 0;
}





#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int tr[50][26],fail[50],val[50],cnt,n,m;
ull sum;
char s[50];
struct Matrix{
    ull a[50][50];
    Matrix(){memset(a,0,sizeof(a));}
    Matrix operator*(const Matrix &b)const{
        Matrix res;
        for(int i=0;i<=cnt+1;i++)
            for(int j=0;j<=cnt+1;j++)
                for(int k=0;k<=cnt+1;k++)
                    res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j]);
        return res;
    }
}ans,base; 
void clear(){
    cnt=0;
    memset(tr,0,sizeof(tr));
    memset(fail,0,sizeof(fail));
    memset(val,0,sizeof(val));
}
void init1(){
    for(int i=0;i<=49;i++)
        for(int j=0;j<=49;j++)
            base.a[i][j]=ans.a[i][j]=0;
    for(int i=0;i<=cnt;i++){
        for(int j=0;j<26;j++){
            int x=tr[i][j],y=val[x];
            if(!y&&!val[i]) base.a[x][i]++;
        }
    }for(int i=0;i<=cnt+1;i++) base.a[cnt+1][i]=1;
    ans.a[0][0]=1;
}
void init2(){
    for(int i=0;i<=49;i++)
        for(int j=0;j<=49;j++)
            base.a[i][j]=ans.a[i][j]=0;
    ans.a[0][0]=ans.a[1][0]=1;
    base.a[0][0]=26,base.a[0][1]=base.a[1][1]=1;
}
void ksm(long long b){
    while(b){
        if(b&1) ans=base*ans;
        base=base*base;
        b>>=1;
    }
}
void DP(){
    sum=0;
    init1();ksm((long long)m);
    for(int i=0;i<=cnt+1;i++) sum+=ans.a[i][0];
    init2();ksm((long long)m);
    //cout<<sum<<endl;
    cout<<ans.a[0][0]-sum<<endl;
}
void build(){
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;i++){
        int c=s[i]-'a';
        if(!tr[u][c]) tr[u][c]=++cnt;
        u=tr[u][c];
    }val[u]=1;
} 
void getfail(){
    queue<int>q;
    for(int i=0;i<26;i++)
        if(tr[0][i]) q.push(tr[0][i]);
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(!tr[u][i]) tr[u][i]=tr[fail[u]][i];
            else{
                int x=tr[u][i],y=fail[u];
                while(y&&!tr[y][i]) y=fail[y];
                fail[x]=tr[y][i],val[x]|=val[fail[x]];
            }
        }
    } 
}
signed main(){
    while(~scanf("%d%d",&n,&m)){
        clear();
        for(int i=1;i<=n;i++)
            scanf("%s",s+1),build();
        getfail();DP(); 
    }return 0;
}