题目:
Description
笨笨在小山顶上种了一棵果树,秋天了,果树结出了许多许多的果子,笨笨要去摘果子。
这是一棵可以结出3种不同果实的树,它的果实长在树枝的分叉处和树顶上。
果实分3种:普通果实、奇异果实和稀有果实。
这颗树的第一个分叉可以用一个2进制码表示(也就是许多的“1”和“0”),
而第一个分叉又分成2个分叉,分别用第一个分叉的前半段和后半段表示(从中间分开),
其他分叉也如此。分叉分到最后只剩下“1”或“0”时就成了树顶。
每个分叉只能分成2个分叉。
表示这棵树第一个分叉的2进制码必定是2的乘方位。
例如:
1 0 1 0
\ / \ /
10 10
\ /
1010
这就是一棵笨笨种的树。
三种果实的分辨方式为:
普通果实:既有“1”又有“0”;
奇异果实:只有“1”;
稀有果实:只有“0”。
每种果实的价值不同,普通果实1元,奇异果实2元,稀有果实5元。
笨笨能摘到的果实范围是一定的,他想知道他所能摘到果实的总价值。
像刚刚所示的“1010”树,它有3个普通果实,2个奇异果实和2个稀有果实,
若笨笨能摘到最高2,最低0,那么他就能得到所有的果实,果实的总价值为31+22+5*2=17元。
Input
第一行一个数n,表示这个2进制码的位数是2的多少次乘方(即长度为2^n,0<=n<=15)。
第二行2个数u,d,表示笨笨可以摘到的最大高度和最小高度(0<=d<=u<=100000)。
第三行为表示第一个分叉的位数为2^n位的2进制数。
Output
一个数,笨笨所能摘到果子的最大总价值。
Sample Input
3
3 0
10001011
Sample Output
40
以下是我的代码:
#include<iostream>
#include<cstring>
using namespace std;
struct lm{
int lc,rc;
int heigh;
int vaule;
}emt[120000];
int beg,kl,cnt=1,ans;
int high,low; //记录可以采摘的最低和最高高度
int check(string s){
bool b,i;
for(int j=0;j<s.size();j++){
if(s[j]=='1' && !i) i=1;
if(s[j]=='0' && !b) b=1;
if(i && b) return 1;
}
if(!i && b) return 5;
if(i && !b) return 2;
}
void f(string s,int root){
emt[root].vaule=check(s);
cout<<"root="<<root<<" s="<<s<<" vaule="<<emt[root].vaule<<endl; //这是重点
emt[root].vaule;
if(s.size()!=1){
int k=s.size()/2;
string lc=s.substr(0,k);
string rc=s.substr(k,k);
emt[root].lc=++cnt;
emt[cnt].heigh=emt[root].heigh+1;
f(lc,cnt);
emt[root].rc=++cnt;
emt[cnt].heigh=emt[root].heigh+1;
f(rc,cnt);
}else{
emt[root].lc=0;
emt[root].rc=0;
}
}
void print(int i){
if(emt[i].heigh>high) return ;
if(emt[i].heigh>=low) ans+=emt[i].vaule;
if(emt[i].lc!=0) print(emt[i].lc);
if(emt[i].rc!=0) print(emt[i].rc);
emt[i].lc=0,emt[i].rc=0;
}
int main(){
int n;
string s;
cin>>n>>high>>low>>s;
f(s,1);
print(1);
cout<<ans;
return 0;
}
我并没有删掉标记的那个调试代码,因为只要删掉它,ans的结果就会发生改变!
如果我输入样例,在有调试代码的情况下,ans的确是40。但如果去掉调试代码,ans就会变成27!
开始以为是电脑的问题,换了个电脑重新试,ans又变成了32!(去掉调试代码的情况下)
太奇怪了,fw的我实在不知道有什么错误,所以请各位大佬告诉我这段代码有什么问题,谢谢!