SDOI2017 R2泛做

2022-08-22 18:50:21

由于各种原因，在bzoj上我day1的题一题都没过，所以这里就直接贴loj的链接好了。

中心极限定理。

https://en.wikipedia.org/wiki/Central_limit_theorem

由于某些原因这里的公式挂了...直接看维基吧...

要算积分可以用标准库里的erf：https://en.wikipedia.org/wiki/Error_function。

对于正态分布，值落在[-x,x]的概率为，所以落在[0,x]的概率就是这个值的一半，这玩意儿就可以直接当做不定积分了。

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <time.h>

#include <stdlib.h>

#include <string>

#include <bitset>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

#include <iomanip>

using namespace std;

#define pb push_back

#define mp make_pair

typedef pair<int,int> pii;

typedef long long ll;

typedef double ld;

typedef vector<int> vi;

#define fi first

#define se second

#define fe first

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}

#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}

#define es(x,e) (int e=fst[x];e;e=nxt[e])

#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])

#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}

#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}

#define SZ 666666

int x,y,a,b,T;

ld f[];

void sol()

{

    scanf("%d%d",&x,&y);

    if((ll)x*y*y<=)

    {

        for(int i=;i<=x*y;++i) f[i]=;

        for(int i=;i<=y;++i)

        {

            for(int j=x*y;j>=x;--j)

                f[j]-=f[j-x];

            for(int j=;j<=x*y;++j)

            {

                f[j]/=x;

                if(j) f[j]+=f[j-];

            }

        }

        for(int i=;i<=;++i)

        {

            int l,r;

            scanf("%d%d",&l,&r);

            ld ans=f[r];

            if(l) ans-=f[l-];

            printf("%.10lf\n",ans);

        }

    }

    else

    {

        int n=y; ld m=(x-)/2.0,s=(x*(ld)x-)/;

        ld k=-n*m,b=sqrt(n*s*);

        for(int i=;i<=;++i)

        {

            ld l,r;

            scanf("%lf%lf",&l,&r);

            l-=0.5,r+=0.5;

            l=(l+k)/b; r=(r+k)/b;

            printf("%.10lf\n",(erf(r)-erf(l))/);

        }

    }

}

int main()

{

    scanf("%d",&T);

    while(T--) sol();

}

D1T2 苹果树

首先如果是树上有父亲限制的01背包，可以参见http://www.cnblogs.com/zzqsblog/p/5537440.html。

现在不是01背包了，为了方便起见，一个ai>1的点我们拆成一个ai=1和一个ai比原来少1的点，把这个新点挂在ai=1的点下面进行dp。

多重背包显然可以单调队列优化。

现在剩的就是那个莫名其妙的k。我们枚举一条到叶子的链（注意这里我们忽略ai>1的点），那么我们的要求就是在除了这条链以外最多只能有k个点。

我们进行一次这个背包，可以得到一个dfs序，即我们可以得到一个dfs序后缀的背包信息，那我们把每个点的儿子反过来再得到一个dfs序，把两个dfs序这两个后缀并在一起，恰好就是整棵树去掉这条链，泛化背包类似搞搞就行。

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <time.h>

#include <stdlib.h>

#include <string>

#include <bitset>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

#include <iomanip>

using namespace std;

#define pb push_back

#define mp make_pair

typedef pair<int,int> pii;

typedef long long ll;

typedef double ld;

typedef vector<int> vi;

#define fi first

#define se second

#define fe first

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define Tree vector<int> ch[SZ];\

void setf(int x,int f) {ch[f].pb(x);}

#define esb(x,e,b) \

(unsigned __=,b=(__<ch[x].size())?(ch[x][__]):;\

__<ch[x].size();++__,b=(__<ch[x].size())?(ch[x][__]):)

#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}

#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}

#define SZ 1234567

namespace FF

{

char ch,B[<<],*S=B,*T=B;

#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)

#define isd(c) (c>='0'&&c<='9')

int aa,bb;int F(){

    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=:(aa=ch-'',bb=);

    while(ch=getc(),isd(ch))aa=aa*+ch-'';return bb?aa:-aa;

}

}

#define gi FF::F()

int T,n,k;

#define max(a,b) (((a)>(b))?(a):(b))

#define cmax(a,b) (((a)<(b))?((a)=(b)):0)

Tree

int m1[],m2[];

#define R(x,a) (x+(a)*(k+1))

inline void pack(int*r,int v,int x) //x个重1价值v

{

    if(!x);

    else if(x==)

        for(int i=k;i>=;--i)

            cmax(r[i],r[i-]+v);

    else if(x>=k)

        for(int i=;i<=k;++i)

            cmax(r[i],r[i-]+v);

    else

    {

        static pii qs[SZ];

        int h=,t=;

        for(int j=;j<=k;j++)

        {

            int cv=r[j]-j*v;

            while(h!=t&&qs[t-].fi<cv) --t;

            qs[t++]=pii(cv,j);

            while(qs[h].se<j-x) ++h;

            r[j]=qs[h].fi+j*v;

        }

    }

}

