Menu
April 22, 2015
只想看代码的直接翻到最下面

BZOJ3996: [TJOI2015]线性代数

一眼最小割,首先计算出答案

然后对于所有i<j,连边

对于所有i,连边:

做最小割得到c,则


BZOJ3997: [TJOI2015]组合数学

Dilworth定理:有向无环图(DAG)的最小链覆盖=最大点独立集

于是只要从左下角到右上角DP就可以了

时间复杂度:


BZOJ3998: [TJOI2015]弦论

先构造出后缀自动机(SAM),然后统计一下以某个点开始的子串数目,最后从root开始26分查找就行了。

时间复杂度


BZOJ3999: [TJOI2015]旅游

树链剖分裸题树链剖分不会的看这个

线段树节点维护:

合并也很简单

struct msg
struct msg
{
    LL mn,mx,m1,m2;
    msg(const LL &_mn=0,const LL &_mx=0,const LL &_m1=0,const LL &_m2=0):mn(_mn),mx(_mx),m1(_m1),m2(_m2){}
    friend inline msg operator+(const msg &a,const msg &b)
    {return msg(min(a.mn,b.mn),max(a.mx,b.mx),max(max(a.m1,b.m1),b.mx-a.mn),max(max(a.m2,b.m2),a.mx-b.mn));}
};

链剖时注意信息的合并顺序,且信息本身是有序的。

复杂度

具体看代码吧。


BZOJ4000: [TJOI2015]棋盘

题面略坑,行列编号是从0开始的。

题目里说,样例秒打脸。

说解法吧:显然一行的方案是否合法只跟上一行有关,设表示第i行,状态为j时的方案数,那么转移时枚举上一行状态是的,如果使用矩阵乘法优化DP,可以做到


BZOJ4001: [TJOI2015]概率论

首先递推出n个节点所有形态的二叉树的叶子节点的总数,发现是个,而n个节点的二叉树有个,用通项公式展开,得到公式.

精度是个大问题,我用的是手写高精度除法。。。就不用考虑精度误差啦!

如果是在BZOJ上交的话,由于标程本身精度不够,所以跟std交一样的:

4001_std
long long n;
cin>>n;
cout<<fixed<<setprecision(9)<<1.0*n*(n+1)/(4*n-2)<<endl;

TJOI2015就这么做完啦。。。水不水呢……

代码:

BZOJ3996: [TJOI2015]线性代数
3996.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
inline void readi(int &x);
const int maxn=555,maxm=3333333,inf=(1<<30)-1;
int n;
int B[maxn][maxn];
int C[maxn],SF[maxn];
int ans,maxflow;

int head[maxn],adj[maxm],f[maxm],next[maxm],tot=1;
int S,T,level[maxn],q[maxn],qh,qt;

void addedge(int u,int v,int w)
{tot++;adj[tot]=v;f[tot]=w;next[tot]=head[u];head[u]=tot;
tot++;adj[tot]=u;f[tot]=0;next[tot]=head[v];head[v]=tot;}

bool bfs()
{
    qh=0,q[qt=1]=S;
    memset(level,-1,T+1<<2);
    level[S]=0;
    for(int u,i;qh<qt;)
    {
        u=q[++qh];
        for(i=head[u];i;i=next[i])
            if(f[i]>0&&level[adj[i]]==-1)
            {
                level[adj[i]]=level[u]+1;
                if(adj[i]==T)return 1;
                q[++qt]=adj[i];
            }
    }
    return 0;
}

int aug(int u,int flow)
{
    if(u==T)return maxflow+=flow,flow;
    int left=flow,t;
    for(int i=head[u];i&&left;i=next[i])
        if(level[adj[i]]==level[u]+1&&f[i]>0)
        {
            t=aug(adj[i],min(left,f[i]));
            left-=t;
            f[i]-=t;
            f[i^1]+=t;
        }
    if(left==flow)level[u]=-1;
    return flow-left;
}

void init()
{
    readi(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            readi(B[j][i]),ans+=B[j][i]<<1;
    for(int i=1;i<=n;i++)
        readi(C[i]);
    S=n+1,T=n+2;
}

void work()
{
    for(int i=1;i<=n;i++)
        addedge(i,T,C[i]<<1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            addedge(i,j,B[i][j]+B[j][i]);
            addedge(j,i,B[i][j]+B[j][i]);
            SF[i]+=B[i][j]+B[j][i];
            SF[j]+=B[i][j]+B[j][i];
        }
        SF[i]+=B[i][i]<<1;
    }
    for(int i=1;i<=n;i++)
        addedge(S,i,SF[i]);
    
    while(bfs())
        aug(S,inf);
    printf("%d\n",ans-maxflow>>1);
}

int main()
{
    init();
    work();
    return 0;
}

inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}


BZOJBZOJ3997: [TJOI2015]组合数学
3997.cpp
#include<cstdio>
#include<algorithm>
using namespace std;
inline void readi(int &x);
const int maxn=1005;
int n,m;
int a[maxn][maxn];
long long f[maxn][maxn];

