C - Folia

题目链接

题目大意

有一棵二叉树，总共n层（1e5），每层有ai个叶子节点（1e8）.
问这个二叉树里最多有多少个节点。
肯定优先这种情况：一个连一个的这种

二叉树最多有两个儿子，所以我比赛的时候总想着从上往下推万一多了，不能满足下面的，从下往上又不一定上面有那么多。
于是我就懵逼了。

题解

如果这一层下面总共有x个叶子节点，最好分出x个分支，每个叶子节点一个分支，随便到第几层截至，只要是在这层下面即可。
但是x个分支不一定能分出来，因为还受上层不是叶子结点的分支有多少个限制。

这个图的过程就是：
想在1的下面分出4各分支，但是1的下面最多有2个分支，所以分两个。
2的下面有3个叶子，所以最优分出三个分支，但只能有两个，就是2.
以此类推。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("xxx.in","r",stdin);freopen("xxx.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}

const double inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int maxn = 2e5+5;
const int M = 1e8;

int a[maxn];
ll s[maxn];
int main()
{
   
	int n;
	scanf("%d",&n);
	ll sum = 0;
	for (int i = 0; i<= n; i ++ )
	{
   
		scanf("%d",&a[i]);
		sum += a[i];
	}
	if(n > 0 && a[0] > 0)
	{
   
		printf("-1\n");
		return 0;
	}
	else if(n == 0 && a[0] > 1)
	{
   
		printf("-1\n");
		return 0;
	}
	ll s =  1;
	ll ans = 1;
	for (int i = 1; i <= n; i ++ )
	{
   
		s = min(s * 2, sum);
		ans += s;
		s -= a[i];
		sum -= a[i];
		// printf("%lld %lld %d\n",s,sum,a[i]);
		if(s < 0)
		{
   
			printf("-1\n");
			return 0;
		}
	}
	printf("%lld\n",ans);
}