解题报告 UVA297 四分树 Quadtrees

题目内容

UVA297

大意:一个 32*32 的黑白图像可以用一棵四分树表示,方法是用根节点表示整张图像,然后子树描述四个正方形,如果某个小正方形里面又有白色又有黑色,则这个儿子节点为灰色并且递归向下建树。

给出两棵四分树的前序遍历,求两张图合并起来之后的黑像素点个数。

解题思路

根据四分树的递归性,直接模拟填充颜色并统计并集的答案即可。

其中 draw(int x1,int y1,int w) 表示当前以 s_p 为根的四分树描述的是以 (x_1,y_1) 为左上角,边长为 w 的正方形区域。如果当前的根为灰色,则需要按顺序往四个子树递归(四个顺序就是象限的顺序),如果为黑色,说明整块区域都是黑色的,直接 O(w^2) 填充,白色的话直接不管即可。

#include <cstdio>
#include <cstring>

char s[1024+5];
int buf[33][33];
int ans,p;

void draw(int x1,int y1,int w)
{
    char ch=s[p++];
    if(ch=='p')
    {
        draw(x1+w/2,y1    ,w/2);//1
        draw(x1    ,y1    ,w/2);//2
        draw(x1    ,y1+w/2,w/2);//3
        draw(x1+w/2,y1+w/2,w/2);//4
    }
    else if(ch=='f')
        for(int i=x1;i<x1+w;i++)
            for(int j=y1;j<y1+w;j++)
                if(!buf[i][j])
                    buf[i][j]=1,ans++;//直接填充并记录答案
    return;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ans=0;
        memset(buf,0,sizeof buf);//记得每组数据间的清零操作
        scanf("%s",s);
        p=0;
        draw(1,1,32);
        p=0;
        scanf("%s",s);
        draw(1,1,32);
        printf("There are %d black pixels.\n",ans);
    }
    return 0;
}

解题报告 UVA839 天平 Not so Mobile

题目内容

UVA839

以前序遍历的形式给出一棵二叉树天平,给出每边的力和力臂,求整个天平能不能平衡。

解题思路

首先是 IO,由于天平是以前序遍历的形式给出来的,因此考虑直接在递归读入并直接求解。

某个天平平衡当且仅当它的每一个子天平平衡且它自身平衡,所以当读入有子天平的天平时继续往子天平递归,然后返回上来的是描述是否平衡的 bool 值,同时本层也返回本身是否满足平衡即可。

#include <cstdio>
#include <cctype>

inline int read_int()
{
    //快读被省略了
}

bool read(int &W)//W参数为子天平重量的引用,可以很方便的往上层传子天平值
{
    int WL=read_int(),DL=read_int(),WR=read_int(),DR=read_int();
    bool b1=true,b2=true;
    if(!WL)//如果有左儿子
        b1=read(WL);
    if(!WR)
        b2=read(WR);//如果有右儿子
    W=WL+WR;//当前天平的重量
    return b1 && b2 && WL*DL==WR*DR;//左右儿子都平衡且自身平衡时为true
}

int main()
{
    int t=read_int();
    int W;
    while(t--)
    {
        printf("%s\n",read(W=0)?"YES":"NO");
        if(t)
            printf("\n");//最后不输出多余空行
    }
    return 0;
}

解题报告 UVA548 树 Tree

题目内容

UVA548

给定一棵二叉树的中序遍历和后序遍历,找出一个叶子节点,使得满足从根节点到该叶子节点经过的路径上节点编号的和最小的前提下该叶子节点的编号也最小

解题思路

思路非常类似于求先序排列,关键都是在于后序遍历序列的最后一位一定是该子树的根节点,由此进行向下的递归遍历整棵树并直接在递归的时候统计答案。

难点在于 IO,可先使用 getline() 直接读入一行然后再用 stringstream 提出每一个数字来。

代码中的 int build(int l1,int r1,int l2,int r2,int sum) 表示中序遍历为 in_o[l1]in_o[r1],后序遍历为 post_o[l2]post_o[r2]sum 表示当前从根节点到当前根节点的路径经过的点权总和。

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

const int maxn=1e4+5;
int in_o[maxn],post_o[maxn],lson[maxn],rson[maxn],n;

void read(string s,int *a)
{
    stringstream ss(s);
    n=0;
    int x;
    while(ss>>x)
        a[n++]=x;
    return;
}


int ans,ans_sum;

int build(int l1,int r1,int l2,int r2,int sum)
{
    if(l1>r1)
        return 0;
    int root=post_o[r2];
    sum+=root;
    int p=l1;
    while(in_o[p]!=root)
        p++;
    int cnt=p-l1;
    lson[root]=build(l1,p-1,l2,l2+cnt-1,sum);
    rson[root]=build(p+1,r1,l2+cnt,r2-1,sum);
    if(!lson[root] && !rson[root])
        if(sum<ans_sum || (sum==ans_sum && root<ans))
            ans_sum=sum,ans=root;
    return root;
}