int fa[SZ],a[SZ],v[SZ],dep[SZ],fc[SZ];

int d1[SZ],c1=,l1[SZ],d2[SZ],c2=,l2[SZ],r1[SZ],r2[SZ];

inline void dfs(int x,int*d,int&c,int*l,int*r)

{

    d[x]=++c; r[c]=x;

    for esb(x,e,b)

        dep[b]=dep[x]+,fc[b]=fc[x]+v[b],

        dfs(b,d,c,l,r);

    l[x]=c;

}

inline void work(int*d,int&c,int*l,int*p,int*r)

{

    for(int i=c;i>=;--i)

    {

        int x=r[i],*A=R(p,d[x]),*B=R(p,l[x]+),*C=R(p,d[x]+);

        for(int s=;s<=k;s++)

            A[s]=max(B[s],C[s-]+v[x]);

        pack(A,v[x],a[x]-);

    }

}

bool good[SZ];

void sol()

{

    n=gi,k=gi; int N=n; c1=c2=;

    for(int i=;i<=n+n;++i)

        good[i]=,ch[i].clear();

    ll tot=;

    for(int i=;i<=N;++i)

    {

        fa[i]=gi,a[i]=gi,v[i]=gi; tot+=a[i];

        if(fa[i]) setf(i,fa[i]),good[fa[i]]=;

        if(a[i]>)

        {

            ++n; setf(n,i); a[n]=a[i]-; good[n]=;

            v[n]=v[i]; fa[n]=i; a[i]=;

        }

    }

    int tt=(n+)*(k+);

    memset(m1,,tt*sizeof(int));

    memset(m2,,tt*sizeof(int));

    dep[]=; fc[]=v[];

    dfs(,d1,c1,l1,r1);

    work(d1,c1,l1,m1,r1);

    for(int i=;i<=n;++i)

        reverse(ch[i].begin(),ch[i].end());

    dfs(,d2,c2,l2,r2);

    work(d2,c2,l2,m2,r2);

    int ans=;

    for(int i=;i<=n;++i)

    {

        if(!good[i]) continue;

        int x=min(tot-dep[i],(ll)k);

        int*f=R(m1,d1[i]+),*g=R(m2,l2[i]+);

        for(int s=;s<=x;++s)

            cmax(ans,fc[i]+f[s]+g[x-s]);

    }

    printf("%d\n",ans);

}

int main()

{

    T=gi; while(T--) sol();

}

D1T3 切树游戏

这里讲一下本人常数很大的做法。首先众所周知如果有一个序列A和一个序列B，A和B做异或卷积等于C，那么fwt(A)*fwt(B)（点乘）=fwt(C)。

我们记v[i]为单点值fwt之后的数组，那么有如下的dp方程：

$s[i]=v[i]\prod_cs[c]+1$（c是i的孩子，+1是加上空子树的情况）

最后我们要求的是$\sum_{i=1}^ns[i]$。求出这玩意儿之后ifwt回去，把n个空子树扣掉就有答案了。

考虑记$g[i]=v[i]\prod_{c'}s[c']$，c'是i的轻孩子。

这玩意儿可以支持修改，只要修改的时候跳重链就好。

现在的问题就是要求出重链顶端的s值以及把一整条重链的s值求和。

我们只考虑重链的话，可以发现$s[i]=s[w]g[i]+1$，w是i的重孩子，如果我们把g预处理成矩阵（每个元素都是向量），然后这玩意儿是可以矩乘的，同时也可以顺便把s求和。然后线段树维护一下就好了。注意到矩阵有一些位置是不变的可以减小常数。

这玩意儿还是常数爆炸了，那我也没有办法，复杂度都是一样的...

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <time.h>

#include <stdlib.h>

#include <string>

#include <bitset>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

#include <iomanip>

using namespace std;

#define pb push_back

#define mp make_pair

typedef pair<int,int> pii;

typedef long long ll;

typedef double ld;

typedef vector<int> vi;

#define fi first

#define se second

#define fe first

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}

#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}

#define es(x,e) (int e=fst[x];e;e=nxt[e])

#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])

#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}

#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}

#define SZ 66666

#pragma pack(1)

int n,m,q; Edg

#define SZ 33333

const int MOD=;

int inv[MOD+];

struct num

{

short x; short z;

num() {x=z=;}

num(int p) {(p%=MOD)?(x=p,z=):(x=z=);}

inline operator int() const {return z?:x;}

};

inline num operator * (num a,num b)

{a.x=int(a.x)*b.x%MOD; a.z+=b.z; return a;}

inline num operator / (num a,num b)

{a.x=int(a.x)*inv[b.x]%MOD; a.z-=b.z; return a;}

template<class T>

struct arr

