Codeforces Beta Round #69 (Div. 1 Only) 【E题还是不会】

【A. Heroes】

就是一个DFS枚举，然后模拟。

最坏时间3^7 * 7^2

 

【B. Falling Anvils】

【题目大意】

给定一个方程。然后p的范围是[0,a]，q的范围是[-b,b]。

p,q在各自区间上等概率分布。

问这个方程有解的概率。

【算法分析】

就是求p-4q>=0的概率。

然后把p看成x，q看成y。然后画出对应的平面图形分类讨论一下即可。高中数学课本的例题阿

代码就这样

        if (fabs(b)<1e-9) ret=1;

        else

        if (a

            ret=(2*b+a/4)/(4*b);

        }

        else{

            ret=1-b/a;

        }

注意b=0的情况。被坑了一次。

 

 

【C. Beavermuncher-0xFF】

【题目大意】

给定一棵有根树，每个点上有w[i]只鱼(其实题目是海狸= =)，一开始你在根上。你每走一条边x->y，那么y上要少一条鱼。如果y上没鱼，那么不能走边x->y。现在要求你结束时依然需要站在根处，问你最多能干掉多少条鱼(即最多能走多少步)。

n<=10^5

【算法分析】

首先很容易发现我们可以把走出去的路线分解为很多圈圈，每个圈圈只包含两个点。

于是我们可通过点来划分路径。

考虑一棵以p为根的子树

我们可以以p为分界点把路径分隔开。

那么p下面怎么走和上面无关，只要剩下一条鱼在p上，就足够把p这个子树拼接到fa上。

我们考虑p上的鱼消失的两种方式。

A、从儿子走回来

B、从fa走下来

如果能选A，我们肯定尽量选A。因为如果选了B，那么必须要走回fa那儿去，那么就要同时消耗fa上鱼的数目，这就会影响以后的决策，使得后面取得的鱼变少。

于是这个贪心算法就很显然了。令F[i]表示以i为根，绕一圈回到i最多能吃到多少鱼。(如果i不为根，那么要求最后i上剩的鱼>=1，否则>=0)。

然后每次将自己的儿子按F[i]排个序。然后拼接就好了。

如果拼接完还有在i上的鱼多出来，那么就找个儿子卡能不能抵消。最后输出F[i]即可。

附代码

#include

#include

#include

#include

#include

using namespace std;

const int N=100005;

const int oo=0x80000000;

int n,S;

int w[N];

int fa[N];

int Q[N];

long long F[N];

vector

 

void bfs(){

    int head=0,tail=1;

    Q[1]=S;

    fa[S]=0;

    while (head!=tail){

        head++;

        int x=Q[head];

        int L=G[x].size();

        for (int i=0;i

            int y=G[x][i];

            if (fa[x]!=y){

                fa[y]=x;

                Q[++tail]=y;

            }

        }

    }

}

 

bool cmp(int i,int j){

    return F[i]>F[j];

}

 

void solve(){

    for (int i=1;i<=n;i++) F[i]=oo;

    for (int j=n;j>=1;j–){

        int low_limit= (j==1) ? 0 : 1;

        int x=Q[j];

        int L=G[x].size();

        F[x]=0;

        sort(G[x].begin(),G[x].end(),cmp);

        for (int i=0;i

            int y=G[x][i];

            if (fa[x]!=y){

                if (w[x]>low_limit && w[y]>0){

                    F[x]+=F[y]+2;

                    w[x]–;

                    w[y]–;

                }

            }

        }

        for (int i=0;i

            int y=G[x][i];

            if (fa[x]!=y){

                if (w[x]>low_limit && w[y]>0){

                    int delta=min(w[x]-low_limit,w[y]);

                    F[x]+=delta*2;

                    w[x]-=delta;

                    w[y]-=delta;

                }

            }

        }

    }

    cout << F[S] << endl;

}

 

int main(){

    freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%d",&w[i]);

    for (int x,y,i=1;i

        scanf("%d%d",&x,&y);

        G[x].push_back(y);

        G[y].push_back(x);

    }

    scanf("%d",&S);

    bfs();

    solve();

}

 

【D. Domino Carpet】

【题目大意】

经过一些人肉转换以后，题目变成了m*n个格子，这些格子有3种类型。

1、只允许被2*1的方块覆盖的。

2、只允许被1*2的方块覆盖的。

3、允许被1*2或2*1的方块覆盖的。

然后用2*1或者1*2的格子去完美覆盖这些格子。问有多少种方案。

n,m<=250

还有一个重要条件，假如放了一块1*2的方块占在(i,j)和(i,j+1)，那么就不能存在其它的1*2方块放在(k,j-1)(k,j)或(k,j+1)(k,j+2)。

【算法分析】

由于那个重要条件，我们可以一列一列地dp转移。

要么直接整列竖的2*1方块。要么就是存在1*2方块的两列。

第一种很好算直接F[j+1]+=F[j]。

第二种可以在里面套一个dp。G[i][0]表示到达第i行，还没有放过1*2的方块，这时候的方案数。G[i][1]就是放过2*1的方块的方案数了。

然后F[j+2]+=G[m][1]*F[j]。

 

【E. Martian Food】

= =，算了10页草稿纸发现算不出来。唉，太弱小了。不会捉。

 

 

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

比赛时前3题都是迅速反应出算法，但是第3题写的时候，头脑有点混，悲剧写挂了。今天重打一遍不到10分钟就1Y了

然后就前两题那个沙茶分数排到了DIV I 150+。居然还涨rating了