ZJT's Blog

大変に気分がいい~

集训队作业之AGC017-D

2017-12-16 7:582017-12-16 7:58
集训队作业AtCoder博弈论树形DP

传送门

裸的树上删边游戏,直接按$f_x=(f_{y_1}+1)\oplus(f_{y_2}+1)\oplus\cdots$来DP就行了。其中$y_1,y_2,\cdots$是$x$的所有儿子。加一的原因是在原来每个状态后面都接了一个终止态。

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

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int g[MAXN],nume;
int f[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dfs(e[i].to,x);
            f[x]^=f[e[i].to]+1;
        }
}

int main(){
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1,0);
    if(f[1]) puts("Alice");
    else puts("Bob");
}

查看详细内容

集训队作业之AGC010-F

2017-11-22 19:132017-11-22 19:13
集训队作业AtCoder博弈论树形DP

传送门

现在都流行把$O(n)$的题出到几百几千的吗。。。又是看了范围不敢写。。。

显然一个点往权值大于等于他的另一个点走是没有意义的,因为对方可以再走回来。所以就只能往权值更小的点走了,随便按点权排个序之后DP一下之后就可以$O(n)$做了。

不知道这题出现在AGC的F是怎么回事。。。我感觉这题放到C也不会奇怪啊。。。

因为基排麻烦,就干脆写了个$O(n^2)$的DP,省了排序,直接枚举起点DP。结果跑得比别人的$O(n)$还快。。。

#include <cstdio>
#include <cstring>
#define MAXN 3010

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int a[MAXN];
int g[MAXN],nume;

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

bool dfs(int x,int p){
    for(int i=g[x];~i;i=e[i].next)
        if(a[x]>a[e[i].to])
            if(!dfs(e[i].to,x)) return 1;
    return 0;
}

int main(){
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    for(int i=1;i<=n;i++)
        if(dfs(i,0)) printf("%d ",i);
    return 0;
}

查看详细内容

集训队作业之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);
}

查看详细内容

集训队作业之AGC010-D

2017-11-2 11:222017-11-2 11:22
集训队作业AtCoder博弈论

传送门

被一个D题虐了,持续智障了一上午。。。期间各种打表,找规律,最后终于找到了$N$为偶数时的规律。。。然而并没有什么x用。一直在想除以偶数的情况怎么办,并没有发现这种情况直接暴力无脑递归下去算就行了。。。

考虑每次除以gcd前,如果存在奇数,那么除完之后所有数的奇偶性是不变的。如果场上有偶数个偶数,且存在至少两个奇数,这时先手不管怎么走,除掉的gcd一定都是奇数。所以他走一步之后,偶数的奇偶性一定会改变,这时后手再减掉一个偶数,就又变回去之前的局面了。所以这时先手一定必败。同理,当存在奇数个偶数时,先手可以减掉一个偶数,就会让后手面临刚才那个必败的局面了。

这时还有一种情况没有考虑,就是存在偶数个偶数,且只剩下1个奇数了(不可能全是偶数,因为保证了所有数gcd为1)。我做的时候一直在找这种情况的性质和各种规律,然而并没有找到。其实根本什么性质都不用,直接暴力除掉gcd之后递归下去算就行了,因为最多除$O(\log a_i)$次,所以复杂度是对的。。。感觉智商已经差不多流失完了。。。

#include <cstdio>
#define MAXN 100010
#define LL long long

int n;
int a[MAXN];

int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}

bool gao(){
    int c0=0,p1;
    for(int i=1;i<=n;i++)
        if(a[i]&1) p1=i;
        else c0++;
    if(c0&1) return 1;
    if(n-c0>1) return 0;
    int g=0;
    for(int i=1;i<=n;i++)
        if(a[i]&1){
            if(a[i]==1) return 0;
            g=gcd(g,a[i]-1);
        }else g=gcd(g,a[i]);
    for(int i=1;i<=n;i++) a[i]/=g;
    return !gao();
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    if(gao()) puts("First");
    else puts("Second");
}

查看详细内容

集训队作业之AGC014-D

2017-10-11 8:422017-10-11 18:4
集训队作业AtCoder博弈论树形DP

传送门

这场原来是yutaka出的。。。太强了orz

这个题有两个做法,一个是我的智障做法,一个是正解的巧妙做法。先讲我的乱搞DP做法,考虑一棵树$T$,记$f(T)$为$T$这棵树中先手是否必胜。考虑一个点$x$删掉之后,其实相当于对于$x$的每个儿子,从$x$这个方向就不会对子树造成影响了(即不会因为$x$被染成黑色而影响子树内的博弈)。有个结论就是任何一棵树,只要黑色方先手,则黑色方必胜。这个结论其实我也没怎么证他,感觉他是对的吧。因此,$f(T)=1$当且仅当存在存在一个$x\in T$,使得把$x$删掉后,剩下的子树中至少有两个是先手必胜的。因为如果只有一个子树先手必胜,黑色方直接在这个子树里面走一步,则每个子树都是黑色方必胜了。

考虑以1为根的有根树中,记$f(x)$为以$x$为根的子树$S_x$的$f(S_x)$。$f(x)=1$的条件要么是删掉$x$后至少两棵子树先手必胜,要么是每次在子树中找一个至少一个儿子先手必胜的点,并把这个点为根的子树删掉,最终能删得只剩$x$一个点。所以除了$f(x)$以外,我们还要dp一个$g(x)$代表以$x$为根的子树能不能通过每次删掉一个至少一个儿子先手必胜的点,把整棵子树删完。经过推导发现$g(x)=1$其实就等价于$x$有至少一个子树先手必胜。这样经过两个树形DP,就能得出答案了。

题解的做法则巧妙的多。可以证明,黑色方必胜当且仅当这棵树存在完美匹配。因为如果存在完美匹配,白色方每走一个点,黑色方走他的匹配点,就能最终取胜。否则,白色方每次随便找个叶子,选他的父亲走,下一步黑色方只能走这个叶子(不然白色方再把这个叶子选掉就赢了)。如果除了这两个点以外的点存在完美匹配,那么再把这两个点匹配上,整棵树就存在完美匹配,这就矛盾了,所以剩下的点也不存在完美匹配。这就可以归纳了,最终的情况只可能是一堆孤立点,白色方随便选一个走就赢了。

代码(我的乱搞DP):

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

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int g[MAXN],nume;
int f[MAXN],h[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x,int p){
    int c0=0,cf=0,cg=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            c0++;
            dfs(e[i].to,x);
            if(f[e[i].to]) cf++;
            if(h[e[i].to]) cg++;
        }
    if(cf>=2 || cg==c0) f[x]=1;
    if(cf>=1) h[x]=1;
}

int main(){
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1,0);
    if(f[1]) puts("First");
    else puts("Second");
    return 0;
}

查看详细内容