2023.07.10

题面链接：https://www.aliyundrive.com/s/TDSwboqmeZh

4 位提取码在本文中出现。

blizzard

高级题目，考场差点 AC。

由于答案不可能超过 $\log n$，所以考虑借此递推。

但是，不仅需要考虑乘法组合，还要考虑加法组合。

这个加法组合……根据神秘数据，实际上只需要枚举 $1 \sim 4$ 即可……

然后我只枚举了 $1$，成功只有 80 分。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>
#include <assert.h>

using namespace std;
const int N = 5e5 + 7, INF = 0x7FFFFFFF;

void makeTrans(vector<int> &transer, int i) {
    for (int j = 2; j * j <= i; ++j) {
        if (i % j) continue;
        transer.push_back(j);
        if (j * j != i) transer.push_back(i / j);
    }
}

const int UP = 18;
int f[N][UP + 1];
void brokenHeart(int n) {
    vector<int> trans;

    for (int i = 1; i <= n; ++i) {
        f[i][0] = i - 1;
    }

    for (int i = 2; i <= n; ++i) {
        trans.clear();
        makeTrans(trans, i);

        for (int k = 1; k <= UP; ++k) {
            f[i][k] = f[i - 1][k] + 1;
            for (int j = 1; j <= min(4, i - 1); ++j) {
                for (int x = 0; x <= k; ++x)
                    f[i][k] = min(f[i][k], f[i - j][x] + f[j][k - x] + 1);
            }

            for (int t : trans) {
                for (int x = 0; x < k; ++x) {
                    f[i][k] = min(f[i][k], f[t][x] + f[i / t][k - x - 1]);
                }
            }
        }
    }
}

int ask(int n, int a) {
    int t;
    for (t = 0; t <= UP; ++t) {
        if (f[n][t] <= a) break;
    }

    return t <= UP ? t : -1;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    constexpr int tu = 500000;
    brokenHeart(tu);
    cerr << "init ut: " << (double)clock() / CLOCKS_PER_SEC << '\n';


    int T, n, a; cin >> T;
    while (T--) {
        cin >> n >> a;
        cout << ask(n, a) << '\n';
    }

    cerr << "prog ut: " << (double)clock() / CLOCKS_PER_SEC << '\n';
    return 0;
}

flames

神秘数据结构。核心在于拆矩形，变成 4 个三角形和一个正方形。

正方形容易。

三角形考虑离线后，依次扫。维护一个凸包，判断是否在三角形内。

代码没写。

heart

不会的题……