摘要
Title: 4461. 范围分区
Tag: 思维
Memory Limit: 64 MB
Time Limit: 1000 ms

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 <bits/stdc++.h>
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;
}

4461. 范围分区

题意

思路

代码