ZJT's Blog

Keep your determination.

集训队作业之AGC017-F

2017-11-27 18:472017-11-27 18:49
集训队作业AtCoder状压DP

传送门

想了半天还是卡在$O(n^32^n)$的复杂度。。。然后不知道怎么就突然发现可以省掉一维了(奥妙重重.jpg)。

考虑$L_i\to L_{i+1}$如何转移,我们记$d_{i,j}$为$L_i$中第$j$步的方向,则$d_{i+1}$的每个前缀和都必须大于等于$d_i$的前缀和。直接根据这个DP是$O(n^32^n)$的,显然会T,我们需要省掉其中的一维。

通过观察可以发现,$d_i$和$d_{i+1}$之间满足刚才的条件,当且仅当$d_i$可以通过一系列以下两种操作来得到$d_{i+1}$:

  1. 把$d_i$的二进制位中的某个1往左移。
  2. 把$d_i$的二进制位中的某个0设为1。

我们从低到高逐位考虑,设当前决策到第$j$位,如果我们要把第$j$位从0变成1,就可以把后面的第一个1往左移动到第$j$位(如果后面没有1就直接添一个1);剩下的情况除了1不能变成0以外,都可以直接转移。

这样,我们的DP维数就少了一维(不用记前缀和),复杂度是$O(n^22^n)$,可以直接通过这道题。

一次过样例+AC,爽到

#include <cstdio>
#include <cstring>
#define MAXN 30
#define MAXS 1050000

const int P=1000000007;

int n,m,q,maxs;
int f[2][MAXS];
int limit[MAXN][MAXN];
int trans[MAXN][MAXS];

void init(){
    for(int i=0;i<n;i++){
        int mask=(maxs-1)^((1<<i)-1);
        for(int j=0;j<maxs;j++){
            int j2=j&mask;
            trans[i][j]=(j^(j2&(-j2)))|(1<<i);
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    n--;
    maxs=1<<n;
    init();
    memset(limit,-1,sizeof limit);
    while(q--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        limit[u][v-1]=w;
    }
    int now=0;
    f[0][0]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<n;j++){
            int l=1<<j;
            int nxt=now^1;
            memset(f[nxt],0,sizeof f[nxt]);
            if(limit[i][j]!=1){
                for(int k=0;k<maxs;k++)
                    if(!(k&l))
                        f[nxt][k]=f[now][k];
            }
            if(limit[i][j]!=0){
                for(int k=0;k<maxs;k++)
                    f[nxt][trans[j][k]]=(f[nxt][trans[j][k]]+f[now][k])%P;
            }
            now=nxt;
        }
    }
    int ans=0;
    for(int i=0;i<maxs;i++)
        ans=(ans+f[now][i])%P;
    printf("%d\n",ans);
}

查看详细内容

集训队作业之AGC016-F

2017-11-5 9:182017-11-5 9:18
集训队作业AtCoder状压DP博弈论

传送门

瞎写了一个$O(3^nn^2)$的鬼畜做法,神tm5s差点T了。。。

这题显然要状压DP,大概就是分层决策SG函数,先确定SG值为0的点,然后是1的点,最后把所有点的SG值都决策了。需要预处理层之间的转移,我大概就是这里的常数大了。。。

然后看了题解,神tm还有bell数的做法。。。

#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 20
#define MAXS 33000
#define LL long long
using namespace std;

const LL P=1000000007;

int n,m,maxs;
int w[MAXN][MAXN];
LL f[MAXN][MAXS];
vector< pair<int,LL> > trans[MAXS];
LL g[MAXS],p2[MAXS];

void pre_gao(int x){
    for(int y=x;;y=(y-1)&x){
        LL res=1;
        int cnt=0;
        for(int i=1;i<=n;i++)
            if((1<<(i-1))&y){
                int temp=0;
                for(int j=i+1;j<=n;j++)
                    if(((1<<(j-1))&x) && !((1<<(j-1))&y) && w[i][j])
                        temp++;
                res=res*((1LL<<temp)-1)%P;
            }else if((1<<(i-1))&x){
                for(int j=i+1;j<=n;j++)
                    if(((1<<(j-1))&y) && w[i][j])
                        cnt++;
            }
        res=res*p2[cnt]%P;
        if(res) trans[x].push_back(make_pair(y,res));
        if(!y) break;
    }
    int temp=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(w[i][j] && ((1<<(i-1))&x) && ((1<<(j-1))&x))
                temp++;
    g[x]=1;
    while(temp--) g[x]=g[x]*2%P;
}

