题目描述
我考的是个啥呀!分数太尴尬了。还有你旦能不能分数和排名一起出啊!
样例
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int tree[N],idx; // 0值代表null
int upper_num[N]; // 记录到当前节点的路径上的最大值
int res;
void dfs(int root){
//先序遍历
if(!tree[root] || root>idx) return;
if(tree[root]>=upper_num[root>>1]){// 如果当前节点的值大于父节点所记录的路径最大值,那么是合法的 res++,并且更新当前节点路径最值
res++;
upper_num[root] = tree[root];
}else upper_num[root] = upper_num[root>>1]; // 如果不是,则将当前路径最值记录为父节点的路径最值,继续
dfs(root<<1);
dfs((root<<1)+1);
}
int main(){
string str;
getline(cin,str);
// 这一步主要是处理输入,将输入的数字直接存放到数组中(层序遍历 所以直接一个一个放)
for(int i = 0;i<str.size();){
char c = str[i];
if(c==','){
++i;
continue;
}else if(isalpha(c)){
while(str[i]!=',' && i<str.size())i++;
++idx;
}else if(isdigit(c)){
string s = "";
while(str[i]!=',' && i<str.size())
s+=str[i++];
tree[++idx] = stoi(s);
}
}
upper_num[1] = tree[1]; // 初始化
dfs(1);
cout<<res;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla