4.12题型总结

//看同学代码发现了神奇代码，借一下先存储一下，以后可能有用
template 
inline void read(T &x){x=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if(f)x=-x;}
template 
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
//之后可以一次性读取 read(x1,x2,x3..)

第一题：寻找二叉树

给邻接表结构，要求中序查找某个值对应的点，不需要太多的过程也就不用建很多变量，记录左儿子右儿子即可。

一开始出错的原因是答案格式不对，改后又错，意识到算法有点问题（就是查找的时候好像是变量重复使用重叠了），也是快速改过来。

void find(int x,int &ans){
    if(x==0) return;
    find(ls[x],ans);
    ans++; //自身 
    if(w[x] == q){
        printf("%d",ans);
        exit(0);
    }
    find(rs[x],ans);
}

总结教训就是在没有大样例支持的时候，还是要更稳一点。最好多检查几次。

第二题：对称二叉树

这个题就根据二叉树定义即可。先构造函数：

#define L(x) (x<<1)
#define R(x) x<<1|1
//左右子树 

#为0，其他为1，左右子树按位异或需要得0否则No，遍历一遍即可。

然后大小写犯错

第三题：称重

这个题类似于完全背包问题，直接展开做即可。

其实一开始还有一种想法（理论上是可以的）：比如有2g和10g砝码各一个，那么当然可以称出8g物品（左右各放1）

但是不符合天平使用标准所以忽略其实是麻烦不想写

一维数组滚动啊，然后注意输出格式

int main(){
    
    freopen("weight.in","r",stdin);
    freopen("weight.out","w",stdout);
    
    FOR(i,1,6){
        x=read();
        FOR(j,1,x) a[++cnt] = w[i];
    }
    
    f[0] = 1;
    FOR(i,1,cnt){
        for(int j = 1010;j >= 0;j--){
            if(f[j]) f[j+a[i]] = 1;
        }
    }
    
    int ans = 0;
    FOR(i,1,1010) if(f[i]) ans++;
    printf("Total=%d",ans);
    return 0;
}

第四题：装箱

这是一道01背包的变形，有意思的点在于，物品的价值就是它的重量（总价值最高，总重量最高，剩余重量就最低）

今天做题状态不错，过程比较顺利，继续加油！