inline void update(LL &x,LL y){ x=(x+y)%P; }

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    p2[0]=1;
    for(int i=1;i<MAXS;i++) p2[i]=p2[i-1]*2%P;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        w[x][y]=1;
    }
    maxs=1<<n;
    for(int i=0;i<maxs;i++) pre_gao(i);
    f[0][maxs-1]=1;
    LL ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<maxs;j++)
            if(f[i][j]){
                for(int k=0;k<trans[j].size();k++)
                    if((trans[j][k].first&3)==3)
                        update(f[i+1][trans[j][k].first],f[i][j]*trans[j][k].second);
                    else if((trans[j][k].first&3)==0)
                        update(ans,f[i][j]*trans[j][k].second%P*g[trans[j][k].first]);
            }
    LL temp=1;
    for(int i=1;i<=m;i++) temp=temp*2%P;
    ans=(temp-ans+P)%P;
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之ARC078-F

2017-10-19 9:62017-10-19 9:6
集训队作业AtCoder状压DP

传送门

比较烦人的状压题。。。不过猜日语题面倒是挺好玩的233

大概就是如果只有一条路径,考虑这条路径中的不相邻的两个点,肯定不能存在别的路径(即包含不在这条路径上的边)把他们连起来。所以,就可以把原图中的点集划成一个块的序列,每个块内可以随便连边,然后在序列中相邻的两个块之间可以连一条边,但是一个块往相邻两个块连边的点肯定是同一个点。然后随便状压一下就能dp了。

这样搞的复杂度(算上状压的常数)应该是$O(3^{n-2}n^2)$,我觉得可能会T就强行优化成了$O(3^{n-4}n^2)$,导致非常难写,结果跑出来才不到100ms(时限4s)。。。也就是说根本就不用优化??

#include <cstdio>
#include <cstring>
#define MAXN 20
#define MAXS 40000

int n,m,maxs;
int g[MAXS],f[MAXS][MAXN];
int e[MAXN][MAXN];

inline void update(int &x,int y){ x=x>y?x:y; }

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    int totw=0;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[v][u]=e[u][v]=w;
        totw+=w;
    }
    maxs=1<<n;
    for(int i=0;i<maxs;i++){
        for(int j=1;j<=n;j++)
            if(i&(1<<(j-1)))
                for(int k=j+1;k<=n;k++)
                    if(i&(1<<(k-1)))
                        g[i]+=e[j][k];
    }
    int maxs0=maxs;
    maxs>>=2;
    memset(f,0x88,sizeof f);
    for(int i=0;i<maxs;i++) f[i][1]=g[i<<1|1];
    for(int i=0;i<maxs;i++)
        for(int x=1;x<n;x++){
            if(x!=1 && !(i&(1<<(x-2)))) continue;
            for(int y=2;y<n;y++){
                if((i&(1<<(y-2))) || !e[x][y]) continue;
                int by=1<<(y-2);
                int lims=(maxs-1)^i^by;
                for(int j=lims;;j=(j-1)&lims){
                    update(f[i|j|by][y],f[i][x]+e[x][y]+g[(j|by)<<1]);
                    if(!j) break;
                }
            }
        }
    int ans=-1;
    for(int i=0;i<maxs;i++)
        for(int j=1;j<n;j++)
            if(j==1 || (i&(1<<(j-2)))){
                if(e[j][n])
                    update(ans,f[i][j]+e[j][n]+g[(maxs0-1)^1^(i<<1)]);
            }
    ans=totw-ans;
    if(ans<=totw) printf("%d\n",ans);
    else puts("zjtsb");
}

查看详细内容

集训队作业之AGC012-E

2017-9-24 9:152017-9-26 13:45
AtCoder集训队作业状压DP

传送门

一看到这题就想到转树的模型,然后就想到树上搞dp,发现好像要状压,结果仔细想想我的复杂度可以卡到$O(n^2)$。。

然后又想了一会儿还是不会做,就去看了题解。结果题解根本用不到跟建树有关的任何东西。。。