{

T g[];

arr() {for(int i=;i<m;++i) g[i]=;}

void fwt()

{

    for(int i=;i<m;i<<=)

    {

        for(int j=;j<m;++j)

        {

            if(j&i) continue;

            int a=g[j],b=g[j|i];

            g[j]=(a+b)%MOD;

            g[j|i]=(a+MOD-b)%MOD;

        }

    }

}

void ifwt() //only for <short>

{

    fwt();

    for(int i=;i<m;++i)

        g[i]=g[i]*(int)inv[m]%MOD;

}

template<class T1>

operator arr<T1> ()

{

    arr<T1> r;

    for(int i=;i<m;++i) r.g[i]=g[i];

    return r;

}

};

arr<num> one_n,zero_n;

arr<short> one_i,zero_i;

template<class T>

arr<T> operator + (arr<T> a,arr<T> b)

{

    for(int i=;i<m;++i)

        a.g[i]=(int(a.g[i])+b.g[i])%MOD;

    return a;

}

template<class T>

arr<T> operator - (arr<T> a,arr<T> b)

{

    for(int i=;i<m;++i)

        a.g[i]=(int(a.g[i])+MOD-b.g[i])%MOD;

    return a;

}

arr<num> operator * (arr<num> a,arr<num> b)

{

    for(int i=;i<m;++i)

        a.g[i]=a.g[i]*b.g[i];

    return a;

}

arr<short> operator * (arr<short> a,arr<short> b)

{

    for(int i=;i<m;++i)

        a.g[i]=a.g[i]*(int)b.g[i]%MOD;

    return a;

}

arr<num> operator / (arr<num> a,arr<num> b)

{

    for(int i=;i<m;++i)

        a.g[i]=a.g[i]/b.g[i];

    return a;

}

struct mat

{

arr<short> g00,g01,g20,g21;

/*

x y 0

0 1 0

z s 1

*/

};

mat operator * (mat a,mat b)

{

    mat p;

    p.g00=a.g00*b.g00;

    p.g01=a.g00*b.g01+a.g01;

    p.g20=a.g20*b.g00+b.g20;

    p.g21=a.g20*b.g01+a.g21+b.g21;

    return p;

}

//pair(w,s)

pair<arr<short>,arr<short> > cp(mat s)

{

    return make_pair(s.g00+s.g01,s.g20+s.g21);

}

inline mat gs(arr<short> x)

{

    mat s;

    s.g01=s.g21=one_i;

    s.g00=s.g20=x; return s;

}

arr<short> sw,isw; //sum of w[i]

arr<num> v[SZ],g[SZ],w[SZ]; mat gm[SZ]; //重链顶端的w保证正确

int fa[SZ],son[SZ],sz[SZ],top[SZ],fi[SZ],bt[SZ],C=;

arr<num> ts[];

void dfs(int x,int f=)

{

    fa[x]=f; sz[x]=;

    for esb(x,e,b) if(b!=f)

    {

        dfs(b,x),sz[x]+=sz[b];

        if(sz[b]>sz[son[x]]) son[x]=b;

    }

}

void dfs2(int x,int t,int f=)

{

    top[x]=t; fi[x]=++C; bt[t]=C;

    if(!son[x]) return;

    dfs2(son[x],t,x);

    for esb(x,e,b) if(b!=f&&b!=son[x])

        dfs2(b,b,x);

}

const int Z=;

mat seg[Z+Z+],I;

void dfs3(int x,int f=,int d=)

{

    for esb(x,e,b) if(b!=f) dfs3(b,x,d+);

    g[x]=v[x];

    for esb(x,e,b) if(b!=f) g[x]=g[x]*w[b];

    w[x]=g[x]+one_n; if(son[x]) g[x]=g[x]/w[son[x]];

    seg[Z+fi[x]]=gm[x]=gs(g[x]); sw=sw+arr<short>(w[x]);

}

void upd(int x)

{

    for((x+=Z)>>=;x;x>>=) seg[x]=seg[x+x]*seg[x+x+];

}

mat qry(int l,int r)

{

    mat rs=I; static int st[SZ]; int sn=;

    for(l+=Z-,r+=Z+;l^r^;l>>=,r>>=)

    {

        if(~l&) rs=rs*seg[l^];

        if(r&) st[++sn]=r^;

    }

    while(sn) rs=rs*seg[st[sn--]];

    return rs;

}

int main()

