ZJT's Blog

大変に気分がいい~

集训队作业之AGC016-E

2017-11-27 13:212017-11-27 13:21
集训队作业AtCoder逆向思维

传送门

我们反过来考虑,如果在一次操作$(x,y)$之后要求$x$存活,则$y$必须在操作前也存活。所以,如果我们要求$u,v$两个点在所有操作之后都存活,我们就从后往前枚举$i$,维护第$i$次操作之前必须存活的点的集合。这样,对于每次操作$(x,y)$,如果$x$和$y$都已经在集合里了,就可以直接说明无解(因为执行完$(x,y)$的操作后$x$和$y$必死一个);如果有一个在集合里,就把另一个加进集合;否则不会产生任何影响,可以无视这次操作。

然而这样搞的时间复杂度是$O(n^2m)$,显然会T。我们考虑某个时刻集合的形态,一定是两棵分别包含$u,v$的树。如果在某一步中,两棵树合成了一棵,就说明肯定无解。所以,对于每个点$x$,我们可以用$O(m)$的时间求出以这个点为初始集合,加完所有边之后的集合。如果加边过程中已经判出了无解,也要标记一下。这样,对于询问$(u,v)$,我们就判一下这两个点分别作为起点时最终的集合又没有交集,没有的话就说明$(u,v)$是可行的。这样,我们的总时间复杂度就是$O(nm+n^3)$,可以通过这道题。

#include <cstdio>
#include <cstring>
#define MAXN 410
#define MAXM 100010

int n,m;
int e[MAXM][2];
bool visit[MAXN],flag[MAXN],a[MAXN][MAXN];

bool gao(int x){
    memset(visit,0,sizeof visit);
    visit[x]=1;
    for(int i=m;i>=1;i--){
        if(visit[e[i][0]] && visit[e[i][1]]) return 0;
        else if(visit[e[i][0]]) visit[e[i][1]]=1;
        else if(visit[e[i][1]]) visit[e[i][0]]=1;
    }
    for(int i=1;i<=n;i++) a[x][i]=visit[i];
    return 1;
}

bool query(int x,int y){
    if(flag[x] || flag[y]) return 0;
    for(int i=1;i<=n;i++)
        if(a[x][i] && a[y][i]) return 0;
    return 1;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&e[i][0],&e[i][1]);
    for(int i=1;i<=n;i++) if(!gao(i)) flag[i]=1;
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(query(i,j)) ans++;
    printf("%d\n",ans);
    return 0;
}

查看详细内容

集训队作业之AGC004-E

2017-10-22 23:582017-11-27 13:21
集训队作业AtCoderDP逆向思维

传送门

考虑把整个过程反过来,就变成了每次加一个点,这个点的范围必须把当前点集整个框起来。注意到当前的状态只跟点集的边界有关,所以关于边界进行DP就行了,复杂度$O(n^4)$。

#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#define MAXN 110
#define MAXS 5100
using namespace std;

int n,m;
int a[MAXN][MAXN],s[MAXN][MAXN],ex,ey;
int px[MAXN][MAXN],py[MAXN][MAXN],numpx,numpy;
int f[MAXS][MAXS];

int getS(int x1,int x2,int y1,int y2){
    return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}

int trans(int x1,int x2,int y1,int y2,int x3,int x4,int y3,int y4){
    int tx1=x2-n+ex,tx2=x1+ex-1;
    int ty1=y2-m+ey,ty2=y1+ey-1;
    if(tx1>x3) x3=tx1;
    if(tx2<x4) x4=tx2;
    if(ty1>y3) y3=ty1;
    if(ty2<y4) y4=ty2;
    if(x3<=x4 && y3<=y4) return getS(x3,x4,y3,y4);
    else return 0;
}

int gao(int x1,int x2,int y1,int y2){
    if(x1==x2 && y1==y2) return a[x1][y1];
    int res=0;
    if(x1<x2){
        res=max(res,f[px[x1][x2-1]][py[y1][y2]]+trans(x1,x2-1,y1,y2,x2,x2,y1,y2));
        res=max(res,f[px[x1+1][x2]][py[y1][y2]]+trans(x1+1,x2,y1,y2,x1,x1,y1,y2));
    }
    if(y1<y2){
        res=max(res,f[px[x1][x2]][py[y1][y2-1]]+trans(x1,x2,y1,y2-1,x1,x2,y2,y2));
        res=max(res,f[px[x1][x2]][py[y1+1][y2]]+trans(x1,x2,y1+1,y2,x1,x2,y1,y1));
    }
    return res;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++)
            if(str[j]=='o'){
                a[i][j]=1;
            }else if(str[j]=='E'){
                ex=i;
                ey=j;
            }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            px[i][j]=++numpx;
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
            py[i][j]=++numpy;
    for(int w=1;w<=n;w++)
        for(int h=1;h<=m;h++)
            for(int i=1;i+w-1<=n;i++)
                for(int j=1;j+h-1<=m;j++)
                    f[px[i][i+w-1]][py[j][j+h-1]]=gao(i,i+w-1,j,j+h-1);
    printf("%d\n",f[px[1][n]][py[1][m]]);
    return 0;
}

查看详细内容