求助站外题
  • 板块学术版
  • 楼主Spz_Dashygo
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/7/14 11:49
  • 上次更新2023/11/3 09:56:37
查看原帖
求助站外题
382886
Spz_Dashygo楼主2023/7/14 11:49

题目:


  • 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的我实在不知道有什么错误,所以请各位大佬告诉我这段代码有什么问题,谢谢!

2023/7/14 11:49
加载中...