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

BZOJ4008: [HNOI2015]亚瑟王

  • 显然
  • 于是设
  • 时间复杂度

BZOJ4009: [HNOI2015]接水果

  • 整体二分,问题变成了刚开始给出p条路径,询问p路径有多少条路径是给定路径的子路径。
  • 转dfs序,考虑p中的一条路径


,目前BZOJ rank 1。


BZOJ4010: [HNOI2015]菜肴制作

  • 将图反向,求拓扑序,每次取编号最大的点,优先队列维护,最后逆序输出。
  • 想想为什么:




  • 时间复杂度:


BZOJ4011: [HNOI2015]落忆枫音

  • 考虑DAG的树形图,
  • 考虑一个环对树形图个数的贡献:
  • 环必定经过边
  • 就是统计所有路径的贡献,记忆话搜索即可。
  • 时间复杂度:

BZOJ4012: [HNOI2015]开店

  • 以年龄为时间轴,建立可持久化边分治结构,类似主席树的方法直接查询。

  • 时间复杂度:


BZOJ4013: [HNOI2015]实验比较

首先并查集合并=号,对于小于号发现是一棵森林,加入超级根变成树。

树形DP,

转移时需要知道,显然:

直接将子树依次合并就行。
时间复杂度


代码

BZOJ4008: [HNOI2015]亚瑟王

4008.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=225,maxm=135;
int n,m;
double P[maxn],D[maxn];
double f[maxn][maxm],pw[maxn][maxm],pr[maxn];

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",P+i,D+i),pw[i][0]=1;
    memset(f,0,sizeof(f));
    memset(pr,0,sizeof(pr));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            pw[i][j]=pw[i][j-1]*(1.-P[i]);
}

void work()
{
    f[0][m]=1;
    for(int j=m;j>0;j--)
        for(int i=0;i<n;i++)
        {
            f[i+1][j]+=f[i][j]*pw[i+1][j];
            f[i+1][j-1]+=f[i][j]*(1.-pw[i+1][j]);
            pr[i+1]+=f[i][j]*(1.-pw[i+1][j]);
        }
    double ans=0;
    for(int i=1;i<=n;i++)
        ans+=pr[i]*D[i];
    printf("%.12lf\n",ans);
}

int main()
{
    int CT;
    for(scanf("%d",&CT);CT--;)
    {
        init();
        work();
    }
    return 0;
}


BZOJ4009: [HNOI2015]接水果

4009.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
inline void readi(int &x);
const int maxn=40005;
int n,pn,qn,sn;
int ans[maxn];
int head[maxn],adj[maxn*2],next[maxn*2],tot=1;
int dfn[maxn],las[maxn],idx,dep[maxn],fa[maxn][17],lg2[maxn];

int tr[maxn];

void add(int x,const int &c)
{for(;x;x^=x&-x)tr[x]+=c;}
int get(int x)
{int r=0;for(;x<=n;x+=x&-x)r+=tr[x];return r;}

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 path
{
    int u,v,c,id;
    inline bool operator<(const path &o)const
    {return c<o.c;}
}p[maxn],q[maxn],q_[maxn];

bool cmpx(const path &a,const path &b)
{return a.u<b.u;}

struct seg
{
    int x,y1,y2,c;
    seg(){}
    seg(const int &_x,const int &_y1,const int &_y2,const int &_c)
    :x(_x),y1(_y1),y2(_y2),c(_c){}
    inline bool operator<(const seg &o)const
    {return x<o.x;}
}s[maxn*2],sp[maxn][5];

int getup(int x,int d)
{
    for(;d;d^=d&-d)x=fa[x][lg2[d&-d]];
    return x;
}

void tdfs(const int &x)
{
    dfn[x]=++idx;
    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]);
    las[x]=idx;
}

void addseg(int u,int v,seg *s)
{
    int sn=0;
    if(dfn[v]>=dfn[u]&&dfn[v]<=las[u])
    {
        int z=getup(v,dep[v]-dep[u]-1);
        if(dfn[z]>1)
            s[sn++]=seg(0,dfn[v]-1,las[v],1),
            s[sn++]=seg(dfn[z]-1,dfn[v]-1,las[v],-1);
        if(las[z]<n)
            s[sn++]=seg(dfn[v]-1,las[z],n,1),
            s[sn++]=seg(las[v],las[z],n,-1);
    }
    else
    {
        if(dfn[u]>dfn[v])swap(u,v);
        s[sn++]=seg(dfn[u]-1,dfn[v]-1,las[v],1);
        s[sn++]=seg(las[u],dfn[v]-1,las[v],-1);
    }
}