int main()
{
    string in,post;
    while(getline(cin,in) && getline(cin,post))
    {
        read(in,in_o);
        read(post,post_o);
        ans_sum=0x7f7f7f7f;
        build(0,n-1,0,n-1,0);
        cout<<ans<<endl;
    }
    return 0;
}

解题报告 UVA122 树的层次遍历 Trees on the level

题目内容

UVA122

大意:给定一棵二叉树,每个节点按照从根节点到它的移动序列(L 或 R)表示,如果能构成合法的二叉树,输出这棵二叉树的层次遍历,否则输出 not complete

解题思路

不能单纯的使用开一个很大的数组来堆式存储二叉树了,因为 2^{256}-1 会炸空间,所以需要使用指针来动态开点存储二叉树。

struct node
{
    bool have_value;//是否被赋值过
    int val;//节点的值
    node *left,*right;//指向左右儿子的指针,默认为NULL
    node():have_value(false),left(NULL),right(NULL){}//构造函数
};

然后就是读入一棵树了:

char s[maxn];

bool read()
{
    failed=false;
    remove_tree(root);//释放内存
    root=newnode();//指定新的根节点
    while(1)
    {
        if(scanf("%s",s)!=1)//如果输入结束了
            return false;
        if(!strcmp(s,"()"))//如果一棵树到头了
            break;
        int v;//读入该节点的值使用
        sscanf(&s[1],"%d",&v);//sscanf大法好
        addnode(v,strchr(s,',')+1);//将逗号以后的所有值传入addnode函数进行开点操作
    }
    return true;
}

动态开点:

使用 new 操作符可以动态开一个空间,同样用 delete 可以释放空间:

inline node* newnode()
{
    return new node();
}

void remove_tree(node *now)
{
    if(now==NULL)//如果节点为空
        return;
    remove_tree(now->left);//递归释放左子树
    remove_tree(now->right);
    delete now;//删除当前节点
}

传入括号内的内容进行开点

void addnode(int v,char *s)
{
    int n=strlen(s);
    node *u=root;//因为给出的点的形式都是从根开始遍历的
    for(int i=0;i<n;i++)//根据提示一步步往下走
    {
        if(s[i]=='L')
        {
            if(u->left==NULL)
                u->left=newnode();
            u=u->left;
        }
        else if(s[i]=='R')
        {
            if(u->right==NULL)
                u->right=newnode();
            u=u->right;
        }
    }
    if(u->have_value)//如果这个点已经被赋过值了,那么显然输入错误
        failed=true;
    u->val=v;//赋值
    u->have_value=true;//打标记
    return;
}

最后就是层次遍历了,可以使用 bfs 实现

bool bfs(vector<int> &ans)
{
    queue<node*> q;//存储待访问节点
    ans.clear();
    q.push(root);
    while(!q.empty())
    {
        node *now=q.front();
        q.pop();
        if(!now->have_value)//如果当前节点未赋值
            return false;//说明信息不完整
        ans.push_back(now->val);//计入答案
        if(now->left!=NULL)
            q.push(now->left);
        if(now->right!=NULL)
            q.push(now->right);//分别加入左右儿子节点
    }
    return true;
}

具体的思路就是动态开点,动态维护,然后进行 bfs。唯一的坑点是行末不能输出多余空格

#include <cstdio>
#include <cstring>
#include <queue>

using std::queue;
using std::vector;

struct node
{
    bool have_value;
    int val;
    node *left,*right;
    node():have_value(false),left(NULL),right(NULL){}
};

const int maxn=258;
bool failed;
node* root;

inline node* newnode()
{
    return new node();
}

void remove_tree(node *now)
{
    if(now==NULL)
        return;
    remove_tree(now->left);
    remove_tree(now->right);
    delete now;
}

void addnode(int v,char *s)
{
    int n=strlen(s);
    node *u=root;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='L')
        {
            if(u->left==NULL)
                u->left=newnode();
            u=u->left;
        }
        else if(s[i]=='R')
        {
            if(u->right==NULL)
                u->right=newnode();
            u=u->right;
        }
    }
    if(u->have_value)
        failed=true;
    u->val=v;
    u->have_value=true;
    return;
}

char s[maxn];

bool read()
{
    failed=false;
    remove_tree(root);
    root=newnode();
    while(1)
    {
        if(scanf("%s",s)!=1)
            return false;
        if(!strcmp(s,"()"))
            break;
        int v;
        sscanf(&s[1],"%d",&v);
        addnode(v,strchr(s,',')+1);
    }
    return true;
}

