SDUT 3513 皮卡丘的梦想(二进制+线段树)解题报告

2016-03-26 270 次浏览 解题报告

题面

皮卡丘的梦想
Time Limit: 1000ms Memory limit: 65536K

题目描述
一天,一只住在 501 的皮卡丘决定发奋学习,成为像 LeiQ 一样的巨巨,于是他向镇上的贤者金桔请教如何才能进化成一只雷丘。
金桔告诉他需要进化石才能进化,并给了他一个地图,地图上有 n 个小镇,并且标注了每个小镇上可收集的进化石。
但是皮卡丘拿到地图就蒙圈了,他可不知道自己到底需要哪种进化石,而且由于经费有限,他只能去某几个相邻的小镇,所以他机智地找到了善于编程的你,询问你这些镇上可收集的进化石有哪些,然后再自己决定行程。

输入
首先输入一个整数 T (1 <= T <= 10),代表有 T 组数据。
每组数据的第一行输入一个整数 n (1 <= n <= 100000),代表有 n 个小镇。
接下来的 n 行表示第 1 个到第 n 个的小镇的信息。每行先输入一个整数 m (0 <= m <= 30),代表这个小镇上进化石的种类数,紧接着输入 m 个整数,代表进化石的种类编号(编号从 1 开始,不超过 30)。
之后的一行输入一个整数 q (1 <= q <= 25000),代表皮卡丘有 q 次询问。 接下来的 q 行每行输入两个整数 l, r (1 <= l <= r <= n),表示他想询问从第 l 个到第 r 个小镇上可收集的进化石有哪几种。

输出
对于每组输入,首先输出一行 "Case T:",表示当前是第几组数据。
接下来对于每一次询问,按编号升序输出所有可收集的进化石。如果没有进化石可收集,则输出一个小豪的百分号 "%"(不要问我为什么,出题就是这么任性)。

示例输入
1
3
2 3 10
3 1 2 4
0
3
1 2
2 3
3 3

示例输出
Case 1:
1 2 3 4 10
1 2 4
%

提示

来源
bLue

解题思路

作为大一小学弟一枚,第一次在学校 OJ 上出题,还连上了三道(3511、3512、3513,推荐大家都去做做),感觉好方啊,还好有 raincloud 老师和 LeiQ 学长帮忙。

言归正传,这道题一看就是很裸的区间查询(毕竟弱弱一枚,只能出这种难度的题了QAQ~),很容易想到要用线段树(不会的童鞋们抓紧去学吧,有一点树的基础就很容易入门)。当然肯定不能就这样算了,为了让题目中的「皮卡丘」同学火一把,肯定要增加一些难度,于是便有了查询区间内进化石有哪几种的设定,所以如果只用线段树,在每次查询的时候照旧遍历所有进化石的话还是会超时的(怪我咯)。这时我们就需要更高效的方法来存储和查询所有进化石的状态,这种方法就是利用二进制表示存在状态。

我们用二进制数的每一位来表示每种进化石的有无,也即该小镇进化石的存在状态。举个栗子,对于有 1、4 号进化石的小镇,我们可以用二进制数 1001 来表示。它的含义是:从右向左依次表示第 1 个到第 n 个进化石的有无,1 表示有,0 表示无。而且很容易想到,由于每一位只有 0 或 1 两种可能,且每一位都对应固定的编号,所以对于任意一个二进制数,都能保证唯一对应一种存在状态。

解决了如何表示存在状态的问题,下一步就是如何存储了。再举个栗子,当前我们的进化石存在状态为:1、4,对应二进制 1001,如果我们加入一个 3 号进化石,则应变为 1101,也就是让倒数第三位变成 1。这里需要用到位运算(没学过的赶快去学):对于 1001,我们让它与 0100(只含有 3 号石的状态)进行或运算,即两数对应的位有一个或两个为 1 时结果为1,否则为 0,运算结果为 1101。这样我们使用或运算就可以实现两个状态的合并。至于如何表示单个进化石的状态,很简单,使用左移运算就可以了,栗如:表示 3 号石存在,只需将 1(0001)左移 3-1=2 位即得到 0100。

这样,我们只需要把二进制和线段树结合一下就可以愉快地告别 TLE 了。在存储时,每一个结点都表示它的左右子结点的合并状态,即对左右子结点进行或运算后的结果,而叶结点直接存储状态。在查询时,只需要遍历结果对应二进制的每一位来输出即可。

这样我们就可以写出本题的代码了:

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

const int MAX = 100001;
int st[MAX<<2];

void Initialize();
void Update(int node, int l, int r, int index, int value);
int Query(int node, int l, int r, int il, int ir);

int main(int argc, char const *argv[]) {
    int t, n, m, q, l, r;
    scanf("%d", &t);
    for(int i=1; i<=t; ++i) {
        printf("Case %d:\n", i);
        scanf("%d", &n);
        Initialize();
        for(int j=1; j<=n; ++j) {
            scanf("%d", &m);
            int binary = 0, idx;
            while(m--) {
                scanf("%d", &idx);
                //每读入一个编号,更新一次状态
                binary |= 1<<(idx-1);
            }
            //在线段树中更新此下标的状态
            Update(1, 1, n, j, binary);
        }
        scanf("%d", &q);
        while(q--) {
            scanf("%d %d", &l, &r);
            int res = Query(1, 1, n, l, r);
            int digit = 1;
            bool is_first = true;
            //遍历状态来输出存在的进化石编号
            while(res) {
                //如果当前状态的最后一位为1,则输出
                if(res & 1) {
                    if(is_first) is_first = false;
                    else printf(" ");
                    printf("%d", digit);
                }
                //判断完一位,右移删掉最后一位
                res >>= 1;
                digit++;
            }
            if(digit == 1) printf("%%");
            printf("\n");
        }
    }
    
    return 0;
}

void Initialize() {
    memset(st, 0, sizeof(st));
}

void Update(int node, int l, int r, int index, int value) {
    int mid = (l + r) >> 1;
    if(l == r) {
        st[node] |= value;
        return;
    }
    if(index <= mid)
        Update(node<<1, l, mid, index, value);
    else
        Update(node<<1|1, mid+1, r, index, value);
    //更新为左右子结点的合并状态
    st[node] = st[node<<1] | st[node<<1|1];
}

int Query(int node, int l, int r, int il, int ir) {
    int mid = (l + r) >> 1;
    if(l == il && r == ir)
        return st[node];
    if(ir <= mid)
        return Query(node<<1, l, mid, il, ir);
    else if(il > mid)
        return Query(node<<1|1, mid+1, r, il, ir);
    else
        //跨区间查询时,返回左右两边状态的合并状态
        return Query(node<<1, l, mid, il, mid)
            | Query(node<<1|1, mid+1, r, mid+1, ir);
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/03/26/sdut-3513.dream

还不快抢沙发

添加新评论