ACM 树的递归 Not so Mobile & The Falling Leaves

àì夳堔傛蜴生んèń 2022-06-12 05:56 127阅读 0赞

滴，集训第一天打卡。

今天是紫书第六章训练+STL的运用。

STL的就不放啦~这里有2道表面是建树，其实是递归（不必要建树）的题讲一下。

（哇，刷新了我对递归的认识..感觉超级厉害的！）

**UVA 839 Not so Mobile**

**![20170717160151470][]**

**![20170717160231521][]**

**题目大意：给你一个杠杆两端的物体的质量和力臂，如果质量为零，则下面是一个杠杆，判断是否所有杠杆平衡。**

#include<iostream>
    using namespace std;
    bool solve(int& W) 
    {
    	int W1,D1,W2,D2;
    	bool b1=true,b2=true;
    	cin>>W1>>D1>>W2>>D2;
    	if(!W1) 
    	b1=solve(W1);
    	if(!W2) 
    	b2=solve(W2);
    	W=W1+W2;
    	return b1&&b2&&(W1*D1==W2*D2);
    }
    int main() 
    {
    	int T,W;
    	cin>>T;
    	while(T--) 
    	{
    	    if(solve(W))
     		cout<<"YES"<<endl; 
    		else 
    		cout<<"NO"<<endl;
    	    if(T) 
    		cout<<endl;
      	}
      	return 0;
    }

**UVA 699 The Falling Leaves**

**![20170717162603771][]**

**![20170717162700590][]**

**题目大意：给定一棵树，从左到右计算竖着的权值合，例如图就是7，5+6，3**

#include <iostream>  
    #include <cstring>  
    using namespace std;  
    const int maxNum = 1005;  
    int sum[maxNum];  
    void build(int pos)   
    {// 输入并统计子树，水平位置为pos  
        int v;  
        cin >> v;  
        if(v == -1) return;// 空树结点  
        sum[pos] += v;  
        build(pos - 1);  
        build(pos + 1);  
    }  
    bool init()   
    {// 输入并初始化树根，再构建子树  
        int v;  
        cin >> v;  
        if(v == -1) return false;  
        memset(sum, 0, sizeof(sum));     
        int pos = maxNum / 2; // 树根的水平位置  
        sum[pos] = v;  
        build(pos - 1);// 构建左子树堆  
        build(pos + 1);// 构建右子树堆  
        return true;
    }  
    int main()   
    {  
        int kase=0;  
        while(init())   
        {  
            int p=0;  
            while(sum[p]==0)   
            p++;   
            cout << "Case " << ++kase << ":\n" << sum[p++];  
            while(sum[p]!= 0)    
            cout << " " << sum[p++];  
            cout << "\n\n";  
        }  
        return 0;
    }

再贴一个学姐的代码~

#include<stdio.h>
    #include<string.h>
    int a[200];
    void f(int y)
    {
    	int x;
    	scanf("%d",&x);
    	if(x==-1)return;
    	a[y]+=x;
    	f(y-1),f(y+1);
    }
    int main()
    {
    	int n,k,x,l=0,i;
    	while(scanf("%d",&x),x!=-1)
    	{
    		k=0;
    		memset(a,0,sizeof(a));
    		a[100]=x;
    		f(99),f(101);
    		printf("Case %d:\n",++l);
    		for(i=0;i<200;i++)
    		{
    			if(a[i]!=0)
    			{
    				if(k)printf(" ");
    				printf("%d",a[i]);
    				k=1;
    			}
    		}
    		puts("\n");
    	}	
    }

[20170717160151470]: /images/20220612/a20c9aeeecff484c96731cfef0f4f114.png
[20170717160231521]: /images/20220612/df5f4bd02ef342428bb09400ff1cedf2.png
[20170717162603771]: /images/20220612/8a3c2a239b5e4159b593e1dbdc21a122.png
[20170717162700590]: /images/20220612/ebf142e5a0164660bfdec5fe68d5e4fc.png