bool bfs(vector<int> &ans)
{
    queue<node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty())
    {
        node *now=q.front();
        q.pop();
        if(!now->have_value)
            return false;
        ans.push_back(now->val);
        if(now->left!=NULL)
            q.push(now->left);
        if(now->right!=NULL)
            q.push(now->right);
    }
    return true;
}

void print(vector<int> &ans)
{
    for(int i=0;i<ans.size()-1;i++)
        printf("%d ",ans[i]);
    printf("%d\n",ans[ans.size()-1]);
    return;
}

int main()
{
    vector<int> ans;
    while(read())
    {
        if(bfs(ans) && (!failed))
            print(ans);
        else
            printf("not complete\n");
    }
    return 0;
}

解题报告 UVA679 小球下落 Dropping Balls

题目内容

UVA679

一棵满二叉树,深度为 D,每个非叶子节点有一个开关,所有开关初始为关。在根节点放一个小球,他会下落,小球到达某个开关时,如果开关关,则往左走,如果开关关,则往右走,并改变开关状态,求第 I 个小球下落到的叶子节点的编号

解题思路

不难写出模拟,但发现复杂度极高,所以会 TLE,需要思考性质。

发现:对于一个落到 k 节点的第 I 个小球,I 如果是单数,则说明这个小球要向左走,反之向右走,而且发现如果落下左边,则他是落到左边的儿子节点的第 (I+1)/2 个小球,如果落到右边则是落到右边儿子节点的第 I/2 个小球,于是我们可以只关注第 I 个小球,根据奇偶性判断小球应该往哪边走。

总的时间复杂度为 O(lD),可以通过本题。

#include <cstdio>

int main()
{
    int D,I,l;
    scanf("%d",&l);
    while(l--)
    {
        scanf("%d %d",&D,&I);
        int k=1;//一开始处于根节点
        for(int i=1;i<D;i++)//往下走(D-1)层
        {
            k<<=1;//k先自乘2
            if(!(I&1))//如果I是偶数
                k|=1;//那么k要走右儿子
            else
                I+=1;//如果是奇数的话I先加1
            I>>=1;//I自除以2
        }
        printf("%d\n",k);//打印出最后的k即可
    }
    return 0;
}

解题报告 P1827 [USACO3.4]美国血统 American Heritage

题目内容

P1827

给定一二叉树的中序和先序遍历,求后序遍历

解题思路

与求先序排列的类似,思路都是找根然后递归求解。

注意到一个子树的先序遍历的第一个元素必然是这棵子树的根,因此可以通过在中序遍历中查找这个根来获知左右子树的大小然后分开递归左右子树

#include <iostream>
#include <string>
using namespace std;

void dfs(string f,string m)
{
    if(f.empty())
        return;
    int k=m.find(f[0]);
    dfs(f.substr(1,k),m.substr(0,k));
    dfs(f.substr(k+1,f.size()-k),m.substr(k+1));
    cout<<f[0];
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    string f,m;
    cin>>m>>f;
    dfs(f,m);
    return 0;
}

解题报告 P1040 加分二叉树【NOIP2003TG】

题目内容

P1040

大意:给出一个中序遍历为 1,2,\dots,n 的二叉树,记节点 i 的分数为 d_i,定义子树 subtree 的分数为左子树的加分乘右子树的加分加根的分数。求最大加分以及该情况下树的前序遍历。

解题思路

首先,只给了一个中序遍历是无法确定一棵二叉树的,这就导致了不同的二叉树有着不同的加分,我们只需要求出这最大的加分就可以了。

一棵子树的中序遍历有一个性质:选定根节点后,中序遍历左边的点一定在左子树中,右边的一定在右子树中,这就导致了我们可以递归进行求解,每次都枚举根节点。

f(i,j) 表示从 ij 的节点构成的子树的最大加分,其中 i。很明显读入的时候即可确定 f(i,i) 就是这个节点的分数,然后是状态转移方程:

f(i,j)=\max_{i\le k\le j}\lbrace f(i,k-1)\times f(k+1,j)+f(k,k)\rbrace

这个状态转移方程意思就是当前递归到子树 i,j 时,枚举所有可能存在的根节点 k,然后进行下一步的递归,在整个过程中寻找可达到的最大加分并记录。最后输出 f(1,n) 即可。

然后就是如何输出前序遍历的问题了,其实在上一步进行状态转移的时候就可以记录下可以使得子树加分最大的根节点,然后记录下来之后依次按照这样递归遍历就可以了。

上述过程中注意判断边界条件,当 i>j 时就要停止

#include <cstdio>
#include <cstring>
typedef long long ll;