{

    inv[]=;

    for(int i=;i<MOD;++i)

        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;

    scanf("%d%d",&n,&m);

    static int a[SZ];

    for(int i=;i<=n;++i) scanf("%d",a+i);

    for(int i=;i<n;++i)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        adde(a,b);

    }

    for(int i=;i<m;++i) one_n.g[i]=,zero_n.g[i]=;

    for(int i=;i<m;++i) one_i.g[i]=,zero_i.g[i]=;

    I.g00=one_i; I.g01=I.g20=I.g21=zero_i;

    sw=zero_i; dfs(); dfs2(,);

    for(int i=;i<m;++i)

        ts[i]=zero_n, ts[i].g[i]=, ts[i].fwt();

    for(int i=;i<=n;++i) v[i]=ts[a[i]];

    dfs3(); isw=sw; isw.ifwt();

    for(int i=Z-;i>=;--i)

        seg[i]=seg[i+i]*seg[i+i+];

    int q; scanf("%d",&q);

    while(q--)

    {

        char s[]; scanf("%s",s);

        if(s[]=='Q')

        {

            int a; scanf("%d",&a);

            ll ans=isw.g[a];

            if(!a) ans-=n;

            ans=(ans%MOD+MOD)%MOD;

            printf("%d\n",int(ans));

        }

        else

        {

            int x,y;

            scanf("%d%d",&x,&y);

            mat r=qry(fi[top[x]],bt[top[x]]);

            pair<arr<short>,arr<short> > s=cp(r); sw=sw-s.se;

            g[x]=g[x]/v[x]*ts[y]; v[x]=ts[y];

            seg[Z+fi[x]]=gm[x]=gs(g[x]); upd(fi[x]); x=top[x];

            r=qry(fi[top[x]],bt[top[x]]);

            s=cp(r); sw=sw+s.se;

            while(fa[x])

            {

                int y=fa[x]; g[y]=g[y]/w[x]*arr<num>(s.fi);

                w[x]=s.fi; x=y;

                r=qry(fi[top[x]],bt[top[x]]);

                s=cp(r); sw=sw-s.se;

                seg[Z+fi[x]]=gm[x]=gs(g[x]); upd(fi[x]); x=top[x];

                r=qry(fi[top[x]],bt[top[x]]);

                s=cp(r); sw=sw+s.se;

            }

            w[x]=s.fi; isw=sw; isw.ifwt();

        }

    }

}

D2T1 天才黑客

好像这种做法不是最优的，比标解多了一个log的样子。

考虑把边拆点，拆成入点和出点，中间连边权。然后1号点连上入点，出点连上边另一个端点。接下来我们要做的就是把同一个点的入边的出点和出边的入点之间连边。

考虑把这些点提取出来在字典树上建个虚树，然后连边的话考虑lca为一个点的有哪些点对，要么是子树之间的，要么是自己和整棵树之间的，在dfs序上建两棵线段树辅助一下连边就好了。

代码难度还是挺高的...

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <time.h>

#include <stdlib.h>

#include <string>

#include <bitset>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

#include <iomanip>

using namespace std;

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef double ld;

typedef vector<int> vi;

#define fi first

#define se second

#define fe first

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}

#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}

#define es(x,e) (int e=fst[x];e;e=nxt[e])

#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])

#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}

#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}

#define SZ 2000000

int N=;

#define SS 3500000

int M=,fst[SS],vb[SS],nxt[SS],vc[SS];

void ad_de(int a,int b,int c=){if(a&&b);else return;

//cout<<a<<"->"<<b<<"[label="<<c<<"]\n";

++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b; vc[M]=c;}

void ad_fe(int a,int b,int c=) {ad_de(b,a,c);}

typedef pair<ll,int> pii;

ll dist[SS];

#define fi first

#define se second

void dj()

{

    priority_queue<pii,vector<pii>,greater<pii> > pq;

    for(int i=;i<=N;++i) dist[i]=1e18;

    dist[]=; pq.push(pii(,));

    while(!pq.empty())

    {

        pii t=pq.top(); pq.pop();

        if(t.fi!=dist[t.se]) continue;

        int x=t.se;

        for(int e=fst[x];e;e=nxt[e])

        {

            int b=vb[e];

            if(dist[b]<=dist[x]+vc[e])

                continue;

            dist[b]=dist[x]+vc[e];

            pq.push(pii(dist[b],b));

        }

    }

}

template<void f(int,int,int)>

struct seg

{

int Z,s[SZ];

void init(int n)

{

    Z=; while(Z<=n+) Z<<=;

    for(int i=;i<=Z+Z;++i) s[i]=++N;

    for(int i=Z-;i>=;--i)

        f(s[i],s[i+i],),f(s[i],s[i+i+],);

}

int gr(int l,int r)

{

    int p=++N;

    if(l>r) return p;

    for(l+=Z-,r+=Z+;l^r^;l>>=,r>>=)

    {

        if(~l&) f(p,s[l^],);

        if(r&) f(p,s[r^],);

    }

    return p;

}

};

seg<ad_de> zs;

seg<ad_fe> fs;

int fl[SZ];

namespace vt

{

Edg

int C,df[SZ],ls[SZ];

void dfs(int x)

{

    df[x]=++C;

    for esb(x,e,b) dfs(b);

    ls[x]=C;

}

void dfs2(int x)

{

    int l=df[x],r=df[x];

    ::ad_de(fs.gr(l,r),zs.gr(l,r),fl[x]);

    for esb(x,e,b) dfs2(b);

    for esb(x,e,b)

    {

        ::ad_de(fs.gr(l,r),zs.gr(df[b],ls[b]),fl[x]),

        ::ad_de(fs.gr(df[b],ls[b]),zs.gr(l,r),fl[x]);

        r=ls[b];

    }

}

void doit(int r)

{

    C=; dfs(r); zs.init(C);

    fs.init(C); dfs2(r);

}

}

namespace rt

{

Edg

int n,dfn[SZ],C=,sz[SZ],son[SZ];

void dfs(int x,int f=)

{

    if(f) fl[x]=fl[f]+; dfn[x]=++C; sz[x]=; son[x]=;

    for esb(x,e,b)

    {

        dfs(b,x); sz[x]+=sz[b];

        if(sz[b]>sz[son[x]]) son[x]=b;

    }

}

int top[SZ],fa[SZ];

void dfs2(int x,int t,int f=)

{

    fa[x]=f; top[x]=t;

    if(!son[x]) return;

    dfs2(son[x],t,x);

    for esb(x,e,b) if(b!=son[x]) dfs2(b,b,x);

}

int lca(int a,int b)

{

    while(top[a]!=top[b])

        if(fl[top[a]]<fl[top[b]]) b=fa[top[b]];

        else a=fa[top[a]];

    return (fl[a]<fl[b])?a:b;

}

bool cmp(int a,int b) {return dfn[a]<dfn[b];}

void init()

{

    C=M=;

    for(int i=;i<=n;++i) fst[i]=;

    for(int i=;i<n;++i)

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        ad_de(a,b);

    }

    dfs();dfs2(,);

}

int vs[SZ],st[SZ],vn=,stn=,vfa[SZ];

void buildrt(int*g,int gn)

{

    sort(g+,g++gn,cmp);

    gn=unique(g+,g++gn)-g-;

    vn=stn=;

    for(int i=;i<=gn;i++) vs[++vn]=g[i],vfa[g[i]]=;

    for(int i=;i<=gn;i++)

    {

        int x=g[i];

        if(!stn) {st[++stn]=x; vfa[x]=; continue;}

        int lca=rt::lca(x,st[stn]);

        for(;fl[st[stn]]>fl[lca];--stn)

            if(fl[st[stn-]]<=fl[lca])

                vfa[st[stn]]=lca;

        if(st[stn]!=lca)

        {

            vs[++vn]=lca;

            vfa[lca]=st[stn];

            st[++stn]=lca;

        }

        vfa[x]=lca; st[++stn]=x;

    }

    int ro=; vt::M=;

    for(int i=;i<=vn;++i)

        vt::fst[vs[i]]=;

    for(int i=;i<=vn;++i)

        if(vfa[vs[i]]) vt::ad_de(vfa[vs[i]],vs[i]); else ro=vs[i];

    vt::doit(ro);

}

}

namespace Sol

{

int n,m,k,ea[SZ],eb[SZ],ec[SZ],ed[SZ],i1[SZ],i2[SZ];

namespace Z{Edgc}

namespace F{Edgc}

void sol()

{

    scanf("%d%d%d",&n,&m,&k); Z::M=F::M=;

    ::M=; ::N=n; memset(::fst,,sizeof ::fst);

    for(int i=;i<=n;++i) Z::fst[i]=F::fst[i]=;

    for(int i=;i<=m;++i)

    {

        scanf("%d%d%d%d",ea+i,eb+i,ec+i,ed+i);

        Z::ad_de(ea[i],eb[i],i);

        F::ad_de(eb[i],ea[i],i);

        i1[i]=++N; i2[i]=++N;

        ad_de(i1[i],i2[i],ec[i]);

        if(ea[i]==) ad_de(,i1[i]);

        ad_de(i2[i],eb[i]);

    }

    rt::n=k; rt::init();

    for(int i=;i<=n;++i)

    {

        static int tmp[SZ]; int tn=;

        for(int e=Z::fst[i];e;e=Z::nxt[e])

            tmp[++tn]=ed[Z::vc[e]];

        for(int e=F::fst[i];e;e=F::nxt[e])

            tmp[++tn]=ed[F::vc[e]];

        rt::buildrt(tmp,tn);

        for(int e=F::fst[i];e;e=F::nxt[e])

            ad_de(i2[F::vc[e]],fs.s[vt::df[ed[F::vc[e]]]+fs.Z]);

        for(int e=Z::fst[i];e;e=Z::nxt[e])

            ad_de(zs.s[zs.Z+vt::df[ed[Z::vc[e]]]],i1[Z::vc[e]]);

    }

    dj();

    for(int i=;i<=n;++i)

        printf("%lld\n",dist[i]);

}

}

int main()

