URAL2108 Oleg and Little Ponies（bitset模拟）

Oleg and Little Ponies

Time limit: 0.9 second
Memory limit: 64 MB

Little boy Oleg loves the cartoon My Little Pony. How it cannot be loved, because there is friendship, magic and colored horses!

For the past several months Oleg has been begging from his parents a real pony, but they are just ready to buy him only collectible figures of cartoon characters. With these figures Oleg recreates the best episodes of My Little Pony on his desk. Sometimes he realizes that he has already all the key characters for the next episode, and begins to feel the desire to immediately buy the missing figures for this episode. For example, if Oleg has on hand Twilight Sparkle and Spike, his life will not be sweet without Princess Celestia. It may happen that the new figures will cause new desires: having three above-mentioned figures, Oleg will want Nightmare Moon.

For convenience, let’s number all the figures with integers from 1 to n. Then the Oleg’s desire will be described by two sets of numbers {a1, ..., ak} and {b1, ..., bt}, which means that if he already has figures with numbers a1, ..., ak, he also wants figures with numbers b1, ..., bt.

Oleg’s parents in order to distract him from his desires of real pony are ready to buy him as many figures as he wants. But they want to buy a set of figures that will satisfy all the desires of Oleg, in a single purchase. Of course, parents will not buy the extra figures.

What figures will Oleg have after purchase?

Input

The first line contains integers n and m that are the number of figures and the number of Oleg’s desires (1 ≤ n ≤ 1000; 0 ≤ m ≤ 4000). The following m lines describe the desires. Each desire is given by two sets, separated by a space. A set is a string of n characters, each of that is “0” or “1”. The figure with number iis in the set, only when i-th character of the string is “1”. The last line contains the set of figures, which Oleg already has, in the same format.

Output

In a single line output a set of figures, which Oleg will have after purchase. In other words, it is the union of the set of the existing figures and the set of figures bought by parents. Output format is the same as in the input.

Sample

input

6 4
111000 101000
110000 111000
010000 100000
000010 000001
010100

output
```
111100
```

Notes

In the example Oleg has already the figures 2 and 4. First, he wants the figure 1 (the third desire). If he gets it, he will want the figure 3 (the second desire). If you just buy him the figures 1 and 3, Oleg will not want anything more (the right part of the first desire consists of already existing figures, and the left side of the last desire is not fulfilled). Thus, after purchase Oleg will have figures with the numbers 1, 2, 3 and 4.

Problem Author: Kirill Borozdin
Problem Source: Ural FU Junior Championship 2016

链接

https://cn.vjudge.net/problem/URAL-2108

题意

给定2*m个n位01二进制卡片和一个已有的n位卡片，如果已有的卡片存在与左边卡片中某位二进制相同，那么必须要有对应右边的卡片，一直匹配下去（已有的卡片会加上新获得的卡片），问最后拥有的卡片情况，二进制表示。

题解

使用bitset进行模拟，判断某位相同可以用(desire[i][0] & figure) == desire[i][0]，获取为1的位可以使用figure |= desire[i][1]，最后输出的时候是将bitset转为了string，因为bitset是从低位开始存的，所以输出string的最后n位。

Status	Accepted
Time	639ms
Memory	1464kB
Length	1305

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn = 1010;
const int maxm = 4010;
bitset <maxn> desire[maxm][2];
bitset <maxn> figure;
bool vis[maxm];
int n, m;

void init()
{
    for (int i = 0; i < maxm; ++i)
    {
        desire[i][0].reset();
        desire[i][1].reset();
    }
    figure.reset();
    memset(vis, 0, sizeof(vis));
}

int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        init();
        for (int i = 0; i < m; ++i)
        {
            cin >> desire[i][0];
            cin >> desire[i][1];
        }
        cin >> figure;
        bool flag;
        while (true)
        {
            flag = false; // 标记结束条件
            for (int i = 0; i < m; ++i)
            {
                if (vis[i])
                    continue;
                if ((desire[i][0] & figure) == desire[i][0]) // 如果存在为1的位相同
                {
                    vis[i] = true;
                    figure |= desire[i][1]; // 获取为1的位
                    flag = true;
                }
            }
            if (!flag) // 找不到了
                break;
        }
        string s = figure.to_string(); // to_string的作用是把位组成的数据集合转换成字符串
        cout << s.substr(s.length() - n, n) << endl; // 输出最后n位
    }
    return 0;
}

时间限制为900ms，跑了639ms。

The end.
2018-08-29 星期三