牛客练习赛88题解

A题：活着的证据
显然是贪心，对于位数不够的情况肯定是要吧所有v和i都用上，如果位数够了，多的v显然没用，多的i从高位向低位补齐即可，注意一些细节iii=3 viii=8

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
    char c;
    ll w=1;
    while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
    ll ans=c-'0';
    while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    return ans*w;
}
int T;
const int xx=5e6+5;
int a[xx];
int main(){
    T=read();
    while(T--)
    {
        int V=read(),I=read(),n=read();
        if(V+I<=n)
        {
            while(V--)putchar('5');
            while(I--)putchar('1');
            puts("");
            continue;
        }
        memset(a,0,sizeof(a[0])*(n+1));
        for(int i=1;i<=min(V,n);i++)a[i]=5;
        for(int i=n;i>=1;i--)if(!a[i])a[i]=1,I--;
        //注意单i只能加到3 
        for(int i=1;i<=n;i++)
        {
            if(a[i]==5&&I>=3){I-=3;a[i]+=3;}
            else if(I>=2)I-=2,a[i]+=2;
            else if(I>=1)I-=1,a[i]++;
        }
        for(int i=1;i<=n;i++)cout<<a[i];
        puts("");
    }
    return 0;
}

B题：寻寻觅觅寻不到
明显模拟，记录从最长多少个后缀是合法的，最长多少前缀是合法的，最后再把截取的字符串放到最末尾看是否匹配即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
    char c;
    ll w=1;
    while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
    ll ans=c-'0';
    while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    return ans*w;
}
int n;
const int xx=3e5+5;
char s[xx],c[xx];
int pre[xx],suf[xx];
int main(){
//    freopen("str.in","r",stdin);
//    freopen("str.out","w",stdout);
    int T=read();
    while(T--)
    {
        scanf("%s",s+1);
        scanf("%s",c+1);
        int n=strlen(s+1),m=strlen(c+1),k=read();
        assert(k<=n);
        if(n!=m){puts("NO");continue;}
        memset(pre,0,sizeof(pre[0])*(n+3));
        memset(suf,0,sizeof(suf[0])*(n+3));
        for(int i=1;i<=n;i++)
        {
            if(s[i]==c[i])pre[i]=1;
            else break;
        }
        pre[0]=1;suf[n+1]=1;
        for(int i=n;i>=k+1;i--)
        {
            if(s[i]==c[i-k])suf[i]=1;
            else break;
        }
        int vis=0;
        for(int i=1;i<=n-k+1;i++)
        {
            int vs=1;
            for(int j=1;j<=k;j++)if(s[i+j-1]!=c[n-k+j]){vs=0;break;}
            if(!vs)continue;
            if(pre[i-1]&&suf[i+k]){vis=1;break;}
        }
        if(!vis)puts("NO");
        else puts("YES");
    }
    return 0;
}

C题：踩不出足迹
考虑异或的性质，首先异或和同或都是具有交换律的，所以我们可以任意调换顺序。
首先同或运算符就等价于和另外一个数取反异或起来。。
所以我们如果需要将若干个数取反后异或起来，可以把它们排在一起然后同时消掉这两个取反符号。
最终可能会有一个取反后的数没有被消掉，我们就分类讨论一下。就是比较一下 和 的大小。

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll read()
{
    char c;
    ll w=1;
    while((c=getchar())>'9'||c<'0');
    ll ans=c-'0';
    while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    return ans*w;
}
ll x,y;
signed main(){
    int n,k;
    n=read();
    k=read();
    while(n--)
    {
        y=read();
        x^=y;
    }
    if(n==1)cout<<y<<"\n";
    else 
    if(k==64)cout<<max(x,x^((0ull)-1ull))<<'\n';
    else cout<<max(x,x^((1ull<<k)-1))<<'\n';
    return 0;
}

D题：都市的柏油路太硬
仔细观察题面，对于第二次建边之后答案一定就是原最小生成树上的最大边，将原树建成最小生成树多次询问两点之间的最大路径，考虑如何优化多测，可以使用kruskal重构树+O(1) lca 得到每次询问O(1)的复杂度（对于部分常数优秀的应该不优化也可以带log跑过）