void init()
{
    readi(n),readi(m);
    for(int i=n;i>0;i--)
        for(int j=1;j<=m;j++)
            readi(a[i][j]);
}

void work()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=max(f[i-1][j-1]+a[i][j],max(f[i][j-1],f[i-1][j]));
    printf("%lld\n",f[n][m]);
}

int main()
{
    int T;
    for(readi(T);T--;)
    {
        init();
        work();
    }
    return 0;
}

inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}


BZOJ3998: [TJOI2015]弦论
3998.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn=1000005;
int T,K;
char s[maxn],ans[maxn];
int len;
int Q[maxn],W[maxn];
namespace Suffix_Automaton
{
    struct Sam
    {
        Sam *nex[26],*pre;
        int dep;
        LL w,s;
    }P[maxn],*root=P+1,*last=root,*ns=root;
    
    void Extend(int x)
    {
        Sam *p=last,*np=++ns;
        np->dep=p->dep+1;
        np->w=1;
        last=np;
        for(;p&&!p->nex[x];p=p->pre)
            p->nex[x]=np;
        if(!p)np->pre=root;
        else
        {
            Sam *q=p->nex[x];
            if(q->dep==p->dep+1)
                np->pre=q;
            else
            {
                Sam *nq=++ns;
                memcpy(nq->nex,q->nex,sizeof(q->nex));
                nq->pre=q->pre;
                nq->dep=p->dep+1;
                np->pre=q->pre=nq;
                for(;p&&p->nex[x]==q;p=p->pre)
                    p->nex[x]=nq;
            }
        }
    }
    
    void work()
    {
        int L=ns-P;
        for(int i=1;i<=L;i++)
            W[P[i].dep]++;
        for(int i=1;s[i];i++)
            W[i]+=W[i-1];
        for(int i=L;i;i--)
            Q[W[P[i].dep]--]=i;
        for(int i=L;i>1;i--)
            if(T)
                P[Q[i]].pre->w+=P[Q[i]].w;
            else P[Q[i]].w=1;
        P[1].w=0;
        for(int i=L;i;i--)
        {
            Sam &p=P[Q[i]];
            p.s=p.w;
            for(int j=0;j<26;j++)
                if(p.nex[j])
                    p.s+=p.nex[j]->s;
        }
    }
    
    void solve()
    {
        Sam *p=root;
        while(K)
        {
            if(K<=p->w)return;
            K-=p->w;
            for(int i=0;i<26;i++)
                if(p->nex[i])
                    if(K<=p->nex[i]->s)
                    {
                        ans[len++]=i+'a';
                        p=p->nex[i];
                        break;
                    }
                    else K-=p->nex[i]->s;
        }
    }
}

int main()
{
    using namespace Suffix_Automaton;
    scanf("%s%d%d",s+1,&T,&K);
    for(int i=1;s[i];i++)
        Extend(s[i]-'a');
    work();
    if(K<=root->s)
        solve(),puts(ans);
    else puts("-1\n");
    return 0;
}


BZOJ3999: [TJOI2015]旅游
3999.cpp
#include<cstdio>
#include<algorithm>
using namespace std;
#define all 1,n
typedef long long LL;
inline void readi(int &x);
const int maxn=50005;
const LL inf=(1LL<<60)-1;

int n,Q;
int a[maxn];
int head[maxn],adj[maxn*2],next[maxn*2],tot;
int siz[maxn],son[maxn],fa[maxn],dep[maxn],top[maxn];
int dfn[maxn],dfa[maxn],idx;

inline void addedge(const int &u,const int &v)
{tot++;adj[tot]=v;next[tot]=head[u];head[u]=tot;
tot++;adj[tot]=u;next[tot]=head[v];head[v]=tot;}

struct msg
{
    LL mn,mx,m1,m2;
    msg(const LL &_mn=0,const LL &_mx=0,const LL &_m1=0,const LL &_m2=0):mn(_mn),mx(_mx),m1(_m1),m2(_m2){}
    friend inline msg operator+(const msg &a,const msg &b)
    {return msg(min(a.mn,b.mn),max(a.mx,b.mx),max(max(a.m1,b.m1),b.mx-a.mn),max(max(a.m2,b.m2),a.mx-b.mn));}
};

struct node
{
    LL dta;
    msg c;
    node *lc,*rc;
    
    inline void tagdta(const LL &x)
    {c.mn+=x,c.mx+=x,dta+=x;}
    
    inline void update()
    {c=lc->c+rc->c;}
    
    inline void downdate()
    {
        if(dta)
        {
            lc->tagdta(dta);
            rc->tagdta(dta);
            dta=0;
        }
    }
    
    msg add(int l,int r,const int &a,const int &b,const int &d)
    {
        msg ret;
        if(l>=a&&r<=b)
        {
            ret=c;
            return tagdta(d),ret;
        }
        else
        {
            int mid=l+r>>1;
            downdate();
            if(a>mid)ret=rc->add(mid+1,r,a,b,d);
            else if(b<=mid)ret=lc->add(l,mid,a,b,d);
            else ret=lc->add(l,mid,a,b,d)+rc->add(mid+1,r,a,b,d);
            update();
            return ret;
        }
    }
}ndl[maxn*3],*root;
int ns=1;

