比赛题解

HZAU 第八届校赛部分题解

C.Friends

题意:
给你一棵树,要你求每个节点在6步以内的结点数量。

思路:
一般看过挑程的都会想到树上点分治。 ~~然而我结束之后才看~~
树上点分治 请移步 poj1741

官方的题解思路是这样的:
f[rt][len] 预处理的节点rt的子孙结点中,距离其长度为 len 的节点个数
ans[rt][len] 整棵树上,距离rt为len的节点个数
f 可以通过一遍简单深搜即可获得
而 ans[rt][len] = f[rt][len] + ans[fa[rt]][len-1] - f[fa[rt]][len-1]

这里必须得指出,官方的题解有错误之处。最后减去的 f[fa[rt]][len-1] 将会减去除开 rt 以外的所有子树,这是不符合题意的。

正确形式应该是 ans[rt][len] = f[rt][len] + ans[fa[rt]][len-1] - f[rt][len-2] (当然这时的len必须大于等于2

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 1e5 + 5;
char str[maxn];
int idx, n;
int head[maxn];
int num[maxn][10];
int ans[maxn][10];
bool vis[maxn];

struct node {
    int to;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void getNum(int pre, int r)
{
    int v;
    if (pre != 0) {
        ans[pre][1]++;
        ans[r][1]++;
    }
    for (int id = head[r]; id != -1; id = edges[id].nxt) {
        v = edges[id].to;
        if (pre != v) {
            getNum(r, v);
            num[r][1]++;
            for (int i = 2; i < 7; i++)
                num[r][i] += (num[v][i - 1] + 1);
        }
    }
}

void getAns(int fa, int r, int len)
{
    int v;
    if (fa != r)
        ans[r][len] = num[r][len] + ans[fa][len - 1] - num[r][len - 2];
    //printf("ans[%d][%d]: %d\n", r, len, ans[r][len]);
    for (int id = head[r]; id != -1; id = edges[id].nxt) {
        v = edges[id].to;
        if (v != fa)
            getAns(r, v, len);
    }
}

void init()
{
    idx = 0;
    memset(num, 0, sizeof num);
    memset(ans, 0, sizeof ans);
    for (int i = 0; i <= n; i++)
        head[i] = -1;
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d", &n);
        init();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        getNum(0, 1);
        for (int i = 1; i < 7; i++)
            ans[1][i] = num[1][i];
        for (int i = 2; i < 7; i++) {
            getAns(1, 1, i);

        }
        printf("Case #%d:\n", cas);
        for (int i = 1; i <= n; i++)
            printf("%d\n", ans[i][6]);
    }
    return 0;
}

E.One Stroke

题意:
给定一棵完全二叉树,每个节点上都有一个权值。要求你连接尽可能多的节点,且权值和不超过给定数值。

思路:
官方说是尺取法。不知道什么算法,之后补一下。

但是!!!!特么居然暴力能过!!!这数据就真的过分了………………

看到暴力能过的时候我真的是有点崩溃,回来写个暴力果然一A了………………

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int maxn = 1e6 + 5;
int n, k;
int val[maxn << 2];

int dfs(int r, int sum, int dep)
{
    int le = 0, ri = 0;
    if (val[r << 1] == -1 && val[r << 1 | 1] == -1)
        return dep;
    if (val[r << 1] != -1 && sum + val[r << 1] <= k)
        le = dfs(r << 1, sum + val[r << 1], dep + 1);
    if (val[r << 1 | 1] != -1 && sum + val[r << 1 | 1] <= k)
        ri = dfs(r << 1 | 1, sum + val[r << 1 | 1], dep + 1);
    return max(le, ri);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &k);
        memset(val, -1, sizeof val);
        for (int i = 1; i <= n; i++)
            scanf("%d", val + i);
        int ans = -1;
        for (int i = 1; i <= n; i++)
            if (val[i] <= k)
                ans = max(ans, dfs(i, val[i], 1));
        printf("%d\n", ans);
    }
    return 0;
}

K.DeadLine

题意:
有一堆bug,给你每个bug修复的最后期限,要求每个bug都要在各自的期限到来或之前完成,一个程序员每天只能修复一个bug,求至少需要多少个程序员。

思路:
一般思路都会是,先排个序,扫一遍记录多余的时间,如果遇到重复的就减去多余的时间,如果没有多余的时间人数就 +1 。

当然,不可能这么简单……题目数据设置特别大……需要的是一个O(n)的算法。

最后还是没写出来,提供的题解是这样的思路:
定义一个数组,表示 deadline = 下标idx 的 bug数量。然后我们 1-n 扫一遍,记录前 idx 的bug数目num。

其中 一个程序员 idx 天能处理 idx 个 bug,那么 num 个 bug 就需要 num/idx 取上界。

妙哉!

#include <cstdio>  
#include <cstring>  
int arr[1000005];
using namespace std;  
int main()  
{  
    int n,x,maxx,num,t;  
    while(scanf("%d",&n)!=EOF) {  
        memset(arr,0,sizeof arr);  
        maxx=1;  
        num=0;
        for(int i=1;i<=n;i++) {  
            scanf("%d",&x);  
            if(x<=n)  
                arr[x]++;  
        }  
        for(int i=1;i<=n;i++) {  
            num=num+arr[i];  
            t=num/i+(num%i!=0);
            maxx=maxx>t?maxx:t;  
        }
        printf("%d\n",maxx);  
    }
    return 0;  
}  

发表评论

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