题解 UVa699 The Falling Leaves

· · 题解

如果我们把这颗二叉树送左往右分成很多列的话（假设是 p\sim q），设每一列的所有层之和为 sum_i ，题目要我们求的就是这个。

利用这个性质，发现：每个节点 i ，就是其父亲节点的左儿子和右儿子；设其父亲节点所处的列是 j ，那么其所属的列数要么是 j-1，要么是 j+1。

这样一来，就可以通过这样的编号方式去计算 sum[] ，然后每次都可以在 sum[] 中找到的连续的不为 0 的一段 [p,q] 。输出这段的 sum 值就可以。

需要注意：

  1. 行末不能有空格；
  2. 两组 \text{Case} 之间要有一个空行。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=500050;
#define mid MAXN/2
int sum[MAXN];
void build(int p)
{
    int x;
    scanf("%d",&x);
    if(x==-1)return;
    sum[p]+=x;
    build(p-1);build(p+1);
    return ;
}
bool read()
{
    int x;
    scanf("%d",&x);
    if(x==-1)return false;
    memset(sum,0,sizeof(sum));
    sum[mid]+=x;
    build(mid-1);build(mid+1);
    return true;
}
int main()
{
    int t=0;
    while(read())
    {
//      memset(sum,0,sizeof(sum));
        int p=0;
        while(sum[p]==0)++p;
        printf("Case %d:\n%d",++t,sum[p++]);
        while(sum[p]!=0)printf(" %d",sum[p++]);
        puts("");puts("");
    }
    return 0;
}