一 奇怪的电梯
我们来分析题目
这个题目有很多层电梯
我们处于这个电梯的时候，我们要考虑，我们在这个电梯里面是要上去还是下去，有两个选择，上去和下来，我们要对于这个上去和下去进行深度搜索，找出那个最好的选择
这里我们可以看到整个数据是十分庞大的，所以我们需要减枝，才可以减少时间的消耗，但是，这个题目是设置了卡dfs的，所以dfs只可以拿到部分分，但是当我们在竞赛的时候，时间不够了，直接用暴力搜索也是不错的选择
我们首先来看，这个题目我们肯定是需要减枝叶的
我们怎么减少呢？
这里我只写出了两个减枝的方案#include<iostream> #include<algorithm> #include<cstring> using namespace std;const int N = 210; int n; int a,b; bool st [N]; int num[N]; int res=1e9;void dfs(int x,int cnt){if(cnt>=res){return ;}if(x==b){res=min(res,cnt);return ;}//上if(x+num[x]<=n && !st[x+num[x]]){st[x+num[x]]=true;dfs(x+num[x],cnt+1);st[x+num[x]]=false;}//下if(x-num[x]>0 && !st[x-num[x]]){st[x-num[x]]=true;dfs(x-num[x],cnt+1);st[x-num[x]]=false;} }int main(){scanf("%d",&n);scanf("%d %d",&a,&b);for(int i=1;i<=n;i++){scanf("%d",&num[i]);}dfs(a,0);if(res==1e9){printf("-1");return 0;}printf("%d",res);return 0; }减枝方案一：
就是我们当得出一个最小值得时候，如果后面得值比这个值还大得时候，我们直接就把return，这样我们就做到了减枝if(cnt>=res){return ;}减枝方案二：
在乘坐电梯得时候，我们不经过重复得电梯，如果经过了重复的电梯层数的话，我们就直接进行return，这样我们就可以进行减枝，为什么这样可以呢？
我们在走的过程中，你想我们如果经过了重复的电梯层数的话，这样就会导致又要进行之前的上下判断，那么这个肯定是循环过来了，所以我们就要避免这个事件的发生，所以我们就可以完成进一步的减枝
我们可以完成大部分的情况，但是还有部分情况是超出时间的范围的，所以这个方法做这个题目的是在想不出别的思路进行书写
二 完全二叉树的权值
我们在分析这个题目的时候，我们要仔细去分析
在算法竞赛我们是没有这么多时间去构造一棵树的，即使你会，你也要先考虑有没有其他的方法来进行解题，减少自己敲代码的时间的花销，如果你树书写错了你还要花时间在树上面
所以这里我们用dfs来解答这个题目
我们来看题目
分析
首先他会给你节点的个数，然后输入一行的数字
这些数字是根据层的顺序来输入的
接下来我来画一个图来表达这个代码的思路
我们可以看到这个题目，这个题目就是说这个我们先以深度优先为头，然后进行后面的回溯，但是有人会说了我怎么知道怎么进行深度优先，这里又没有指数啥的，我咋办，其实这个可以类似于指数，但是不完全是指数
首先我们可以观察到，这个2是上一个序号2倍，然后深入加1了，我们只需要进行对应的深度加对应的值就好了，然后这个经过这个4之后就直接到2，然后进行右子树，这个右子树是多少呢？就是2*对应的值+1我们后面要带一个加1，为什么呢？是由层数决定的，因为你看我们递归到4是第三层，然后再回溯，然后再递归右子树，这个时候深度又要+1，然是这个5其实就是在我们输入顺序的那个左子树的后面一个而已
接下来我们用代码书写一遍
#include<bits/stdc++.h> #include<queue> using namespace std;const int N = 1e5+10; int n; int node[N]; int ans[N];void dfs(int x,int depth){if(x>n) return ;ans[depth]+=node[x];//遍历左子树dfs(x*2,depth+1);//遍历右子树dfs(x*2+1,depth+1); }int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&node[i]);}dfs(1,1);int summax=0;int levelmax=1;for(int i=1;i<=log2(n)+1;i++){if(ans[i]>summax){summax=ans[i];levelmax=i;}}printf("%d\n",levelmax); }
总结：
这里的奇怪电梯分析为dfs主要是它有电梯有上和下选择
这里的二叉树为什么会想到dfs呢？
在思考的过程中我们学过树的广度优先，那么就会想到不用构造树来进行书写代码，首先我们是先递归到最低层的时候来进行逐层计数，但是这个for循环好像写不出来，然后我就想不用直接到底层，把这个逐层改成深度，先进行分为左子树和右子树，然后随着深度的进行加权和值，然后左边判断完再进行右子树，这样就可以进行到逐层的得到对应的值
方法不一定最好，欢迎留下更好的方法