这题其实就是把序列看成有$L=\lceil log_2n\rceil$层,把每次跳跃看成从上一层跳到下一层。由于每一层只要相邻距离不超过该层的规定值,就可以到处乱走,那么我们可以直接用这个阈值去把这一层所有点分成若干个区间,其中每个区间内部都可以互相瞎走。

题目要问我们能不能从一个点开始走完所有点,我们考虑第0层(也就是直接拿$V$划分)中该点所在的区间内的所有点都是显然可达的,而其他的点则需要通过跳跃来到达。这其实等价问是否能在每层选一个区间,让所有的区间的并覆盖住每个点。

由于第0层的区间已经确定了,我们只需要考虑跳跃至少一次后的决策即可。设第0层的区间为$[l_0,r_0]$,我们需要用剩下的$L-1$个区间去覆盖$[1,l_0-1]\cup[r_0+1,r]$。这时,这些区间中有一部分覆盖住了$[1,l_0-1]$,而剩下的覆盖住了$[r_0+1,r]$。由于$L=O(log(n))$,所以我们直接对这些层进行状压dp就行了。

设$f_1[s]$($s$为一个二进制状态,表示哪些层已经被用过了,注意这里不包含第0层)表示已经用了$s$中的层时,所能覆盖住的最长前缀。这个dp的转移很简单,直接枚举覆盖住的前缀中最后一段是由哪一层覆盖的就行了。同理还可以dp出$f_2[s]$表示能覆盖住的最长后缀。这样我们就可以通过$f_1[s]$和$f_2[(2^{L-1}-1)-s]$来判断这种选法能不能覆盖$[1,l_0-1]\cup[r_0+1,r]$。

最后发现答案的统计可以转化成二维平面上的一个判断区域内点是否存在的问题,发现可以离线后$O(n)$处理。这样就在总复杂度$O(nlogn)+O(n)=O(nlog(n))$解决了这道题。

顺便吐槽一下这题的官方数据。。。好多人的做法都是能卡到$O(n^2)$还在官网上A掉了的(比如这个提交)。。我在本地随手构造一个数据就把他们卡了。。。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 200010
#define MAXS 1000010
using namespace std;

int read(){
    char c;
    while(((c=getchar())<'0' || c>'9') && c!='-');
    int flag=1;
    int res=c-'0';
    if(c=='-'){
        flag=-1;
        res=0;
    }
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res*flag;
}

int n,m,v0,maxs;
int a[MAXN];
int lim[MAXN];
int f1[MAXS],f2[MAXS];
int p[20][MAXN][2];
int c[MAXN];

void calcP(int l){
    int last=1;
    for(int i=1;i<=n;i++){
        if(i==n || a[i+1]-a[i]>lim[l]){
            for(int j=last;j<=i;j++){
                p[l][j][0]=last;
                p[l][j][1]=i;
            }
            last=i+1;
        }
    }
    p[l][0][0]=1;
    p[l][n+1][1]=n;
}

void dp(){
    f1[0]=0; f2[0]=n+1;
    for(int s=1;s<maxs;s++){
        f2[s]=n+1;
        for(int i=1,l=1;i<=m;i++,l<<=1)
            if(s&l){
                f1[s]=max(f1[s],p[i][f1[s^l]+1][1]);
                f2[s]=min(f2[s],p[i][f2[s^l]-1][0]);
            }
    }
}

int main(){
#ifdef DEBUG
    freopen("g012e.in","r",stdin);
#endif
    n=read(); v0=read();
    for(int i=1;i<=n;i++) a[i]=read();
    lim[0]=v0;
    while(v0) lim[++m]=(v0/=2);
    maxs=1<<m;
    for(int i=0;i<=m;i++) calcP(i);
    dp();
    memset(c,-1,sizeof c);
    for(int i=0;i<maxs;i++)
        c[f2[i]]=max(c[f2[i]],f1[(maxs-1)^i]);
    int cur=-1,now=-1;
    for(int i=1;i<=n;i++)
        if(p[0][i][0]==i){
            while(cur<p[0][i][1]+1) now=max(now,c[++cur]);
            if(now>=i-1)
                for(int j=p[0][i][0];j<=p[0][i][1];j++)
                    puts("Possible");
            else
                for(int j=p[0][i][0];j<=p[0][i][1];j++)
                    puts("Impossible");
        }
    return 0;
}

查看详细内容