ZJT's Blog

大変に気分がいい~

[自选题 #136] trip

2018-1-4 20:592018-1-4 21:0
集训队作业自选题树形DP概率与期望

传送门

比较水的树形DP,可以直接统计出一条边走过去之后还能走回来的概率。然后把问题转化成求每个点被经过的概率,以及期望的经过次数就行了。这两个都很好DP。

#include <bits/stdc++.h>
#define MAXN 1000010
#define LL long long

const LL P=998244353;

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

int n;
int c[MAXN],d[MAXN];
int g[MAXN],nume;
LL w1[MAXN],w2[MAXN],w3[MAXN];
LL sw2[MAXN];
LL inv_v[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

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

void dfs(int x,int p){
    LL temp=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            dfs(e[i].to,x);
            temp=(temp+w1[e[i].to]);
        }
    w3[x]=temp;
    if(p){
        if(d[x]==1) return;
        temp=temp*inv_v[d[x]]%P;
        w1[x]=getPow(1-temp,P-2)*inv_v[d[x]]%P;
    }
}

void dfs2(int x,int p){
    LL temp=p?w2[x]:0;
    w3[x]=(w3[x]+w2[x])*inv_v[d[x]]%P;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p)
            temp=(temp+w1[e[i].to])%P;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            LL temp2=(temp-w1[e[i].to])*inv_v[d[x]]%P;
            w2[e[i].to]=getPow(1-temp2,P-2)*inv_v[d[x]]%P;
            sw2[e[i].to]=sw2[x]*w2[e[i].to]%P;
            dfs2(e[i].to,x);
        }
}

int main(){
#ifdef DEBUG
    freopen("136.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    inv_v[1]=1;
    for(int i=2;i<MAXN;i++) inv_v[i]=inv_v[P%i]*(P-P/i)%P;
    scanf("%d",&n);
    static char str[MAXN];
    scanf("%s",str+1);
    for(int i=1;i<=n;i++) c[i]=str[i]=='1';
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
        d[u]++; d[v]++;
    }
    dfs(1,0);
    sw2[1]=1;
    dfs2(1,0);
    LL ans=0;
    for(int i=1;i<=n;i++)
        if(c[i]==0 || d[i]==1){
            ans=(ans+sw2[i])%P;
        }else{
            LL temp=getPow(1-w3[i],P-2);
            temp=temp%P*sw2[i]%P;
            ans=(ans+temp)%P;
        }
    ans=(ans%P+P)%P;
    printf("%lld\n",ans);
}

查看详细内容

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

查看详细内容

集训队作业之AGC009-B

2017-12-11 20:482017-12-11 20:48
集训队作业AtCoder树形DP

传送门

树形DP,对于每个点,我们按照DP值从大到小来依次跟他儿子打,这样就一定最优啦。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAXN 100010
using namespace std;

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 d[MAXN];
int ans;

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

void dfs(int x){
    for(int i=g[x];~i;i=e[i].next) dfs(e[i].to);
    static vector<int> S;
    S.clear();
    for(int i=g[x];~i;i=e[i].next) S.push_back(d[e[i].to]);
    sort(S.begin(),S.end());
    int len=S.size();
    for(int i=0;i<len;i++)
        if(S[i]+len-i>d[x]) d[x]=S[i]+len-i;
}

int main(){
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        int t;
        scanf("%d",&t);
        addEdge(t,i);
    }
    dfs(1);
    printf("%d\n",d[1]);
}

查看详细内容

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

查看详细内容

集训队作业之ARC083-E

2017-11-2 11:422017-11-2 11:42
集训队作业AtCoder背包DP树形DP

传送门

显然在一种颜色权值和确定的情况下,另一种的权值和要尽可能小才最优。所以直接DP一下,$f_i$表示$i$的子树里面和$i$颜色不同的权值和最小是多少,转移的时候直接背包一下就行了。如果哪一步背包装不下了,就可以直接判无解了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1010
#define MAXM 5010
using namespace std;

int n;
int p[MAXN],a[MAXN],b[MAXN],f[MAXN][MAXM];

bool gao(int x){
    int temp=-1;
    for(int i=0;i<=a[x];i++)
        if(f[x][i]!=-1) temp=min((temp==-1)?0x7FFFFFFF:temp,f[x][i]);
    if(temp==-1) return 0;
    b[x]=temp;
    return 1;
}

void trans(int x){
    int y=p[x];
    for(int i=a[y];i>=0;i--){
        int temp=-1;
        if(i>=a[x] && f[y][i-a[x]]!=-1) temp=min((temp==-1)?0x7FFFFFFF:temp,f[y][i-a[x]]+b[x]);
        if(i>=b[x] && f[y][i-b[x]]!=-1) temp=min((temp==-1)?0x7FFFFFFF:temp,f[y][i-b[x]]+a[x]);
        f[y][i]=temp;
    }
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d",p+i);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=n;i>=1;i--){
        if(!gao(i)){
            puts("IMPOSSIBLE");
            return 0;
        }
        if(i>1) trans(i);
    }
    puts("POSSIBLE");
    return 0;
}

查看详细内容