Advertisement
Guest User

Untitled

a guest
Aug 12th, 2020
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <iostream>
  4. #include <vector>
  5.  
  6. using std::cin;
  7. using std::cout;
  8.  
  9. void make_bitset(std::bitset<101> &bits, int num) {
  10.     while (num != 1) {
  11.         if (num <= 100) {
  12.             bits[num] = true;
  13.         }
  14.         if (num % 2) {
  15.             num = (num * 3 + 1) / 2;
  16.         } else {
  17.             num /= 2;
  18.         }
  19.     }
  20. }
  21.  
  22. int main() {
  23.     std::ios::sync_with_stdio(false);
  24.     std::bitset<101> bits;
  25.     bits.reset();
  26.     std::vector<int> previous_choice;
  27.     previous_choice.reserve(100);
  28.     int nums[100];
  29.     int n;
  30.     cin >> n;
  31.     for (int i = 0; i < n; ++i) {
  32.         cin >> nums[i];
  33.     }
  34.     for (int i = n-1; i >= 0; --i) {
  35.         if (!bits[nums[i]]) {
  36.             bits.reset();
  37.             make_bitset(bits, nums[i]);
  38.  
  39.             for (auto x = previous_choice.begin();
  40.                     x != previous_choice.end();) { //把之前选择中在新bitset的元素去除
  41.                 if (bits[*x]) {
  42.                     x = previous_choice.erase(x);
  43.                 } else {
  44.                     make_bitset(bits, *x);
  45.                     ++x;
  46.                 }
  47.             }
  48.             previous_choice.push_back(nums[i]);
  49.         }
  50.     }
  51.     int size = previous_choice.size();
  52.     for (int i = 0; i < size - 1; ++i) {
  53.         cout << previous_choice[i] << ' ';
  54.     }
  55.     cout << previous_choice[size - 1] << '\n';
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement