ZJOI2016Day1

2016.03.26 15:58 Sat | 72次阅读 | 旧日oi | 固定链接 | 源码

模拟的时候T1爆炸14分,T2卡常50分,T3标准40分……要是真考试估计还会比这低点……

T1 随机树生成器

不会

T2 旅行者

分治+最短路

考虑分治,假设当前的范围m>n,对中间一列的所有点每个点跑一遍对当前n*m范围内的所有点的最短路,然后更新在当前范围内的所有询问的答案。
然后,我们发现,如果对于一个询问其中一个点在左边,一个点在右边,那么此时这个询问的答案就已经被求出来了,因为一定会跨过中间那一列的点。否则我们把询问递归到两边,递归到两边的询问就和另一边的所有点都没有关系了,所以点的范围也可以缩小一半,然后分治下去就可以了。
复杂度的话……对于min(n,m)<=4,直接一直按长边分治就行了,复杂度是:每次对4个点跑dij,$4(nm)log(nm)$,乘上分治的log(n),每个询问要被更新4logn次,复杂度就是$4(nm)log(nm) log(n)+4Qlogn$。
对于所有数据也是这个做法,只是需要一些技巧,比如手写dij的堆(比pbds快),并且分治的时候要选择长边来分,复杂度就不算了……

#include <bits/stdc++.h>
using namespace std;
#define N 20005
int n,m,Q;
char getc(){
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read(){
    static char ch;static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return D;
}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
struct node
{
    int x,y,xx,yy,id;
}a[100005],_a[100005];
struct element{
    int x,y,d;
    bool operator < (const element &x) const {
        return d>x.d;
    }
}q[N*4];
int nowL,nowR,nowU,nowD;
int r[N],c[N];
int dis[N];
bool vis[N];
int ans[100005];
void dij(int sx,int sy) 
{
    for(int i=nowD;i<=nowU;i++)
    for(int j=nowL;j<=nowR;j++)
    {
        dis[(i-1)*m+j]=1<<29;
        vis[(i-1)*m+j]=0;
    }
    element p{sx,sy,0}; dis[(sx-1)*m+sy]=0;
    int tot=0; q[tot++]=p;
    while(tot) 
    {
        p=q[0]; 
        pop_heap(q,q+tot);--tot;
        int id=(p.x-1)*m+p.y;
        if (vis[id]) continue; vis[id]=1;
        if (p.x>nowD&&dis[id-m]>p.d+c[id-m]) { dis[id-m]=p.d+c[id-m]; q[tot++]=((element){p.x-1,p.y,p.d+c[id-m]}),push_heap(q,q+tot); }
        if (p.x<nowU&&dis[id+m]>p.d+c[id]) { dis[id+m]=p.d+c[id]; q[tot++]=((element){p.x+1,p.y,p.d+c[id]}),push_heap(q,q+tot); }
        if (p.y>nowL&&dis[id-1]>p.d+r[id-1]) { dis[id-1]=p.d+r[id-1]; q[tot++]=((element){p.x,p.y-1,p.d+r[id-1]}),push_heap(q,q+tot); }
        if (p.y<nowR&&dis[id+1]>p.d+r[id]) { dis[id+1]=p.d+r[id]; q[tot++]=((element){p.x,p.y+1,p.d+r[id]}),push_heap(q,q+tot); }
    }
}
void solve(int d,int u,int l,int r,int L,int R)
{
    if(l>r||L>R||d>u) return;
    nowL=l;nowR=r;nowD=d;nowU=u;
    if(R-L<min(u-d,r-l))
    {
        for(int i=L;i<=R;i++)
        {
            dij(a[i].x,a[i].y);
            ans[a[i].id]=min(ans[a[i].id],dis[(a[i].xx-1)*m+a[i].yy]);
        }
        return;
    }
    if(u-d<r-l)
    {
        int mid=(l+r)>>1;
        for(int i=d;i<=u;i++) 
        {
            dij(i,mid);
            for(int i=L;i<=R;i++) 
                ans[a[i].id]=min(ans[a[i].id],dis[(a[i].x-1)*m+a[i].y]+dis[(a[i].xx-1)*m+a[i].yy]);
        }
        int tl=L,tr=R;
        for(int i=L;i<=R;i++) 
        {
            if(a[i].y<mid&&a[i].yy<mid) _a[tl++]=a[i];
            else if(a[i].y>mid&&a[i].yy>mid) _a[tr--]=a[i];
        }
        if(l==r) return;
        for(int i=L;i<tl;i++) a[i]=_a[i];
        for(int i=tr+1;i<=R;i++) a[i]=_a[i];
        solve(d,u,l,mid-1,L,tl-1);
        solve(d,u,mid+1,r,tr+1,R);
    }
    else
    {
        int mid=(u+d)>>1;
        for(int i=l;i<=r;i++) 
        {
            dij(mid,i);
            for(int i=L;i<=R;i++) 
                ans[a[i].id]=min(ans[a[i].id],dis[(a[i].x-1)*m+a[i].y]+dis[(a[i].xx-1)*m+a[i].yy]);
        }
        int tl=L,tr=R;
        for(int i=L;i<=R;i++) 
        {
            if(a[i].x<mid&&a[i].xx<mid) _a[tl++]=a[i];
            else if(a[i].x>mid&&a[i].xx>mid) _a[tr--]=a[i];
        }
        if(u==d) return;
        for(int i=L;i<tl;i++) a[i]=_a[i];
        for(int i=tr+1;i<=R;i++) a[i]=_a[i];
        solve(d,mid-1,l,r,L,tl-1);
        solve(mid+1,u,l,r,tr+1,R);
    }
}
void work()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
            r[(i-1)*m+j]=read();
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
            c[(i-1)*m+j]=read();
    Q=read();
    for(int i=1;i<=Q;i++) 
    {
        a[i].x=read();a[i].y=read();
        a[i].xx=read();a[i].yy=read();
        a[i].id=i;ans[i]=2147483647;
    }
    solve(1,n,1,m,1,Q);
    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}
int main()
{
    n=read();m=read();
    work();
}

T3 小星星

树形dp+容斥

令f[i][j]表示树上的i和i的子树已经匹配好,i和图中的j匹配的方案数。
f[i][k]能用f[son[i][t]转移的条件就是图中k和t有边,然后乘一乘加一加就好了。
但是这样会算重,有些点被匹配了多次。
于是我们容斥一下就行了。ans=最多用了任意n个点的方案-最多用了任意n-1个点的方案+用了任意n-2个点的方案……
%llx考试的时候现场a了这题~

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
ll f[17][17];
int num[1<<17];
int use[17],top;
int mp[17][17];
int h[17],tp=1;
struct edge{int to,next,val;}e[40];
void ae(int u,int v){e[++tp].to=v;e[tp].next=h[u];h[u]=tp;}
ll ans;
void dfs(int u,int fa)
{
    ll ret;
    for(int i=0;i<top;i++) f[u][i]=1;
    for(int v,i=h[u];i;i=e[i].next)
    if((v=e[i].to)!=fa) 
    {
        dfs(v,u);
        for(int i=0;i<top;i++)
        {
            ret=0;
            for(int j=0;j<top;j++) 
            if(mp[use[i]][use[j]])
                ret+=f[v][j];
            f[u][i]*=ret;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++) 
    {
        scanf("%d%d",&u,&v);
        mp[u-1][v-1]=mp[v-1][u-1]=1;
    }
    for(int u,v,i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u-1,v-1);ae(v-1,u-1);
    }
    for(int i=1;i<(1<<n);i++) 
    {
        num[i]=num[i-(i&(-i))]+1;top=0;
        for(int j=0;j<n;j++) if(i>>j&1) use[top++]=j;
        dfs(0,0);
        for(int j=0;j<top;j++) 
        {
            if((n-num[i])&1) ans-=f[0][j];
            else ans+=f[0][j];
        }
    }
    printf("%lld\n",ans);
}