8月12日 2018百度之星初赛 (B)
题目链接:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=826

1001 – degree

思路:
一道比较简单的结论题吧。。。我们贪心地找出一个度数最多的点,当不考虑K时,我们可以将其他的联通块都接在这个点上。当我们考虑K时,我们就可以从联通块上拆下K个点,再接到度数最多的点上,注意一下有没有K个点够拆就好了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
using namespace std;

int T, n, m, k, deg[200005];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int maxd=0;
        memset(deg, 0, sizeof(deg));
        scanf("%d%d%d", &n, &m, &k);
        for(int i=1; i<=m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            deg[x]++, deg[y]++;
            maxd=max(maxd, max(deg[x], deg[y]));
        }
        if(k>m-maxd) printf("%d\n", n-1);
        else printf("%d\n", n-m+maxd+k-1);
    }
}

1003 – odds

思路:
特别好的一道题吧。。。

我们可以把每个叶子节点到根的路径提出来,这样问题可以简化为:一个路径上有K条边,分别有权值$x_1, y_1, x_2, y_2····x_k,y_k$,其中$y_i>=x_i$的。你需要从中选$x$条边取$y_i$,其余边取$x_i$,使这些的乘积最大。根据题目要求,求这个的复杂度应该要在$O(nlogn)$以内的。

于是我们可以想到一个贪心的方法,对于这$K$条边,我们选其中$y_i*x_i$最大的x条边取$y_i$,其余的取$x_i$。证明也很简单:假如已经处理出了前$i-1$条边($i$是应该大于$x$的,否则直接取$y_i$)乘积为$w$。我们考虑第$i$条边:如果第$i$条边取$x_i$,那么乘积为$w*x_i$;如果取$y_i$,那么我们就需要从前$x$条取$y$边中,选出一条边$j$,让它值变为$x_j$,这样乘积就为$w_i*y_i*(x_j/y_j)$。不难看出我们希望乘积尽可能大,那么就需要选$y_i*x_i$尽可能大的边。

有了这个贪心策略后,实现就不难了。用一个multiset动态维护路径上$y_i*x_i$前$x$大的边,同时计算出答案,回溯时要将答案和multiset复原。注意,千万不能对于每一个叶子节点都重新算一遍答案,我比赛时就是这样SB的都算一遍,然后T飞了,比完赛才反应过来。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#define MAXN 200005
#define p 1000000007
#define LL long long
using namespace std;

int T, n, k, cnt, head[MAXN];
LL ans[MAXN], inv[MAXN];

struct Edge {int next, to, dis;} edge[MAXN];
struct Node
{
    LL x, y;
    bool friend operator < (Node a, Node b)
    {
        return a.y*b.x<b.y*a.x;
    }
} node[MAXN];

multiset<Node> st;
multiset<Node>::iterator it;

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void dfs(int x, LL val)
{
    int maxd=-1;
    for(int i=head[x]; i; i=edge[i].next) maxd=max(maxd, edge[i].dis);
    if(maxd==-1) ans[x]=val;
    for(int i=head[x]; i; i=edge[i].next)
    {
        node[i].x=edge[i].dis;
        node[i].y=maxd;
        Node top= *st.begin();
        LL tag=0, temp=val;
        if(st.size()<k)
        {
            tag=1;
            st.insert(node[i]);
            temp=temp*inv[200000]%p*node[i].y%p;
        }
        else if(top<node[i])
        {
            tag=2;
            st.erase(st.begin());
            st.insert(node[i]);
            temp=temp*inv[top.y]%p*top.x%p;
            temp=temp*inv[200000]%p*node[i].y%p;
        }
        else temp=temp*inv[200000]%p*node[i].x%p;
        dfs(edge[i].to, temp);
        if(tag==1)
        {
            it=st.lower_bound(node[i]);
            st.erase(it);
        }
        if(tag==2)
        {
            it=st.lower_bound(node[i]);
            st.erase(it);
            st.insert(top);
        }
    }
}

int main()
{
    inv[0]=inv[1]=1;
    for(int i=2; i<=200000; i++) inv[i]=inv[p%i]*(p-p/i)%p;
    scanf("%d", &T);
    while(T--)
    {
        cnt=0;
        memset(head, 0, sizeof(head));
        memset(ans, -1, sizeof(ans));
        scanf("%d%d", &n, &k);
        for(int i=1; i<n; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            x++, y++;
            addedge(x, y, z);
        }
        dfs(1, 1);
        for(int i=1; i<=n; i++) if(ans[i]!=-1) printf("%lld\n", ans[i]);
    }
}

1004 – p1m2

思路:
二分应该能够很容易的看出来,对于二分值大的就计算一下正的贡献,小于二分值的计算负的贡献,判断正负贡献是否大于0。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
#define LL long long
using namespace std;

int T, n, x[300005], y[300005];

bool check(int mid)
{
    LL res=0;
    memcpy(y, x, sizeof(x));
    for(int i=1; i<=n; i++)
    {
        if(y[i]>mid+1) res+=(y[i]-mid)/2;
        if(y[i]<mid) res-=(mid-y[i]);
    }
    return res>=0;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int ans=0;
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &x[i]);
        int l=0, r=1e8;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid)) ans=mid, l=mid+1;
            else r=mid-1;
        }
        printf("%d\n", ans);
    }
}

1006 – rect

思路:
题目有一句比较重要的话就是$x_i,y_i$彼此不重复,这样的话就直接贪心就好了,到哪条边近就向那条边做垂线,这样线段也一定不会交叉重复。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
#define LL long long
using namespace std;

int T, n, m, k, deg[200005];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int w, h, x, y;
        LL ans=0;
        scanf("%d%d%d", &w, &h, &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &x, &y);
            ans+=min(min(x, y), min(w-x, h-y));
        }
        printf("%lld\n", ans);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注