ll n,f[32][32],root[32][32];
//f的定义见上,root[i][j]表示可以使得子树 i,j 加分最大的根节点的编号

ll search(int l,int r)
{
    ll now;//存储当前状态
    if(l>r)//如果遍历到空子树
        return 1;//返回1
    if(f[l][r]==-1)//如果这个子树还没有进行过处理
        for(int k=l;k<=r;k++)//枚举所有可能存在的根节点
        {
            now=search(l,k-1)*search(k+1,r)+f[k][k];//更新当前状态
            if(now>f[l][r])//如果可以更大
                f[l][r]=now,root[l][r]=k;//更新,并记录根节点
        }
    return f[l][r];//返回上级
}

void preorder(int l,int r)
{
    if(l>r)//如果空了
        return;
    int k=root[l][r];
    printf("%d ",k);//打印根
    preorder(l,k-1);//遍历左
    preorder(k+1,r);//遍历右
    return;
}

int main()
{
    scanf("%lld",&n);
    memset(f,-1,sizeof(f));//先将所有标记为未访问
    for(int i=1;i<=n;i++)
        scanf("%lld",&f[i][i]),root[i][i]=i;
    printf("%lld\n",search(1,n));//输出最大加分
    preorder(1,n);//遍历子树
    return 0;
}

解题报告 P1030 求先序排列

题目内容

P1030

大意:给出一棵二叉树的中序和后序遍历,求其先序

解题思路

首先,前序遍历是左右根,中序是左根右,后序是左右根

所以可以发现后序遍历的最后一个必然是根,然后进行访问输出,再将中序和后序遍历分成两个独立的子树进行递归求解即可。

基本的思路如上,代码:

#include <string>
#include <iostream>
using namespace std;

void dfs(string m,string b)
{
    if(!m.size())//如果递归完了就直接返回
        return;
    cout<<b[b.size()-1];//否则输出当前子树的根——后序遍历的最后一位
    int k=m.find(b[b.size()-1]);//然后将中序遍历的根找到,讲左右子树隔离开
    dfs(m.substr(0,k),b.substr(0,k));//递归求解左子树
    dfs(m.substr(k+1),b.substr(k,b.size()-k-1));//递归求解右子树
    return;
}

int main()
{
    ios::sync_with_stdio(false);//常规关闭流同步
    string m,b;
    cin>>m>>b;
    dfs(m,b);//开始遍历
    return 0;
}

解题报告 HDU4707 Pet

题目内容

HDU4707

注意读题:本题的题意是让我们求出仓鼠可能在多少个位置。由于trap在距离d以内可以捕获仓鼠,所以仓鼠一定在d以外,题目要求求的是距离根节点距离大于d的点的个数

解题思路

给出了边的条数是点数减一,所以这张图是一棵树。使用dfs遍历一遍树然后统计距离大于d的点数即可

坑点:

  • 本题有多组测试数据,每次要重新初始化一遍相关变量。
  • 遍历树的时候记得打vis标记(因为太久没做树的题了所以忘记打标记造成无限递归
  • 节点是从0开始编号的

这里使用了OOP编程(真的香

每次处理新的测试数据时清空即可

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int T;
const int maxn=100000+5;

class tree//tree类
{
public:
    vector<int> g[maxn];//邻接表存树
    bool vis[maxn];//vis数组
    int depth[maxn];//记录每个节点的深度
    int n,d;//注意节点从0开始编号
    inline void ins(int x,int y)//插入操作
    {
        g[x].push_back(y);
        g[y].push_back(x);
    }

    void dfs(int cur,int dep)//dfs
    {
        //printf("%d ",cur);
        depth[cur]=dep;//更新遍历到的节点的深度
        for(int i=0;i<g[cur].size();i++)//寻找该节点与哪些节点相连
            if(!vis[g[cur][i]])//判重
            {
                vis[g[cur][i]]=1;
                dfs(g[cur][i],dep+1);//继续遍历
            }
        return;
    }
    int ans()//统计答案的函数
    {
        int ret=0;
        for(int i=0;i<n;i++)
            if(depth[i]>d)
                ret++;//统计答案
        return ret;
    }
    void clear()//每次操作前记得清空
    {
        n=d=0;
        memset(depth,0,sizeof(depth));
        memset(g,0,sizeof(g));//我也是服了居然vector可以用memset
        memset(vis,0,sizeof(vis));
        vis[0]=1;//vis[0]必须设为1,不然会WA
    }
}t;

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        t.clear();//每次使用记得清空
        scanf("%d %d",&t.n,&t.d);
        for(int i=1;i<t.n;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            t.ins(x,y);
        }
        t.dfs(0,0);//开始遍历,从0号节点开始
        printf("%d\n",t.ans());
    }
    return 0;
}

反思

太久没做树的题果然会手生qwq