解题报告 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

解题报告 HDU1754 I HATE IT

题目内容

hdu1754

题意

维护一些学生成绩,支持单点修改和区间求最值操作

解题思路

嗯,造一棵线段树即可

#include <bits/stdc++.h>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
#define f(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=200000+5;

int a[maxn],f[maxn<<2];

void build(int i,int j,int k)//造树
{
    if(i==j) f[k]=a[i];
    else
    {
        build(i,M,L);
        build(M+1,j,R);
        f[k]=max(f[L],f[R]);
    }
    return;
}

void modify(int u,int d,int i,int j,int k)//单点编辑操作
{
    if(i==j) f[k]=d;
    else
    {
        if(u<=M) modify(u,d,i,M,L);
        if(u>M) modify(u,d,M+1,j,R);
        f[k]=max(f[L],f[R]);//每次操作完记得回溯
    }
    return;
}

int query(int u,int v,int i,int j,int k)//区间查询操作
{
    if(u==i&&v==j) return f[k];
    else
    {
        if(v<=M) return query(u,v,i,M,L);
        if(u>M) return query(u,v,M+1,j,R);
    }
    return max(query(u,M,i,M,L),query(M+1,v,M+1,j,R));
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        f(i,1,n) scanf("%d",&a[i]);
        build(1,n,1);
        getchar();//嗯,读入回车符把我坑死了
        f(i,1,m)
        {
            char c;int a,b;
            scanf("%c %d %d\n",&c,&a,&b);//记得读入回车符
            if(c=='U') modify(a,b,1,n,1);
            if(c=='Q') printf("%d\n",query(a,b,1,n,1));
        }
    }
    return 0;
}

反思

tmd这个回车符把我弄得要死不活的
要么使用cin(怎么可能),要么使用getchar()直接读入回车符,要么使用scanf的格式化功能直接把回车符干掉。

然后每组数据读入完之后记得memset即可