比赛题解

HZAU 第八届校赛部分题解

Posted on

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;  
}  
比赛题解

codeforces

Posted on
A. Anastasia and pebbles

题意:
给你n种小石块,数目确定,你每次每只手只能拿k个小石块,每只手只能拿一种小石块,问多少次拿完。

思路:
贪心。
排序后从最少的开始取。我们设当前你要取的石头堆的剩余石头为cur,每次拿取有如下几种情况:

  • cur<=k 全部取走,并让另一只手去重新讨论下一堆石头
  • k < cur < 2*k 两只手全部取走 所取石头堆往后移
  • cur>2*k 两只手全部取走 当前讨论石头堆不变
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <string>

#define ll long long

using namespace std;
const double eps = 1e-6;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;

int n, m;
int arr[maxn];

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%d", arr + i);
        sort(arr,arr+n);
        int idx=0,ans=0;
        while(idx<n)
        {
            ans++;
            if(arr[idx]<=m){
                idx++;
                if(idx>=n)
                    break;
                if(arr[idx]<=m)
                    idx++;
                else
                    arr[idx]-=m;
            }
            else {
                arr[idx]-=m;
                if(arr[idx]<=m)
                    idx++;
                else
                    arr[idx]-=m;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
B. Masha and geometric depression

题意:
给你一个等比数列和数组,并给你一个上界,要你要上界之下 输出 不属于这个数组的 等比数列的所有数

思路:
题目不难,就是情况有点多,不知道怎么快速,清晰的表达
我这里用了两个set group 和 vis ,group存数组,vis存 已遍历的 等比数列的项
如果不考虑特殊情况的话,就只是两个集合之间的运算,这就不多说了。这里说一下我对特殊情况的考虑和处理。
特殊情况分为:

  • b=0 q=?
  • b=? q=0
  • b=? q=-1

但无论哪种情况,都会出现重复的元素。如果出现重复的元素,如果group内存在这个重复元素,就直接输出记录结果,否则输出inf。
但是第三种 -1 的情况会有点特殊,它可以在-b 和 b 之间不停跳转,这时候就得查找 -b 是否也在group内,如果存在,就输出记录结果,不存在就输出inf。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <string>

#define ll long long

using namespace std;
const double eps = 1e-6;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;

ll b, q, l, m;
set<int> group;
set<int> vis;

int main()
{
    int tmp;
    while (scanf("%lld %lld %lld %lld", &b, &q, &l, &m) != EOF) {
        group.clear();
        vis.clear();
        for (int i = 0; i < m; i++) {
            scanf("%d", &tmp);
            group.insert(tmp);
        }
        int ans = 0;
        bool flag = false;
        while (abs(b) <= l) {
            if (vis.find(b) != vis.end()) {
                if (group.find(b) != group.end() && (q != -1 || group.find(-b) != group.end()))
                    printf("%d\n", ans);
                else
                    puts("inf");
                flag = true;
                break;
            }
            vis.insert(b);
            if (group.find(b) == group.end())
                ans++;
            b *= q;
        }
        if (!flag)
            printf("%d\n", ans);
    }
    return 0;
}
C. Functions again

题意:
给你一个数组,如下公式,让你求最大的 f(l,r)
公式

思路:
把数组内所有数都转化一下 再求连续最大和即可(比B题简单多了

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

long long arr[100100];

long long MaxSubArray(long long a[], long long len)
{
    long long maxsum, maxhere;
    maxsum = maxhere = a[0]; 
    for (int i = 1; i < len; i++) {
        if (maxhere <= 0)
            maxhere = a[i]; 
        else
            maxhere += a[i]; 
        if (maxhere > maxsum) {
            maxsum = maxhere; 
        }
    }
    return maxsum;
}
int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%lld", arr + i);
        int key = 1;
        for (int i = 0; i < n - 1; i++) {
            arr[i] = abs(arr[i] - arr[i + 1]) * key;
            key *= -1;
        }
        long long ans = MaxSubArray(arr,n-1);
        for(int i=0;i<n-1;i++)
            arr[i]*=-1;
        printf("%lld\n",max(ans,MaxSubArray(arr, n - 1)));
    }
    return 0;
}
D. Weird journey

note:这题我自己也搞不明白,最好先别看,大神只给了我代码,我现在也理解不了

题意:
给你一个n,表示点数,m,表示边数目,m条边,构建成无向图,要你求出满足如下要求的路径数目。
任意起点,终点,满足路径上,有两条边只走过一次,其他m-2走过两次。
起点和终点不同即是路径不同,但如果起点0=终点1 终点0=起点1 则0 ,1 视为同一路径

思路:
无( ~~玛德,只给我代码,白白看了2个小时还看不懂。~~

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

const int maxn = 1000000 + 10;
int root[maxn];

int findRoot(int a)
{
    if (root[a] == a)
        return a;
    return root[a] = findRoot(root[a]);
}

bool join(int a, int b)
{
    a = findRoot(a);
    b = findRoot(b);
    if (a == b)
        return false;
    root[b] = a;
    return true;
}

int64 dg[maxn];
bool seen[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int64 n, m;
    cin >> n >> m;
    int tot = 0;    //出现的点数
    int cmp = n;    //点集数

    for (int i = 0; i < n; ++i) {
        root[i] = i;
    }

    int64 loop = 0;  //自环数
    int64 ans = 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;

        if (u == v) {
            ans += m - ++loop; //不是很懂这个地方
            if (!seen[u])
                tot++;
            seen[u] = true;
            continue;
        }

        if (!seen[u])
            tot++;
        dg[u]++;
        seen[u] = true;
        if (!seen[v])
            tot++;
        seen[v] = true;
        dg[v]++;
        if (join(u, v))
            cmp--;      
    }

    if (cmp != n - tot + 1) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < n; ++i)
        ans += dg[i] * (dg[i] - 1) / 2;

    cout << ans << endl;

    return 0;
}

如果有看懂的朋友记得跟我说一声……

E. The Great Mixing

(暂缺)