竞赛讨论区 > D题错麻了,有没有佬帮忙看看
头像
mingjuan
编辑于 01-27 11:14
+ 关注

D题错麻了,有没有佬帮忙看看

// 总体思路是先凑出1 2 4 8 16.....直到乘2大于目标数后停止
// 然后用最大值加之前操作的序列,序列为1 2 4 8 ...,所以一定操作次数后一定可以配成目标数字
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
#define kuaidu ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define PII pair<int, int>
#define endl '\n'
#define PI acos(-1)
#define int long long
vector<pair<int, PII>> v;
signed main()
{
    kuaidu;
    int T;
    cin >> T;
    while (T--)
    {
        int x, y;
        cin >> x >> y;
        if (x > y)
            swap(x, y);
        if (y % x == 0 || x == 1 || y == 1)
        {
            cout << 0 << endl;
            continue;
        }

        v.clear();
        int res = x * y / __gcd(x, y); //目标数字
        multiset<int> mu;
        int ans = 0;
        mu.insert(x), mu.insert(y);
        v.push_back({1, {x, y}}), v.push_back({1, {x, y}});
        mu.insert(1), mu.insert(1); //先把两个1插进去
        ans += 2;
        int now = 1;
        while (now * 2 <= res)
        {
            v.push_back({2, {now, now}}), v.push_back({2, {now, now}});
            ans += 2;
            now *= 2;
            mu.insert(now), mu.insert(now);
        }
        now = *mu.rbegin();
        while (now < res)
        {
            int xu = res - now;
            auto it = mu.lower_bound(xu);
            if (now + *it > res)
                it--;
            ans++;
            v.push_back({2, {*it, now}});
            mu.insert(now + *it);
            now = *mu.rbegin();
        }
        cout << ans << endl;
        for (auto x : v)
        {
            cout << x.first << " " << x.second.first << " " << x.second.second << endl;
        }
    }
}


全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