#include<bits/stdc++.h>using namespace std;using ll=long long;const int N=2e5+5;//开双倍数组避免越界 int n;int a[N],b[N];ll f[N];int main(){ cin>>n;for(int i=1;i<=n;i++) cin>>a[i],f[i]=a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=n;i;i--){  f[i]=max(f[i+1],f[i]);  f[i]=max(f[i+(b[i]?b[i]:1)]+a[i],f[i]);  //注意越界和特判b[i]为0的情况，如果不用双倍数组，需特判越界  } ll ans=0;for(int i=1;i<=n;i++) ans=max(ans,f[i]); cout<<ans;return 0;}

第二题：完全二叉树

题目描述

给定一棵包含  个结点的有根二叉树，结点依次以  编号，根结点编号为 。

对于结点 ，其左儿子的编号记为 ，右儿子编号记为 。特别地，如果左儿子不存在则 ，如果右儿子不存在则 。

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有  棵子树中，有多少棵子树是完全二叉树。

输入格式

第一行，一个正整数 ，表示有根二叉树结点数量。

接下来  行，每行两个正整数 ，表示结点  的左儿子编号和右儿子编号。

输出格式

输出一行，一个整数，表示所有子树中完全二叉树的数量。

输入样例1

42 34 00 00 0

输出样例2

4

输入样例1

42 30 04 00 0

输出样例2

3

说明/提示

对于  的测试点，保证 。

对于所有测试点，保证 。

题解部分

树上贪心

通过观察完全二叉树的结构可以得到以下结论：结论：如果以该节点的两个子节点为根形成的两个子树有一个不是完全二叉树，那么该节点为根形成的子树一定不是完全二叉树；结论2：计  为右子树节点数量  ， 为左子树节点数数量  ，则：

•  至少  个为  的整数次幂
• 如果  为 的整数次幂而  不是，那么 
• 如果  为  的整数次幂而  不是，那么 

算法流程：

1. 先利用递归回溯一遍求出每个子树的节点数
2. 再利用递归回溯一遍判断每个子树是否是完全二叉树

时间复杂度：

#include<bits/stdc++.h>using namespace std;const int N=1e5+5;int n;int l[N],r[N],ans;int cnt[N];int dep[N];bool is_cbt[N];int st[N];int dfs1(int u){//递归求子树大小 if(!u) return 0;return cnt[u]=dfs1(l[u])+dfs1(r[u])+1;}bool dfs2(int u){if(!u) return 1; bool flag=1; flag&=dfs2(l[u])&dfs2(r[u]);//如果左右儿子任一一个不满足则不满足  int rcnt=cnt[r[u]]+1,lcnt=cnt[l[u]]+1; //判断左右子节点数量是否符合要求 if(!st[rcnt]&&!st[lcnt]) flag=0;if(rcnt>lcnt) flag=0;if(st[lcnt]&&(rcnt<lcnt/2)) flag=0;if(st[rcnt]&&(2*rcnt<lcnt)) flag=0; ans+=flag;return flag;}int main(){ cin>>n; st[0]=1;for(int i=1;i<=n;i<<=1) st[i]=1;//标记桶便于判断数是否是2的正整数次幂 for(int i=1;i<=n;i++) cin>>l[i]>>r[i]; dfs1(1); dfs2(1); cout<<ans;return 0;}