{

    int T; scanf("%d",&T);

    for(int i=;i<=T;++i) Sol::sol();

}

D2T2 遗忘的集合

euler transform裸题，详见 http://l0nl1f3.leanote.com/post/Euler-Transform-discussion

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <time.h>

#include <stdlib.h>

#include <string>

#include <bitset>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

#include <iomanip>

using namespace std;

#define pb push_back

#define mp make_pair

typedef pair<int,int> pii;

typedef long long ll;

typedef double ld;

typedef vector<int> vi;

#define fi first

#define se second

#define fe first

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}

#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}

#define es(x,e) (int e=fst[x];e;e=nxt[e])

#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])

#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}

#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}

#define SZ 666666

//mtt

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define mp make_pair

#define x first

#define y second

#define pb push_back

#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b,  : ; }

template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b,  : ; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

int Mod = 1e9 + ;

#define MOD Mod

ll qp(ll a,ll b)

{

    ll x=;

    while(b)

    {

        if(b&) x=x*a%MOD;

        a=a*a%MOD; b>>=;

    }

    return x;

}

const int max0 = ;

struct comp

{

    double x, y;

    comp(): x(), y() { }

    comp(const double &_x, const double &_y): x(_x), y(_y) { }

};

inline comp operator+(const comp &a, const comp &b) { return comp(a.x + b.x, a.y + b.y); }

inline comp operator-(const comp &a, const comp &b) { return comp(a.x - b.x, a.y - b.y); }

inline comp operator*(const comp &a, const comp &b) { return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }

inline comp conj(const comp &a) { return comp(a.x, -a.y); }

const double PI = acos(-);

int N,L;

comp w[max0 + ];

int bitrev[max0 + ];

void fft(comp *a, const int &n)

{

    REP(i, , n) if (i < bitrev[i]) swap(a[i], a[bitrev[i]]);

    for (int i = , lyc = n >> ; i <= n; i <<= , lyc >>= )

        for (int j = ; j < n; j += i)

        {

            comp *l = a + j, *r = a + j + (i >> ), *p = w;

            REP(k, , i >> )

            {

                comp tmp = *r * *p;

                *r = *l - tmp, *l = *l + tmp;

                ++l, ++r, p += lyc;

            }

        }

}

inline void fft_prepare()

{

    REP(i, , N) bitrev[i] = bitrev[i >> ] >>  | ((i & ) << (L - ));

    REP(i, , N) w[i] = comp(cos( * PI * i / N), sin( * PI * i / N));

}

inline void conv(int *x, int *y, int *z)

{

    REP(i, , N) (x[i] += Mod) %= Mod, (y[i] += Mod) %= Mod;

    static comp a[max0 + ], b[max0 + ];

    static comp dfta[max0 + ], dftb[max0 + ], dftc[max0 + ], dftd[max0 + ];

    REP(i, , N) a[i] = comp(x[i] & , x[i] >> );

    REP(i, , N) b[i] = comp(y[i] & , y[i] >> );

    fft(a, N), fft(b, N);

    REP(i, , N)

    {

        int j = (N - i) & (N - );

        static comp da, db, dc, dd;

        da = (a[i] + conj(a[j])) * comp(0.5, );

        db = (a[i] - conj(a[j])) * comp(, -0.5);

        dc = (b[i] + conj(b[j])) * comp(0.5, );

        dd = (b[i] - conj(b[j])) * comp(, -0.5);

        dfta[j] = da * dc;

        dftb[j] = da * dd;

        dftc[j] = db * dc;

        dftd[j] = db * dd;

    }

    REP(i, , N) a[i] = dfta[i] + dftb[i] * comp(, );

    REP(i, , N) b[i] = dftc[i] + dftd[i] * comp(, );

    fft(a, N), fft(b, N);

    REP(i, , N)

    {

        int da = (LL)(a[i].x / N + 0.5) % Mod;

        int db = (LL)(a[i].y / N + 0.5) % Mod;

        int dc = (LL)(b[i].x / N + 0.5) % Mod;

        int dd = (LL)(b[i].y / N + 0.5) % Mod;

        z[i] = (da + ((LL)(db + dc) << ) + ((LL)dd << )) % Mod;

    }

}

int x[SZ],g[SZ],tmp[SZ],tx[SZ],d[SZ],r[SZ];

void ginv(int s)

{

    if(s==)

    {

        g[]=qp(x[],Mod-);

        return;

    }

    ginv(s-);

    L=s+; N=1LL<<L; fft_prepare();

    for(int i=N/;i<N;++i) g[i]=;

    for(int i=;i<N/;++i) tx[i]=x[i];

    conv(tx,g,tmp);

    for(int i=N/;i<N;++i) tmp[i]=;

    for(int i=;i<N;++i) tmp[i]=((i?:)-tmp[i]+MOD)%MOD;

    conv(g,tmp,g);

    for(int i=N/;i<N;++i) g[i]=;

}

int n,rs[SZ];

int main()

{

    scanf("%d%d",&n,&MOD); ++n; x[]=;

    for(int i=;i<n;++i) scanf("%d",x+i);

    int s=;

    while(n>(<<s)) ++s;

    ginv(s);

    L=s+; N=<<L; fft_prepare();

    for(int i=;i<n;++i) d[i-]=x[i]*ll(i)%MOD;

    conv(d,g,r);

    vector<int> ans;

    for(int i=;i<n;++i)

    {

        rs[i]=(r[i-]-rs[i]+MOD)%MOD;

        for(int j=i+i;j<=n;j+=i) (rs[j]+=rs[i])%=MOD;

        if(rs[i]) ans.pb(i);

    }

    printf("%d\n",int(ans.size()));

    for(unsigned j=;j<ans.size();++j)

        printf("%d ",ans[j]);puts("");

}

D2T3 文本校正

假设把原串切成123，那么有以下拼合方法：

123 （那可真蠢）

231、312 （枚举个切分点切开，然后哈希判一判）

213：枚举3的位置，然后可以发现1和2的长度的可能取值必须是两个前缀的最大匹配之一，证明参见相关题目题解，kmp+hash即可。

132：把上面一个倒过来。

321：考虑把两个串做C变换（C(a,b)=a[1]b[n]a[2]b[n-1]...a[n]b[1]），然后就是要判断这个玩意儿是不是一个三偶回文串。枚举一个切分点，就是要看后缀是不是双偶回文串，两个回文串中至少有一个可以是最长回文前缀/最长回文后缀，最长回文后缀直接暴力判，最长回文前缀跑完manacher之后更新一遍。（我们需要知道以每个下标作为左端点的最长回文串。从右到左扫描，维护一下当前的左边界，做第i位时我们只要更新当前i-p[i]~左边界-1这一段，然后更新左边界。正确性显然。）

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <time.h>

#include <stdlib.h>

#include <string>

#include <bitset>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

#include <iomanip>

using namespace std;

#define pb push_back

#define mp make_pair

typedef pair<int,int> pii;

typedef long long ll;

typedef double ld;

typedef vector<int> vi;

#define fi first

#define se second

#define fe first

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}

#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}

#define es(x,e) (int e=fst[x];e;e=nxt[e])

#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])

#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}

#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}

#define SZ 4444444

int l[],r[];

int T,n,m;

const int MOD=,S=;

ll po[SZ];

template<const int G>

struct str

{

int s[G],n;

ll qz[G];

int fail[G],pal[G],sp[G];

void mlc() //malache

{

    int ml=,p=; s[n+]=-;s[]=-;

    for(int i=;i<=n;++i)

    {

        if(i<=ml) pal[i]=min(pal[p+p-i],ml-i);

        else pal[i]=;

        while(i>=pal[i]+&&

        s[i-pal[i]-]==s[i+pal[i]+])

            ++pal[i];

        if(i+pal[i]>ml)

            ml=i+pal[i],p=i;

    }

    for(int i=n;i>=;--i) sp[i]=;

    int cl=n+;

    for(int i=n;i>=;--i)

    {

        for(int j=min(cl-,i);j>=i-pal[i];--j)

            cl=j,sp[j]=max(sp[j],i-j);

    }

}

void init()

{

    for(int i=;i<=n;++i)

        qz[i]=(qz[i-]*S+s[i])%MOD;

    fail[]=;

    for(int i=,j=;i<=n;++i)

    {

        while(j&&s[j+]!=s[i]) j=fail[j];

        if(s[j+]==s[i]) ++j; fail[i]=j;

    }

}

inline ll hsh(int l,int r)

{

    ll rs=qz[r]-qz[l-]*po[r-l+];

    rs%=MOD; return (rs<)?(rs+MOD):rs;

}

void r()

{

    reverse(s+,s++n);

}

const str& operator = (const str<G>& b)

{

    n=b.n; memcpy(s,b.s,sizeof(int)*(n+));

}

};

str<> a,b,ra,rb;

bool w213(str<>&a,str<>&b)

{

    int o=n+;

    for(int i=n;i>=&&a.s[i]==b.s[i];--i) o=i;

    for(int i=,j=;i<n;++i)

    {

        while(j&&a.s[j+]!=b.s[i]) j=a.fail[j];

        if(a.s[j+]==b.s[i]) ++j;

        if(i+<o||!j) continue;

        if(a.hsh(j+,i)==b.hsh(,i-j))

        {

            l[]=; r[]=j;

            l[]=j+; r[]=i;

            l[]=i+; r[]=n;

            return ;

        }

    }

    for(int i=,j=;i<n;++i)

    {

        while(j&&b.s[j+]!=a.s[i]) j=b.fail[j];

        if(b.s[j+]==a.s[i]) ++j;

        if(i+<o||!j) continue;

        if(b.hsh(j+,i)==a.hsh(,i-j))

        {

            l[]=; r[]=i-j;

            l[]=i-j+; r[]=i;

            l[]=i+; r[]=n;

            return ;

        }

    }

    return ;

}