#include <bits/stdc++.h>
using namespace std;
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    //fread->read
    bool IOerror=0;
    //inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;} 
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend){
            p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    template<class T> inline bool read(T &x){
        bool sign=0;char ch=nc();x=0;
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    inline bool read(double &x){
        bool sign=0;char ch=nc();x=0;
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if(ch=='.'){
            double tmp=1; ch=nc();
            for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if(sign)x=-x;
        return true;
    }
    inline bool read(char *s){
        char ch=nc();
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
        return true;
    }
    inline bool read_line(char *s){
        char ch=nc();
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        for(;ch!='\n'&&!IOerror;ch=nc())*s++=ch;
        *s=0;
        return true;
    }
    inline bool read(char &c){
        for(c=nc();blank(c);c=nc());
        if(IOerror){c=-1;return false;}
        return true; 
    }
    template<class T,class... U>bool read(T& h,U&... t){return read(h)&&read(t...);}
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;
/************* debug begin *************/
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
    int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
    return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);}
#ifdef tokitsukaze 
#define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__);
#else
#define debug(...) 233;
#endif
/*************  debug end  *************/
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int,ll> PIL;
typedef pair<ll,int> PLI;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<PII > VPII;
/************* define end  *************/
void read(int *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(ll *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(double *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void println(VI x){for(int i=0;i<sz(x);i++) printf("%d%c",x[i]," \n"[i==sz(x)-1]);}
void println(VL x){for(int i=0;i<sz(x);i++) printf("%lld%c",x[i]," \n"[i==sz(x)-1]);}
void println(int *x,int l,int r){for(int i=l;i<=r;i++) printf("%d%c",x[i]," \n"[i==r]);}
void println(ll *x,int l,int r){for(int i=l;i<=r;i++) printf("%lld%c",x[i]," \n"[i==r]);}
/*************** IO end  ***************/
void go();
int main(){
    #ifdef tokitsukaze
        freopen("TEST.txt","r",stdin);
    #endif
    go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e6+10;
const ll mod=998244353;
/*********************************  head  *********************************/
void assert_lr(int x,int l,int r){assert(x>=l&&x<=r);}
struct LCA
{
    #define type int
    struct node{int to;type w;node(){}node(int _to,type _w):to(_to),w(_w){}};
    type dis[MAX];
    int path[2*MAX],deep[2*MAX],first[MAX],len[MAX],tot,n;
    int dp[2*MAX][22];
    vector<node> mp[MAX];
    void dfs(int x,int pre,int h)
    {
        int i;
        path[++tot]=x;
        first[x]=tot;
        deep[tot]=h;
        for(i=0;i<mp[x].size();i++)
        {
            int to=mp[x][i].to;
            if(to==pre) continue;
            dis[to]=dis[x]+mp[x][i].w;
            len[to]=len[x]+1;
            dfs(to,x,h+1);
            path[++tot]=x;
            deep[tot]=h;
        }
    }
    void ST(int n)
    {
        int i,j,x,y;
        for(i=1;i<=n;i++) dp[i][0]=i;
        for(j=1;(1<<j)<=n;j++)
        {
            for(i=1;i+(1<<j)-1<=n;i++)
            {
                x=dp[i][j-1];
                y=dp[i+(1<<(j-1))][j-1];
                dp[i][j]=deep[x]<deep[y]?x:y;
            }
        }
    }
    int query(int l,int r)
    {
        int len,x,y;
        len=(int)log2(r-l+1); 
        x=dp[l][len];
        y=dp[r-(1<<len)+1][len];
        return deep[x]<deep[y]?x:y;
    }
    int lca(int x,int y)
    {
        int l,r,pos;
        l=first[x];
        r=first[y];
        if(l>r) swap(l,r);
        pos=query(l,r);
        return path[pos];
    } 
    type get_dis(int a,int b){return dis[a]+dis[b]-2*dis[lca(a,b)];}
    int get_len(int a,int b){return len[a]+len[b]-2*len[lca(a,b)];}
    void init(int _n)
    {
        n=_n;
        for(int i=0;i<=n;i++)
        {
            dis[i]=0;
            len[i]=0;
            mp[i].clear();
        }
    }
    void add_edge(int a,int b,type w=1)
    {
        mp[a].pb(node(b,w));
        mp[b].pb(node(a,w));
    }
    void work(int rt)
    {
        tot=0;
        dfs(rt,0,0);
        ST(2*n-1);
    }
    #undef type
}lca;
/*
lca.init(n);
lca.add_edge(a,b,w) undirected edge.
lca.work(rt);
*/
struct dsu
{
    int pre[MAX];
    void init(int n)
    {
        int i;
        for(i=1;i<=n;i++) pre[i]=i;
    }
    int find(int x)
    {
        if(pre[x]!=x) pre[x]=find(pre[x]);
        return pre[x];
    }
    bool merge(int a,int b)
    {
        int ra,rb;
        ra=find(a);
        rb=find(b);
        if(ra!=rb)
        {
            pre[ra]=rb;
            return 1;
        }
        return 0;
    }
}dsu;
struct node
{
    int x,y;
    ll w;
    node(){}
    node(int a,int b,ll c):x(a),y(b),w(c){}
    friend bool operator<(node a,node b) {return a.w<b.w;}
};
vector<node> edge;
int tot;
ll val[MAX];
int kruskal(int n)
{
    int res=0;
    tot=n;
    dsu.init(2*n);
    sort(all(edge));
    lca.init(2*n);
    for(int i=0;i<sz(edge);i++)
    {
        int x=dsu.find(edge[i].x);
        int y=dsu.find(edge[i].y);
        if(x!=y)
        {
            res+=edge[i].w;
            tot++;
            lca.add_edge(tot,x);
            lca.add_edge(tot,y);
            dsu.merge(x,tot);
            dsu.merge(y,tot);
            val[tot]=edge[i].w;
        }
    }
    return res;
}
typedef unsigned long long ull;
ull myRand(ull &k1, ull &k2){
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 <<23);
    k2 = k3 ^ k4 ^ (k3 >>17) ^ (k4 >>26);
    return k2 + k4;
}
pair<int,int>myRanq(ull&k1,ull&k2,int MAXN){
    int x=myRand(k1,k2)%MAXN+1,y=myRand(k1,k2)%MAXN+1;
    if(x>y)return make_pair(y,x);
    else return make_pair(x,y);
}
void go()
{
    int n,m,i,a,b,q;
    ll c,ans;
    ull a1,a2;
    while(read(n,m))
    {
        assert_lr(n,1,1e6);
        assert_lr(m,1,2e6);
        edge.clear();
        while(m--)
        {
            read(a,b,c);
            assert_lr(c,0,2e9);
            edge.pb(node(a,b,c));
        }
        mem(val,0);
        kruskal(n);
        lca.work(tot);
        read(q);
        assert_lr(q,1,1e6);
        read(a1,a2);
        ans=0;
        while(q--)
        {
            PII qst=myRanq(a1,a2,n);
            ll v=val[lca.lca(qst.fi,qst.se)];
        //    debug(qst,lca.lca(qst.fi,qst.se))
            ans^=v;
        }
        printf("%lld\n",ans);
    }

}

E：骄傲无知的现代人不知道珍惜
首先考虑如果组合数中模数远大于指数的情况。

问题转化为给定一张图，可以加边删边，求 GCPI。

对操作时间建立线段树，会发现每条边的贡献都是一个区间，启示我们使用可撤销并查集维护连通性，预处理逆元进行计算。

如果模数不一定大于指数，此时预处理逆元的方法不再可做。此时需要 LUCAS 定理来辅助求解。

同时，观察可知题中所给的模数不一定为质数，启示我们利用 EXLUCAS 的思想，提前预处理好每个数对应的情况，每次用 CRT 合并起来即可。

时限非常宽松，不需要明显常数优化。

#include <bits/stdc++.h>
using namespace std;
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    //fread->read
    bool IOerror=0;
    //inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;} 
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend){
            p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    template<class T> inline bool read(T &x){
        bool sign=0;char ch=nc();x=0;
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    inline bool read(double &x){
        bool sign=0;char ch=nc();x=0;
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if(ch=='.'){
            double tmp=1; ch=nc();
            for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if(sign)x=-x;
        return true;
    }
    inline bool read(char *s){
        char ch=nc();
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
        return true;
    }
    inline bool read_line(char *s){
        char ch=nc();
        for(;blank(ch);ch=nc());
        if(IOerror)return false;
        for(;ch!='\n'&&!IOerror;ch=nc())*s++=ch;
        *s=0;
        return true;
    }
    inline bool read(char &c){
        for(c=nc();blank(c);c=nc());
        if(IOerror){c=-1;return false;}
        return true; 
    }
    template<class T,class... U>bool read(T& h,U&... t){return read(h)&&read(t...);}
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;
/************* debug begin *************/
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
    int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
    return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);}
#ifdef tokitsukaze 
#define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__);
#else
#define debug(...) 233;
#endif
/*************  debug end  *************/
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int,ll> PIL;
typedef pair<ll,int> PLI;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<PII > VPII;
/************* define end  *************/
void read(int *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(ll *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(double *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void println(VI x){for(int i=0;i<sz(x);i++) printf("%d%c",x[i]," \n"[i==sz(x)-1]);}
void println(VL x){for(int i=0;i<sz(x);i++) printf("%lld%c",x[i]," \n"[i==sz(x)-1]);}
void println(int *x,int l,int r){for(int i=l;i<=r;i++) printf("%d%c",x[i]," \n"[i==r]);}
void println(ll *x,int l,int r){for(int i=l;i<=r;i++) printf("%lld%c",x[i]," \n"[i==r]);}
/*************** IO end  ***************/
void go();
int main(){
    #ifdef tokitsukaze
        freopen("TEST.txt","r",stdin);
    #endif
    go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
//const ll mod=998244353;
ll mod;
/*********************************  head  *********************************/
void assert_lr(int x,int l,int r){assert(x>=l&&x<=r);}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll g,t;
    g=exgcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-a/b*y;
    return g;
}
namespace exCRT
{
    ll excrt(VL &a,VL &b)//res=a_i(mod b_i)
    {
        ll x,y,k,g,c,p,res,bg;
        assert(sz(a)==sz(b));
        assert(sz(a)>0);
    //    debug(a)
    //    debug(b)
        p=b[0];
        res=a[0];
        for(int i=1;i<sz(a);i++)
        {
            c=(a[i]-res%b[i]+b[i])%b[i];
            g=exgcd(p,b[i],x,y);
            bg=b[i]/g;
            if(c%g!=0) return -1;
            x=(x*(c/g))%bg;
            res+=x*p;
            p*=bg;
            res=(res%p+p)%p;
        }
        return (res%p+p)%p;
    }
};
namespace exLucas
{
    ll pow2(ll a,ll b,ll p)
    {
        ll res=1;
        while(b>0)
        {
            if(b&1) res=res*a%p;
            a=a*a%p;
            b>>=1;
        }
        return res;
    }
    ll inv(ll a,ll p)
    {
        ll g,x,y,res;
        g=exgcd(a,p,x,y);
        res=(g==1?(x+p)%p:-1);
        assert(res!=-1);
        return res;
    }
    map<ll,pair<VL,VL> > mp;
    map<PLL,VL > fac;
    void init(VL mod_list)
    {
        ll i,j,p;
        mp.clear();
        fac.clear();
        for(auto mod_i:mod_list)
        {
            p=mod_i;
            VL a,b;
            for(i=2;i*i<=p;i++)
            {
                if(p%i) continue;
                b.pb(1LL);
                while(p%i==0) b[sz(b)-1]*=i,p/=i;
                a.pb(i);
            }
            if(p>1) a.pb(p),b.pb(p);
            mp[mod_i]=MP(a,b);
            for(i=0;i<sz(a);i++)
            {
                if(fac.count(MP(a[i],b[i]))) continue;
                VL fac_tmp=VL(b[i]+1);
                fac_tmp[0]=1;
                for(j=1;j<=b[i];j++)
                {
                    if(j%a[i]) fac_tmp[j]=fac_tmp[j-1]*j%b[i];
                    else fac_tmp[j]=fac_tmp[j-1];
                }
                fac[MP(a[i],b[i])]=fac_tmp;
        //        debug(a[i],b[i])
            }
        }
    }
    ll cal_fac(ll n,ll x,ll p)
    {
        if(!n) return 1LL;
        ll res=1;
        assert(fac.count(MP(x,p)));
        res=res*fac[MP(x,p)][p-1]%p;
        res=pow2(res,n/p,p);
        res=res*fac[MP(x,p)][n%p]%p;
        return res*cal_fac(n/x,x,p)%p;
    }
    ll multilucas(ll n,ll m,ll x,ll p)
    {
        if(m>n) return 0;
        ll i,cnt;
        cnt=0;
        for(i=n;i;i/=x) cnt+=i/x;
        for(i=m;i;i/=x) cnt-=i/x;
        for(i=n-m;i;i/=x) cnt-=i/x;
        return pow2(x,cnt,p)*             \
               cal_fac(n,x,p)%p*          \
               inv(cal_fac(m,x,p),p)%p*   \
               inv(cal_fac(n-m,x,p),p)%p;
    }
    ll C(ll n,ll m,ll p)
    {
        if(m>n||m<0||n<0) return 0;
        ll i,res;
        VL a,b,resa;
        assert(mp.count(p));
        a=mp[p].fi;
        b=mp[p].se;
    //    debug(n,m)
        for(i=0;i<sz(a);i++) resa.pb(multilucas(n,m,a[i],b[i]));
        res=exCRT::excrt(resa,b);
        assert(res!=-1);
        return res;
    }
};
ll ans[MAX],val[MAX];
struct dsu
{
    PII st[MAX];
    int pre[MAX],top;
    ll sum[MAX],res[MAX],sz[MAX];
    multiset<ll> ans;
    void init(int n)
    {
        int i;
        ans.clear();
        for(i=1;i<=n;i++)
        {
            pre[i]=i;
            sz[i]=1;
            sum[i]=val[i];
            res[i]=exLucas::C(sum[i],sz[i],mod);
    //        debug(i,res[i])
            ans.insert(res[i]);
        }
        top=0;
    }
    int find(int x)
    {
        while(x!=pre[x]) x=pre[x];
        return x;
    }
    bool merge(int a,int b)
    {
        int ra,rb;
        ra=find(a);
        rb=find(b);
        if(ra==rb) return 0;
        if(sz[ra]>sz[rb]) swap(ra,rb);
        pre[ra]=rb;
        ans.erase(ans.find(res[ra]));
        ans.erase(ans.find(res[rb]));
        sz[rb]+=sz[ra];
        sum[rb]=(sum[rb]+sum[ra]);
        res[rb]=exLucas::C(sum[rb],sz[rb],mod);
        ans.insert(res[rb]);
        st[top++]=MP(ra,rb);
        return 1;
    }
    void roll_back()
    {
        PII now=st[--top];
        pre[now.fi]=now.fi;
        ans.erase(ans.find(res[now.se]));
        sz[now.se]-=sz[now.fi];
        sum[now.se]=((sum[now.se]-sum[now.fi]));
        assert(sum[now.se]>=0);
        res[now.se]=exLucas::C(sum[now.se],sz[now.se],mod);
        ans.insert(res[now.se]);
        ans.insert(res[now.fi]);
    }
}dsu;
PII e[MAX];
struct Segment_Tree
{
    #define type int
    #define ls (id<<1)
    #define rs (id<<1|1)
    int n,ql,qr;
    type qv;
    VI v[MAX<<2];
    void build(int l,int r,int id)
    {
        v[id].clear();
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,ls);
        build(mid+1,r,rs);
    }
    void update(int l,int r,int id)
    {
        if(l>=ql&&r<=qr)
        {
            v[id].pb(qv);
            return;
        }
        int mid=(l+r)>>1;
        if(ql<=mid) update(l,mid,ls);
        if(qr>mid) update(mid+1,r,rs);
    }
    void build(int _n){n=_n;build(1,n,1);}
    void upd(int l,int r,type v)
    {
        ql=l;
        qr=r;
        qv=v;
        update(1,n,1);
    }
    void dfs(int l,int r,int id)
    {
        int cnt=0;
        for(auto it:v[id]) cnt+=dsu.merge(e[it].fi,e[it].se);
        if(l==r)
        {
            ans[l]=*dsu.ans.rbegin();
            while(cnt--) dsu.roll_back();
            return;
        }
        int mid=(l+r)>>1;
        dfs(l,mid,ls);
        dfs(mid+1,r,rs);
        while(cnt--) dsu.roll_back();
    }
    #undef type
    #undef ls
    #undef rs
}tr;
int l[MAX],r[MAX];
void go()
{
    int n,q,i,op,tot,k;
    exLucas::init(VL{4580564,1145141,100160063,102101809});
    while(read(n,q,mod))
    {
        assert_lr(n,1,8e4);
        assert_lr(q,1,8e4);
        for(i=1;i<=n;i++)
        {
            read(val[i]);
            assert_lr(val[i],0,2e9);
        }
        tot=0;
        for(i=1;i<=q;i++)
        {
            read(op);
            if(op==0)
            {
                tot++;
                read(e[tot].fi,e[tot].se);
                l[tot]=i;
                r[tot]=q;
            }
            else if(op==1)
            {
                read(k);
                assert(k>=0&&k<=tot);
                assert(r[k]==q);
                r[k]=i-1;
            }
            else assert(0);
        }
        tr.build(q);
        for(i=1;i<=tot;i++) tr.upd(l[i],r[i],i);
        dsu.init(n);
        tr.dfs(1,q,1);
        for(i=1;i<=q;i++) printf("%lld\n",ans[i]);
    }
}

F：那一片被文明糟踏过的海洋和天地
首先考虑暴力的做法，对于每个询问串，我们可以暴力扫描 4 个询问串，每次对每 4 个询问串扫描 3n 个原串，匹配算法可以使用 算法，时间复杂度 。

对于多个字符串匹配问题，我们可以想到使用 ac 自动机，考虑将 n 组串都建入到 ac 自动机里，考虑直接进行匹配，当询问串与原串都只有 1 个的时候我们可以转化成为一般的 ac 自动机问题。

以下简称 为自动机，默认在建立自动机时建立了 指针所构成的一颗树。

考虑如何处理多个原串与询问串。首先我们每组原串（3 个）在自动机上结尾节点打上相同的标记，对于一个正在进行匹配的询问串，我们可以发现在自动机上的节点一个点对应的可匹配节点是 树到 1 号点的一条链，一个暴力的想法是跳 链到 1 号点，并开一个桶，表示第 个原串是否被匹配，当然这样的复杂度是不可接受的，观察数据范围，发现 n 较小，若直接每个点开桶时间与空间复杂度都为 刚好过不去，但是超出的时间与空间复杂度又并不是很多。考虑优化，发现桶的每一位所记录的只会是 0/1 ，运用压位的思想，我们可以将 64 个 0/1 位记录在一个 unsigned long long 里面，这样时间复杂度与空间复杂度变为 。

考虑对于二进制位桶的合并，其实就是对于两个数进行一次按位或运算，复杂度同样会缩小到 。

对于第二个询问，问每组原串会被多少个询问串包含，我们可以考虑在询问串进行匹配的时候在节点上打上相同的询问串标记，一个原串能被哪些询问串包含就是 树上这个原串结尾子树内询问串的所有标记，按照 树叶子到根进行合并求解即可。

总复杂度为 在可接受范围内。

由于普通的ac自动机实现方法是需要将每条边都补全出来，由于这个是数串，所以暴力补全的想法不再适用，这时我们需要在构建 指针的时候额外进行一些处理，这里需要注意一下。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;};return *s++;}
int read()
{
    char c;
    int w=1;
    while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
    int ans=c-'0';
    while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    return ans*w;
}
const int xx=5e4+5;
struct node
{
    map<int,int>to;
    int fail;
    bitset<20001>toroot;
    bitset<50001>tosubtree;
}e[xx];
int cst=1,a[xx],cnt;
int insert(int id)
{
    int last=1;
    for(int i=1;i<=cnt;i++)
    {
        if(e[last].to.find(a[i])==e[last].to.end())e[last].to[a[i]]=++cst;
        last=e[last].to[a[i]];
    }
    e[last].toroot[id]=1;
    return last;
}
vector<int>v[xx];
int n,m;
vector<int>sx;
void getfail()
{
    queue<int>q;
    sx.push_back(1);
    for(auto it:e[1].to)
    {
        e[it.second].fail=1;
        q.push(it.second);
    }
    e[1].fail=1;
    while(!q.empty())
    {
        int x=q.front();
        sx.push_back(x);
        q.pop();
        for(auto it:e[x].to)
        {
            int to=it.second,i=it.first;
            int p=e[x].fail;
            while(p!=1&&e[p].to.find(i)==e[p].to.end())p=e[p].fail;//特别注意与普通ac自动机不同 
            e[to].fail=(e[p].to.find(i)==e[p].to.end())?1:e[p].to[i];
            q.push(to);
        }
    }
}
bitset<20001>lin;
bitset<50001>col;
signed main(){
    n=read();
    for(int k=1;k<=n;k++)
    {
        int p=3;
        while(p--)
        {
            cnt=read();
            for(int i=1;i<=cnt;i++)a[i]=read();
            v[k].push_back(insert(k));
        }
    }
    getfail();
    for(int i=0;i<sx.size();i++)e[sx[i]].toroot|=e[e[sx[i]].fail].toroot;
    m=read();
    for(int k=1;k<=m;k++)
    {
        lin.reset();
        int p=4;
        while(p--)
        {
            cnt=read();
            for(int i=1;i<=cnt;i++)a[i]=read();
            int last=1;
            for(int i=1;i<=cnt;i++)
            {
                while(last!=1&&e[last].to.find(a[i])==e[last].to.end())last=e[last].fail;
                if(e[last].to.find(a[i])==e[last].to.end())last=1;
                else last=e[last].to[a[i]];
                e[last].tosubtree[k]=1;
                lin|=e[last].toroot;
            }
        }
        cout<<lin.count()<<"\n";
    }
    for(int i=sx.size()-1;i>=0;i--)e[e[sx[i]].fail].tosubtree|=e[sx[i]].tosubtree;
    for(int i=1;i<=n;i++)
    {
        col.reset();
        for(int j=0;j<v[i].size();j++)col|=e[v[i][j]].tosubtree;
        cout<<col.count()<<" \n"[i==n];
    }
    return 0;
}
/*
3 4
3 1 2 3 
2 7 8 
1 9

1 56 
2 1 2 
3 1 2 5

4 5 4 1 4 
1 6 
1 7

4 1 2 3 4 
2 8 9 
1 7
1 114

4 7 8 9 1 
2 8 6 
1 9982
1 514

3 3 2 1 
3 2 3 1
3 7 7 7
3 8 8 8

1 56
3 1 2 5
1 114
1 514 

3    (1 2 3)
2    (1 3)
1    (3)
1    (2)

2 2 3 


*/
全部评论

相关推荐

05-15 10:25
西安交通大学 Java
点赞 评论 收藏
分享
05-14 15:10
海康威视_技术支持部_云存储开发工程师(准入职员工)
海康威视内推-海康威视内推码
真实工作体验！【工作时间】&nbsp;海康实行弹性工作制，一般九点半之前到公司就可以。对于实习生来说，一般只要打够八个半小时的卡就好了。这点还是不错的，早点上班就可以早点下班。正式工可能需要大小周，具体看部门要求。实习生应该都是双休的，不过周末去的话也会给你发工资。中午休息一个半小时，大部分员工都会自己买午休床。&nbsp;【公司环境】&nbsp;实习报到的时候会给你分配一台电脑，一般都是无盘机，配置很普通，不允许自己带电脑。海康对网络管控比较严格，很多网站不能访问。想要访问外网的话只能通过虚拟机，然后通过公司内部的文件传输工具传到红网，这点还是比较麻烦的。&nbsp;海康食堂还行，样式挺丰富的，价格也不贵。早餐我一般在5-10r，...
海康威视公司福利 334人发布
点赞 评论 收藏
分享
04-18 00:32
已编辑
中南大学 Java
点赞 评论 收藏
分享
05-03 16:29
西京学院 Java
点赞 评论 收藏
分享
05-17 06:46
武汉科技大学 设计
点赞 评论 收藏
分享
评论
3
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的求职总结 #
7103次浏览 146人参与
# 辞职之后最想做的一件事 #
7605次浏览 81人参与
# 我的实习日记 #
2410638次浏览 25234人参与
# 选offer应该考虑哪些因素 #
7375次浏览 111人参与
# 一人一个landing小技巧 #
33458次浏览 618人参与
# 工作后会跟朋友渐行渐远吗 #
20076次浏览 153人参与
# 你小时候最想从事什么职业 #
89534次浏览 1676人参与
# 你想留在一线还是回老家？ #
35345次浏览 430人参与
# 设计人如何选offer #
107918次浏览 706人参与
# 生物制药/化工校招攻略 #
42546次浏览 282人参与
# 比亚迪求职进展汇总 #
702859次浏览 3058人参与
# 毕业季，给职场新人一些建议 #
6133次浏览 99人参与
# 你们公司哪个部门最累？ #
13822次浏览 114人参与
# 毕业后不工作的日子里我在做什么 #
167219次浏览 1478人参与
# 大学最后一个寒假，我想…… #
35264次浏览 451人参与
# 秋招想进国企该如何准备 #
56547次浏览 363人参与
# 工作中的卑微时刻 #
8725次浏览 54人参与
# 市场营销面经 #
40830次浏览 298人参与
# 25届网易互娱暑实进度 #
72033次浏览 672人参与
# 薪资爆料 #
101535次浏览 1035人参与
牛客网
牛客企业服务