Powered by:NEFU AB-IN

Link

4461. 范围分区

• 题意

  艾伦和芭芭拉一起玩数字游戏。
  给定前 N 个正整数 1∼N。
  首先，由艾伦从中选取一些数字（不能不取），然后，芭芭拉选取剩余所有数字（如果有的话）。
  不妨设艾伦选取的所有数字之和为 A，芭芭拉选取的所有数字之和为 B。
  现在，给定一个比率 X:Y，要求 A:B 恰好等于 X:Y。
  请你给出一种艾伦选取数字的合理方案。

• 思路

  先将1~n的和求出，记为x，然后将比率放大，直到两数之和等于x，才说明时有可能的，否则是不可能的
  之后，从高到低枚举1~n，凑出刚才算出的比率即可

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-08-16 10:01:10
  * @FilePath: \Acwing\4461\4461.cpp
  * @LastEditTime: 2022-08-16 10:32:42
  */
  #include 
  using namespace std;
  #define N n + 100
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  signed main()
  {
      IOS;
      int T;
      cin >> T;
      for (int _ = 1; _ <= T; ++_)
      {
          int n, x, y;
          cin >> n >> x >> y;
          int cnt = 0;
          for (int i = 1; i <= n; ++i)
              cnt += i;
          for (int i = 1;; ++i)
          {
              int x1 = x * i;
              int y1 = y * i;
              if (x1 + y1 == cnt)
              {
                  x = x1;
                  y = y1;
                  break;
              }
              if (x1 + y1 > cnt)
                  break;
          }
          if (x + y != cnt)
          {
              printf("Case #%lld: IMPOSSIBLE\n", _);
              continue;
          }
          vector<int> a(N);
          auto f = [&](int &x) {
              vector<int> ans;
              for (int i = n; i > 0; --i)
              {
                  if (x >= i && !a[i])
                  {
                      x -= i;
                      a[i] = 1;
                      ans.push_back(i);
                  }
              }
              return ans;
          };
          vector<int> ans;
          if (x >= y)
          {
              ans = f(x);
              f(y);
          }
          else
          {
              f(y);
              ans = f(x);
          }
          printf("Case #%lld: POSSIBLE\n", _);
          printf("%lld\n", SZ(ans));
          sort(ans.begin(), ans.end());
          for (auto i : ans)
          {
              printf("%lld ", i);
          }
          printf("\n");
      }
      return 0;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84