str<> t,rt;

str<> tt;

bool w321()

{

    t.n=;

    for(int i=;i<=n;++i)

        t.s[++t.n]=a.s[i],

        t.s[++t.n]=b.s[n+-i];

    rt=t; rt.r(); t.init(); rt.init();

    tt.n=; tt.s[++tt.n]=m+;

    for(int i=;i<=t.n;++i)

        tt.s[++tt.n]=t.s[i],tt.s[++tt.n]=m+;

    tt.mlc();

    int rm=;

    for(int r=n+n;r>=;--r)

    {

        if(t.hsh(r,n+n)==rt.hsh(,n+n-r+)) rm=n+n-r+;

        int gs=tt.sp[r*-]/*;

        if(r&);else continue;

        //case1: r-1|...|rm

        {

            int a=r-,c=rm,b=n+n-a-c;

            if(a>&&b>&&c>&&a%==&&b%==&&c%==&&

            t.hsh(,a)==rt.hsh(n+n-a+,n+n)

            &&t.hsh(a+,a+b)==rt.hsh(n+n-a-b+,n+n-a)

            //&&t.hsh(n+n-c+1,n+n)==rt.hsh(1,c)

            )

            {

                a/=,b/=,c/=;

                l[]=; ::r[]=a;

                l[]=a+; ::r[]=a+b;

                l[]=a+b+; ::r[]=n;

                return ;

            }

        }

        //case2: r-1|gs|...

        {

            int a=r-,b=gs,c=n+n-a-b;

            if(a>&&b>&&c>&&a%==&&b%==&&c%==&&

            t.hsh(,a)==rt.hsh(n+n-a+,n+n)

            &&t.hsh(a+,a+b)==rt.hsh(n+n-a-b+,n+n-a)

            &&t.hsh(n+n-c+,n+n)==rt.hsh(,c)

            )

            {

                a/=,b/=,c/=;

                l[]=; ::r[]=a;

                l[]=a+; ::r[]=a+b;

                l[]=a+b+; ::r[]=n;

                return ;

            }

        }

    }

    return ;

}

namespace FF

{

char ch,B[<<],*S=B,*T=B;

#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)

#define isd(c) (c>='0'&&c<='9')

int aa,bb;int F(){

    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=:(aa=ch-'',bb=);

    while(ch=getc(),isd(ch))aa=aa*+ch-'';return bb?aa:-aa;

}

}

#define gi FF::F()

void sol()

{

    n=gi,m=gi; a.n=b.n=ra.n=rb.n=n;

    for(int i=;i<=n;++i) b.s[i]=gi;

    for(int i=;i<=n;++i) a.s[i]=gi;

    ra=a; rb=b; ra.r(); rb.r();

    a.init(); b.init(); ra.init(); rb.init();

    l[]=r[]=-;

    if(n<)

    {

        puts("NO");

        return;

    }

    bool s=;

    for(int i=;i<=n;++i) s&=a.s[i]==b.s[i];

    if(s)

    {

        puts("YES");

        puts("1 1");

        puts("2 2");

        printf("3 %d\n",n);

        return;

    }

    for(int i=;i<n;++i)

    {

        if(a.hsh(,i)==b.hsh(n-i+,n)&&

        a.hsh(i+,n)==b.hsh(,n-i))

        {

            if(i!=)

            {

                puts("YES");

                printf("%d %d\n",i+,n);

                puts("1 1");

                printf("2 %d\n",i);

                return;

            }

            else

            {

                puts("YES");

                printf("%d %d\n",i+,i+);

                printf("%d %d\n",i+,n);

                puts("1 1");

                return;

            }

        }

    }

    bool f=w213(a,b);

    if(f)

    {

        puts("YES");

        printf("%d %d\n",l[],r[]);

        printf("%d %d\n",l[],r[]);

        printf("%d %d\n",l[],r[]);

        return;

    }

    f=w213(ra,rb);

    if(f)

    {

        for(int i=;i<;++i)

            l[i]=n+-l[i],r[i]=n+-r[i],

            swap(l[i],r[i]);

        puts("YES");

        printf("%d %d\n",l[],r[]);

        printf("%d %d\n",l[],r[]);

        printf("%d %d\n",l[],r[]);

        return;

    }

    f=w321();

    if(f)

    {

        puts("YES");

        printf("%d %d\n",l[],r[]);

        printf("%d %d\n",l[],r[]);

        printf("%d %d\n",l[],r[]);

        return;

    }

    puts("NO");

}

int main()

{

    po[]=;

    for(int i=;i<SZ;++i)

        po[i]=po[i-]*S%MOD;

    T=gi;

    while(T--) sol();

}

完结撒花

码农公寓

相关文章