Codeforces Round #384 (Div. 2) ABCD

一场比较简单的div2 电脑出了点问题所以在比赛中理论ac了ACD 除了爆int这种事情之外..

A 一个人想从a到b 移动的花费这么定义如果初始点和到达点类型相同就不花钱反之花距离差的绝对值的钱并且是直接移动

判断ab的类型一样就输出0 反之1 因为如果不能直接零花费到b的话就花1花费走到一个和b类型相同的点然后零花费移动

B 给出一个串的增长规律问经过n-1次操作后 k位是多少

规律是这样的一开始只有1 进行一次操作就把当前串复制一遍粘在后面然后在这两个相同串之间插入一个当前没有使用过的最小数字

1 -> 121 -> 1213121 -> 121312141213121 这样

这个串是很对称的如果k处于当前串的中间我们可以很容易的确定他是多少

如果处于当前中点的右边即k处在复制粘贴来的串上就减去一个东西让他平移到原串上

如果处于当前中点的左边就不做修改

k最后一定会在当前串的中间的

持续让一个很长的串进行长度减半直到k处在当前串中点

C 给出一个n 求出abc 使 2/n = 1/a + 1/b + 1/c 且 a != b a !=c b != c

样例很明确...其实就是a = n b = n+1 c = a*b 可以证明满足一切

唯独满足不了n = 1 因为在没有相同数字的前提下 1/1 + 1/2 + 1/3 无法达到2 别的一定小于它

于是特判n = 1

D 给出一棵树找两个点获得他们的子树权值和并且这两个点的子树没有交集点有点权以1为根

树形dp

如果从一个点的所有子树中选出来两个最大的一定是合法(不相交)的

答案就是根的子树的最大值和次大值的加和

维护的办法是维护每个点的最大子树值和选两个子树的加和的最大值

这个点的最大子树值很好求不断递归就好了

两个子树的加和的最大值可以直接从每个子树的加和最大值继承来

也可能是这个点每个儿子节点的最大子树选出来最大值与次大值相加

最后如果根节点的最大值+次大值不存在那就是没法选出来两个不相交子树

虽然写的代码是爆int的..

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<map>

#include<vector>

#include<queue>

#include<malloc.h>

using namespace std;

#define L long long

vector<int >q[200050];

int n ;

L a[200050];

L b[200050];

L dfs1(int fa ,int u){

    b[u] = a[u];

    for(int i = 0;i<q[u].size();i++){

        int v = q[u][i];

        if(v == fa)continue;

        b[u] += dfs1(u,v);

    }

    return b[u];

}

L dp[200050][3];

void dfs(int fa,int u){

    dp[u][0] = b[u];

    dp[u][1] = -9999999999;

    dp[u][2] = b[u];

    L maxx = -9999999999;

    L maxx2 = -9999999999;

    for(int i=0;i<q[u].size();i++){

        int v = q[u][i];

        if(v == fa)continue;

        dfs(u,v);

        dp[u][2] = max(dp[u][2],dp[v][2]);

        if(dp[v][2]!= -9999999999){

            if(maxx == -9999999999){

                maxx = dp[v][2];

            }

            else {

                if(dp[v][2] > maxx){

                    maxx2 = maxx;

                    maxx = dp[v][2];

                }

                else {

                    if(maxx2 == -9999999999 || dp[v][2] > maxx2){

                        maxx2 = dp[v][2];

                    }

                }

            }

        }

    }

    if(maxx2!= -9999999999){

        dp[u][1] = maxx2 + maxx;

    }

    for(int i =0;i<q[u].size();i++){

        int v = q[u][i];

        if(v == fa)continue;

        dp[u][1] = max(dp[u][1] , dp[v][1]);

    }

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld",&a[i]);

        q[i].clear();

    }

    for(int i=1;i<n;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        q[u].push_back(v);

        q[v].push_back(u);

    }

    dfs1(-1,1);

    dfs(-1,1);

    if(dp[1][1]!= -9999999999)printf("%lld\n",dp[1][1]);

    else printf("Impossible\n");

}

巴特西

Codeforces Round #384 (Div. 2) ABCD

最新文章

热门文章