node *build(int l,int r)
{
    node *x=ndl+ns++;
    if(l==r)return x->c=msg(a[dfa[l]],a[dfa[r]],0,0),x;
    x->lc=build(l,l+r>>1);
    x->rc=build(l+r+2>>1,r);
    x->update();
    return x;
}

void tdfs(const int &x)
{
    siz[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(int i=head[x];i;i=next[i])
        if(adj[i]!=fa[x])
        {
            fa[adj[i]]=x;
            tdfs(adj[i]);
            siz[x]+=siz[adj[i]];
            if(siz[adj[i]]>siz[son[x]])son[x]=adj[i];
        }
}

void divide(int x,int tp)
{
    dfa[dfn[x]=++idx]=x;
    top[x]=tp;
    if(son[x])divide(son[x],tp);
    for(int i=head[x];i;i=next[i])
        if(adj[i]!=fa[x]&&adj[i]!=son[x])
            divide(adj[i],adj[i]);
}

void init()
{
    readi(n);
    for(int i=1;i<=n;i++)
        readi(a[i]);
    for(int i=1,u,v;i<n;i++)
    {
        readi(u),readi(v);
        addedge(u,v);
    }
    readi(Q);
    tdfs(1);
    divide(1,1);
    root=build(1,n);
}

LL query(int u,int v,int d)
{
    msg su(inf,-inf,0,0),sv(inf,-inf,0,0);
    for(int fu,fv;(fu=top[u])!=(fv=top[v]);)
    {
        if(dep[fu]>dep[fv])
        {
            su=root->add(all,dfn[fu],dfn[u],d)+su;
            u=fa[fu];
        }
        else
        {
            sv=root->add(all,dfn[fv],dfn[v],d)+sv;
            v=fa[fv];
        }
    }
    if(dep[u]>dep[v])
        su=root->add(all,dfn[v],dfn[u],d)+su;
    else
        sv=root->add(all,dfn[u],dfn[v],d)+sv;
    swap(su.m1,su.m2);
    return (su+sv).m1;
}

void work()
{
    for(int u,v,d;Q--;)
    {
        readi(u),readi(v),readi(d);
        printf("%lld\n",query(u,v,d));
    }
}

int main()
{
    init();
    work();
    return 0;
}

inline void readi(int &x)
{char c;while(c=getchar(),c<'0'||c>'9');
x=c^'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');}


BZOJ4000: [TJOI2015]棋盘
4000.cpp
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=100005,B=20;
typedef unsigned Mat[67][67];
int n,m,N;
int P,K;
int ak[B+B][B+B];

Mat temp,tb,X,A;

void mult(Mat &a,Mat &b,Mat &c)
{
    for(short i=0;i<N;i++)
        for(short j=0;j<N;j++)
            temp[i][j]=0,tb[i][j]=b[j][i];
    for(short i=0;i<N;i++)
        for(short j=0;j<N;j++)
            for(short k=0;k<N;k++)
                temp[i][j]+=a[i][k]*tb[j][k];
    for(short i=0;i<N;i++)
        for(short j=0;j<N;j++)
            c[i][j]=temp[i][j];
}

int attack(const int &x,const int &y)
{return ak[B+x+1][B+y+K];}

void init()
{
    scanf("%d%d%d%d",&n,&m,&P,&K);
    N=1<<m;
    for(int i=0;i<3;i++)
        for(int j=0;j<P;j++)
            scanf("%1d",&ak[B+i][B+j]);
}

unsigned check(const int &a,const int &b)
{
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
        {
            if(i!=j&&(1<<i&a)&&(1<<j&a))
                if(attack(0,j-i)||attack(0,i-j))return 0;
            if(i!=j&&(1<<i&b)&&(1<<j&b))
                if(attack(0,j-i)||attack(0,i-j))return 0;
            if((1<<i&a)&&(1<<j&b))
                if(attack(1,j-i)||attack(-1,i-j))return 0;
        }
    return 1;
}

void build()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            X[i][j]=check(i,j);
    for(int i=0;i<N;i++)
        A[i][i]=1;
}

void work()
{
    for(;n;n>>=1,mult(X,X,X))
        if(n&1)mult(A,X,A);
    unsigned ans=0;
    for(int i=0;i<N;i++)
        ans+=A[0][i];
    printf("%u\n",ans);
}

int main()
{
    init();
    build();
    work();
    return 0;
}


BZOJ4001: [TJOI2015]概率论
4001.cpp
#include<cstdio>
const int E=9;
int main()
{
    long long n,z,m;
    scanf("%lld",&n);
    z=n*(n+1),m=n*4-2;
    printf("%lld.",z/m);z%=m;
    for(int i=1;i<E;i++)
        printf("%d",(int)(z*10/m)),z=z*10%m;
    printf("%d\n",(int)((z*10+m/2)/m));
    return 0;
}

Tags: TJOI, bzoj,
 
comments powered by Disqus