【题目记录】——2021牛客暑期多校训练营9

ゞ浴缸里的玫瑰 2022-09-05 06:00 126阅读 0赞

### 文章目录 ###

*  E Eyjafjalla
 *  H Happy Number

题目集地址 [2021牛客暑期多校训练营9][2021_9]

# E Eyjafjalla #

题目地址[E Eyjafjalla][]  
参考博客[2021牛客暑期多校训练营9 Eyjafjalla][2021_9 Eyjafjalla]  
题意：给出一棵树，每个树上都有权值，且保证父节点的权值比其所有子节点大。现在给出 m组询问，每次询问给出 u , l , r，表示u点只有在其权值为 \[ l , r \]时才会被感染，除了 u 点其它点当且仅当其有一直连点被感染且自身权值在 \[l,r\] 时才会被感染，问最多能扩散到几个点。  
思路：这个是关于树的题目，看样子难度不是很大，但是树这方面的内容不是我主要学习的方面，先把题目记录在这里。

#include <bits/stdc++.h>
    typedef long long ll;
    const int MAXN = 3e5 + 10, INF = 0x3f3f3f3f;
    std::vector < int > G[MAXN], alls;
    int n, m, t[MAXN], fa[MAXN][32], dist[MAXN], vis[MAXN], sz[MAXN];
    int que[MAXN], l, r, root[MAXN], id[MAXN];
    int cnt;
    struct node
    { 
        int lson, rson, val;
    }tr[MAXN * 40];
    struct Query
    { 
        int root, l, r;
    }Q[MAXN];
    int idx = 0;
    int getidx(int x)
    { 
        return std::lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
    }
    int build(int l, int r)
    { 
        if (l == r) return ++idx;
        int p = ++idx, mid = l + r >> 1;
        tr[p].lson = build(l, mid); tr[p].rson = build(mid + 1, r);
        return p;
    }
    int insert(int now, int prv, int l, int r)
    { 
        int pidx = ++idx;
        tr[pidx].val = tr[prv].val + 1;
        if (l == r) return pidx;
        int mid = l + r >> 1;
        if (now <= mid) tr[pidx].lson = insert(now, tr[prv].lson, l, mid), tr[pidx].rson = tr[prv].rson;
        else tr[pidx].lson = tr[prv].lson, tr[pidx].rson = insert(now, tr[prv].rson, mid + 1, r);
        return pidx;
    }
    int query(int p, int q, int t, int s, int l, int r)
    { 
        if (l <= t && s <= r) return tr[q].val - tr[p].val;
        int mid = t + s >> 1, ans = 0;
        if (l <= mid) ans += query(tr[p].lson, tr[q].lson, t, mid, l, r);
        if (r > mid) ans += query(tr[p].rson, tr[q].rson, mid + 1, s, l, r);
        return ans;
    }
    void dfs(int now, int f)
    { 
        sz[now] = 1; ++cnt;
        root[cnt] = insert(getidx(t[now]), root[cnt - 1], 1, m);
        id[now] = cnt;
        for (auto &i : G[now])
        { 
            if (i == f) continue;
            dfs(i, now);
            sz[now] += sz[i];
        }
    }
    int main()
    { 
        scanf("%d", &n);
        for (int i = 1; i <= n - 1; ++i)
        { 
            int u, v; scanf("%d%d", &u, &v);
            G[u].push_back(v); G[v].push_back(u);
        }
        t[0] = INF;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &t[i]), alls.push_back(t[i]);
        int q; scanf("%d", &q);
        for (int i = 1; i <= q; ++i)
        { 
            scanf("%d%d%d", &Q[i].root, &Q[i].l, &Q[i].r);
            alls.push_back(Q[i].l); alls.push_back(Q[i].r);
        }
        std::sort(alls.begin(), alls.end());
        alls.erase(std::unique(alls.begin(), alls.end()), alls.end());
        m = alls.size();
        dist[1] = 1, vis[1] = 1;
        que[1] = 1, l = r = 1;
        while (l <= r)
        { 
            int u = que[l++];
            for (auto &i : G[u])
                if (!vis[i])
                { 
                    dist[i] = dist[u] + 1, fa[i][0] = u;
                    que[++r] = i, vis[i] = 1;
                    for (int j = 1; j <= 31; ++j)
                        fa[i][j] = fa[fa[i][j - 1]][j - 1];
                }
        }
        root[0] = build(1, m); dfs(1, -1);
        for (int i = 1; i <= q; ++i)
        { 
            int rx = Q[i].root;
            if (t[rx] > Q[i].r || t[rx] < Q[i].l)
            { 
                printf("0\n");
                continue;
            }
            for (int j = 31; j >= 0; --j)
                if (t[fa[rx][j]] <= Q[i].r) rx = fa[rx][j];
            printf("%d\n", query(root[id[rx] - 1], root[id[rx] + sz[rx] - 1], 1, m, getidx(Q[i].l), getidx(Q[i].r)));
        }
        return 0;
    }

# H Happy Number #

题目地址[H Happy Number][]  
题意：定义数字2，6，3的数字为ha

ppy number,问第n个happy number是哪个数字。  
思路：比较简单，找到排数的规律就行了。但这个三进制的数值表示是1到3。把n转换为三进制之后对于每个小于等于0的位向高位借一个3即可。

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    int a[100];
    int cnt;
    int main()
    { 
    	freopen("in.txt","r",stdin);
    	freopen("out.txt","w",stdout);
        int n;
        scanf("%d",&n);
        while(n)
        { 
            a[cnt++]=(n%3);
            n/=3;
        }
        for(int i = 0;i < cnt - 1;i++)//最高位不做借位处理
        { 
            if(a[i] <= 0)
            { 
                a[i]+=3;
                a[i+1]--;
            }
        }
        for(int i = cnt-1;i >= 0;i--)
        { 
            if(a[i] == 1)
            { 
                printf("2");
            }
            if(a[i] == 2)
            { 
                printf("3");
            }
            if(a[i] == 3)
            { 
                printf("6");
            }
        }
        return 0;
    }

[2021_9]: https://ac.nowcoder.com/acm/contest/11260
[E Eyjafjalla]: https://ac.nowcoder.com/acm/contest/11260/E
[2021_9 Eyjafjalla]: https://blog.csdn.net/qq_45863710/article/details/119704632
[H Happy Number]: https://ac.nowcoder.com/acm/contest/11260/H