void init()
{
    readi(n),readi(pn),readi(qn);
    lg2[1]=0;
    for(int i=2,u,v;i<=n;i++)
    {
        readi(u),readi(v);
        addedge(u,v);
        lg2[i]=lg2[i-1]+((i&-i)==i);
    }
    tdfs(1);
    for(int j=1;j<=16;j++)
        for(int i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    for(int i=1;i<=pn;i++)
    {
        readi(p[i].u),readi(p[i].v),readi(p[i].c);
        if(dep[p[i].u]>dep[p[i].v])swap(p[i].u,p[i].v);
    }
    sort(p+1,p+pn+1);
    for(int i=1;i<=pn;i++)
        addseg(p[i].u,p[i].v,sp[i]);
    for(int i=1;i<=qn;i++)
    {
        readi(q[i].u),readi(q[i].v),readi(q[i].c);
        q[i].u=dfn[q[i].u],q[i].v=dfn[q[i].v];
        q[i].id=i;
        if(q[i].u>q[i].v)swap(q[i].u,q[i].v);
    }
    sort(q+1,q+qn+1,cmpx);
}

void solve(int l,int r,int a,int b)
{
    if(l==r)
    {
        for(int i=a;i<=b;i++)
            ans[q[i].id]=p[l].c;
        return;
    }
    int m=l+r>>1,pos,i,j,k,t;
    sn=0;
    for(i=l;i<=m;i++)
        for(int j=0;sp[i][j].c;j++)
            s[++sn]=sp[i][j];
    sort(s+1,s+sn+1);
    for(i=a,j=1,k=a;i<=b;i++)
    {
        for(;j<=sn&&s[j].x<q[i].u;j++)
            add(s[j].y2,s[j].c),
            add(s[j].y1,-s[j].c);
        t=get(q[i].v);
        if(q[i].c<=t)q_[k++]=q[i],q[i].c=-1;
        else q[i].c-=t;
    }
    for(;j<=sn;j++)
        add(s[j].y2,s[j].c),
        add(s[j].y1,-s[j].c);
    pos=k;
    for(i=a;i<=b;i++)
    {
        if(q[i].c!=-1)q_[k++]=q[i];
        q[i]=q_[i];
    }
    solve(l,m,a,pos-1);
    solve(m+1,r,pos,b);
}

int main()
{
    init();
    solve(1,pn,1,qn);
    for(int i=1;i<=qn;i++)
        printf("%d\n",ans[i]);
    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');}


BZOJ4010: [HNOI2015]菜肴制作

4010.cpp
#include<cstdio>
#include<queue>
using namespace std;
inline void readi(int &x);
const int maxn=100005;
int n,m;
int d[maxn],s[maxn];
int head[maxn],adj[maxn*2],next[maxn*2],tot;
priority_queue<int> Q;
void addedge(int u,int v)
{tot++;adj[tot]=v;next[tot]=head[u];head[u]=tot;}
int main()
{
    int CT,flag;
    for(readi(CT);CT--;)
    {
        readi(n),readi(m);
        tot=1;
        for(int i=1;i<=n;i++)head[i]=d[i]=0;
        for(int i=1,u,v;i<=m;i++)
            readi(u),readi(v),addedge(v,u),d[u]++;
        for(int i=1;i<=n;i++)
            if(!d[i])Q.push(i);
        flag=1;
        for(int x=n,i;x>0;x--)
        {
            if(Q.empty()){flag=0;puts("Impossible!");break;}
            s[x]=Q.top(),Q.pop();
            for(i=head[s[x]];i;i=next[i])
                if(--d[adj[i]]==0)Q.push(adj[i]);
        }
        if(flag)
        {
            for(int i=1;i<=n;i++)
                printf("%d ",s[i]);
            puts("");
        }
    }
    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');}


BZOJ4011: [HNOI2015]落忆枫音

4011.cpp
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=100005,maxm=222222,M=1000000007;
int n,m,X,Y;
int head[maxn],adj[maxm],next[maxm],tot=1;
int d[maxn];
int inv[maxn],ans,f[maxn];

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

inline void up(int &x,const int &y)
{x+=y;if(x>=M)x-=M;}

void init()
{
    scanf("%d%d%d%d",&n,&m,&X,&Y);
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        d[v]++;
    }
    d[Y]++;
    ans=1;
    for(int i=2;i<=n;i++)
        ans=(LL)ans*d[i]%M;
    inv[1]=1;
    for(int i=2;i<=n;i++)inv[i]=(LL)inv[M%i]*(M-M/i)%M;
    memset(f,-1,sizeof(f));
}

int dfs(const int &x)
{
    if(x==X)return inv[d[X]];
    if(f[x]!=-1)return f[x];
    int &sum=f[x];
    sum=0;
    for(int i=head[x];i;i=next[i])
        up(sum,dfs(adj[i]));
    sum=(LL)sum*inv[d[x]]%M;
    return sum;
}

void work()
{
    if(Y==1){printf("%d\n",ans);return;}
    ans=(LL)ans*(1-dfs(Y))%M;
    if(ans<0)ans+=M;
    printf("%d\n",ans);
}

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


BZOJ4012: [HNOI2015]开店

4012.cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
inline void readi(int &x);
const int maxn=150005;
int n,Q,AM;
int head[maxn],adj[maxn*2],c[maxn*2],next[maxn*2],tot=1;
int siz[maxn],fa[maxn];
bool vis[maxn*2];

long long ans;

struct monster
{
    int pos,age;
    bool operator<(const monster &o)const
    {return age<o.age;}
}mo[maxn];

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

struct node
{
    int L,R;
    int ls,rs;
    LL ld,rd;
    node *lc,*rc;
}pool[5000000],*pns=pool,*root[maxn];

namespace RMQ
{
    int pos[maxn],tn;
    int st[maxn*3][19],dep[maxn];
    int lg2[maxn*3];
    void tdfs(const int &x)
    {
        pos[x]=++tn;
        *st[tn]=dep[x];
        for(int i=head[x];i;i=next[i])
            if(adj[i]!=fa[x])
            {
                fa[adj[i]]=x;
                dep[adj[i]]=dep[x]+c[i];
                tdfs(adj[i]);
                *st[++tn]=dep[x];
            }
    }
    void init()
    {
        dep[1]=0;
        fa[1]=0,tdfs(1);
        lg2[0]=-1;
        for(int i=1;i<=tn;i++)
            lg2[i]=lg2[i-1]+((i&-i)==i);
        for(int j=1;j<=18;j++)
            for(int i=1;i+(1<<j)-1<=tn;i++)
                st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    }
    int get(const int &l,const int &r)
    {
        int k=lg2[r-l+1];
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
    int dist(int u,int v)
    {
        if(pos[u]>pos[v])swap(u,v);
        return dep[u]+dep[v]-(get(pos[u],pos[v])<<1);
    }
}

void init()
{
    readi(n),readi(Q),readi(AM);
    for(int i=1,x;i<=n;i++)
    {
        readi(x);
        mo[i].age=x,mo[i].pos=i;
    }
    sort(mo+1,mo+n+1);
    mo[0].age=-1,mo[n+1].age=AM+1;
    for(int i=1,u,v,w;i<n;i++)
    {
        readi(u),readi(v),readi(w);
        addedge(u,v,w);
    }
    RMQ::init();
}

//TREE DIVIDE

int szl,nos;

void dfs1(const int &x)
{
    siz[x]=1;
    for(int i=head[x];i;i=next[i])
        if(!vis[adj[i]]&&adj[i]!=fa[x])
        {
            fa[adj[i]]=x;
            dfs1(adj[i]);
            siz[x]+=siz[adj[i]];
        }
    if(siz[x]<=szl&&siz[x]>siz[nos])nos=x;
}

node* build(int u,int sz)
{
    node *c=++pns;
    if(sz==1){c->L=c->R=0;return c;}
    szl=sz+1>>1;nos=0;
    fa[u]=0,dfs1(u);
//if(siz[u]!=sz)exit(0);
 int lsz=siz[nos];
    c->L=nos;c->R=fa[nos];
    vis[c->R]=1;
    c->lc=build(c->L,lsz);
    vis[c->R]=0;
    vis[c->L]=1;
    c->rc=build(c->R,sz-lsz);
    vis[c->L]=0;
    return c;
}

void Insert(node* &c,const int &x)
{
    if(!c->L)return;
    node *temp=++pns;
    *temp=*c;
    c=temp;
    int dl=RMQ::dist(x,c->L),dr=RMQ::dist(x,c->R);
    if(dl<dr)
    {
        c->ls++,c->ld+=dl;
        Insert(c->lc,x);
    }
    else
    {
        c->rs++,c->rd+=dr;
        Insert(c->rc,x);
    }
}

LL Query(node* &c,const int &x)
{
    if(!c->L)return 0;
    int dl=RMQ::dist(x,c->L),dr=RMQ::dist(x,c->R);
    long long ret;
    if(dl<dr)
    {
        ret=c->rd+(LL)c->rs*dr;
        ret+=Query(c->lc,x);
    }
    else
    {
        ret=c->ld+(LL)c->ls*dl;
        ret+=Query(c->rc,x);
    }
    return ret;
}

void work()
{
    root[0]=build(1,n);
    root[1]=root[0];
    for(int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        Insert(root[i],mo[i].pos);
    }
}

int FindL(const int &x);
int FindR(const int &x);

const bool isonline=1;

void solve()
{
    for(int qi=1,x,a,b,l,r;qi<=Q;qi++)
    {
        readi(x),readi(a),readi(b);
        if(isonline)
        {
            a=(ans+a)%AM;
            b=(ans+b)%AM;
        }
        l=min(a,b),r=max(a,b);
        l=FindL(l);
        r=FindR(r);
        ans=Query(root[r],x);
        ans-=Query(root[l],x);
        printf("%lld\n",ans);
    }
}

int main()
{
    init();
    work();
    solve();
    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');}

int FindL(const int &x)
{
    int low=0,high=n+1,mid;
    while(low+1<high)
    {
        mid=low+high>>1;
        if(mo[mid].age<x)low=mid;
        else high=mid;
    }
    return low;
}

int FindR(const int &x)
{
    int low=0,high=n+1,mid;
    while(low+1<high)
    {
        mid=low+high>>1;
        if(mo[mid].age<=x)low=mid;
        else high=mid;
    }
    return low;
}


BZOJ4013: [HNOI2015]实验比较

4013.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn=105,M=1000000007;
int n,m;
int bf[maxn];
int X[maxn],Y[maxn];
bool notroot[maxn];
int head[maxn],adj[maxn],next[maxn],tot;

int f[maxn][maxn],s[maxn];
int C[maxn*2][maxn*2],T[maxn*2][maxn*2][maxn*2];

inline void up(int &x,const int &y)
{x+=y;if(x>=M)x-=M;}

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

int getf(int x)
{return bf[x]?bf[x]=getf(bf[x]):x;}

int dell[maxn];

void init()
{
    scanf("%d%d",&n,&m);
    C[0][0]=1;
    for(int i=1;i<maxn;i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
            up(C[i][j],C[i-1][j-1]),up(C[i][j],C[i-1][j]);
    }
    for(int i=0;i<=n;i++)
        for(int j=0;i+j<=n;j++)
            for(int k=0;k<=i+j;k++)
                T[i][j][k]=(LL)C[k][i]*C[i][i+j-k]%M;
    char opt[5];
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%s%d",&x,opt,&y);
        if(*opt=='=')
        {
            x=getf(x),y=getf(y);
            if(x!=y)bf[y]=x,notroot[y]=1,dell[y]=1;
        }
        else X[i]=x,Y[i]=y;
    }
    for(int i=1;i<=m;i++)
        if(X[i])
        {
            X[i]=getf(X[i]),Y[i]=getf(Y[i]);
            addedge(X[i],Y[i]);
            notroot[Y[i]]=1;
        }
}

bool vis[maxn];
int siz[maxn];

void dfs(int x)
{
    if(vis[x]){puts("0");exit(0);}
    vis[x]=1;
    if(head[x]==0){siz[x]=1,f[x][1]=1;return;}
    f[x][0]=1;
    for(int p=head[x];p;p=next[p])
    {
        dfs(adj[p]);
        for(int i=0;i<maxn;i++)
            s[i]=f[x][i],f[x][i]=0;
        for(int i=0;i<=siz[x];i++)
            for(int j=0;j<=siz[adj[p]];j++)
                for(int k=0;k<=i+j;k++)
                    up(f[x][k],(LL)s[i]*f[adj[p]][j]%M*T[i][j][k]%M);
        siz[x]+=siz[adj[p]];
    }
    siz[x]++;
    for(int i=siz[x];i>0;i--)f[x][i]=f[x][i-1];
    f[x][0]=0;
}

void work()
{
    for(int i=1;i<=n;i++)
        if(!notroot[i])addedge(n+1,i);
    n++;
    dfs(n);
    for(int i=1;i<=n;i++)
        if(!vis[i]&&!dell[i])
            {puts("0");exit(0);}
    int ans=0;
    for(int i=0;i<=siz[n];i++)
        up(ans,f[n][i]);
    printf("%d\n",ans);
}

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

 
comments powered by Disqus