【二进制 && bitset】URAL - 2108 Oleg and Little Ponies

xiaoxiao2021-02-28  12

Problem Description

输入n, m分别代表二进制串的长度 和 有m对串的转换。 再给你一个当前串。 串的转换是指:如果当前串&左串=当前串,那么当前串|左串。 m对串你随便使用来转换,让你求最后 输出当前串。 例子 6 4 111000 101000 110000 111000 010000 100000 000010 000001 010100 当前串&第三对的左串 = 当前串,so 当前串 = 010100|100000 = 110100 当前串&第二对的左串 = 当前串,so 当前串 = 110100|111000 = 111100 以此类推 最后当前串为 111100

思路:

核心:只要使用过的串,就不需要在使用它

#include<bits/stdc++.h> using namespace std; const int N = 1005; const int M = 4005; bitset<N> data[M][2], sf; bool vis[M]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= m; i++) { cin >> data[i][0] >> data[i][1]; } cin >> sf; memset(vis, false, sizeof(vis)); while(true) { bool flag = false; for(int i = 1; i <= m; i++) { if(vis[i]) continue; if((data[i][0] & sf) == data[i][0]) { flag = true; vis[i] = true; sf |= data[i][1]; } } if(!flag) break; } string s; s = sf.to_string(); cout << s.substr(s.size()-n) << endl; return 0; }
转载请注明原文地址: https://www.6miu.com/read-1650208.html

最新回复(0)