伊埃斯的小站
日记

日记

Thu Jan 09 2025
8 分钟
life 日记
1279 字

反正你也写不出来题，不如来写日记。

上午 Link to 上午

有日记的那天一定有考试。

T1 Link to T1

赛时想法：∅\empty

T2 Link to T2

赛时做法：先考虑熊熊的方案。很简单，就是先把 a,ba,b 按照和排序，然后依次把 ai+bi>0a_{i} + b_{i} > 0 的记录进答案。如果有那种 ai×bi<0a_{i} \times b_{i} < 0 的，可以把它放在两边，那样也能够有贡献。

再考虑梦梦的方案。梦梦肯定要尽可能的吧和最小的那对 ai,bia_{i},b_{i} 塞进熊熊的区间内。但是他先手，他不知道熊熊如何取，为了尽可能的碰到熊熊的区间，他肯定吧他放在数组的中间，以最大化碰到熊熊区间的可能性。

T3 Link to T3

德塔斯抓克车儿啊，写不了一点。

T4 Link to T4

因为死磕 T2 去了，所以没写。但是似乎有点思路？

看到第一句话，你应该想到这是在考试里写的日记，个人感觉今天要爆零。上面说了 T4 有思路，但是也仅限有思路，因为好歹还是一道 T4 是吧，最后 1010 min 怎么可能写的完呢？

中午 Link to 中午

颓废了一中午。

其实也不是颓废啦，就是无所事事而已。

感觉有点浪费时间，但是内耗更浪费时间，所以还是算了，别想了

下午 Link to 下午

改题。

T1 Link to T1

直到现在都云里雾里的。

T2 Link to T2

一道 dp，码量奇大无比。

以下为 自己骂自己：

你 tm 连蓝色的 dp 都 tmd 写的出来，被 tmd 这么一道小的 dp 创翻了？你 tm 有没有点出息？

你说的对，但是我能做到蓝色紫色 dp 仅限于数位 dp 和板一点的斜率优化 dp。偶尔也能做线性 dp。

但是你 tm 不是切过一道蓝色的线性 dp 吗。

蚁钳是蚁钳，现在是现在。

你 ******。

由于太中二了，所以就不写下去了。

T3 Link to T3

没改。究其原因是去找 T4 题解了。

T4 Link to T4

sourcesolution

记录一下解题思路：

根据不知道叫啥反正是个定理，每个数都可以分解成 ∏piei\prod p_{i}^{e_{i}}。而这个数的因数数量就是 ∏(ei+1)\prod (e_{i} + 1)。于是我们就只用关心 ee 了。对于每一个数 ii 都有一个可重集 vi={e1,e2,e3,⋯ ,en}v_{i} = \{e_{1},e_{2},e_{3},\cdots,e_{n}\}。其中有 ei≥ei+1e_{i} \ge e_{i + 1}。可以证明一共只有 289289 个不同的 SS（可惜我不会）。设 valival_{i} 为 ii 的最小质因数，mpvi,jmp_{v_{i},j} 表示把集合 viv_{i} 变到有 jj 个因数的最小步数。初始状态 mpv1,1=0mp_{v_{1},1} = 0。考虑转移：

mpv1,i=mpv1,ivali+vali−1mp_{v_{1},i} = mp_{v_{1},\frac{i}{val_{i}}} + val_{i} - 1

为什么可以这么转移呢？因为如果我们想增加因数的个数，无非就是两种方案：新增一个质数或者把某一个原有质数的次数 +1+1。显然新增质数更快。所以我们就需要 vali−1val_{i} - 1 次操作。

现在考虑 mpvi,jmp_{v_{i},j} 的转移。根据刚刚的结论，可以得出如果存在质因数 pp 只在 ii 中出现且是次数最小的，那么用它转移 jj 是最优的，花费为其出现次数。

那如果没有 pp 怎么办，也很简单。我们只用修改 eie_{i} 最小的质因数，枚举 k∈[2,+∞]k \in [2,+ \infty]，然后用 vk×jv_{k \times j} 转移 SjS_{j}。

贴一下代码：

CPP
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
#include<bits/extc++.h>
#define int long long
#define vi vector<int>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 1e6 + 5,n = 1e6;
const int maxm = 300,m = 290;
int val[maxn];
vi pr,v[maxn];
map<vi,vi>mp;
void prime()
{
    for (int i = 2; i <= n; i++)
    {
        if (!val[i])
        {
            pr.push_back(i);
            val[i] = i;
        }
        for (auto j = pr.begin(); j != pr.end() && *j * i <= n; j++)
        {
            val[*j * i] = *j;
            if (i % *j == 0)
                break;
        }
    }
}
signed main()
{
    prime();
    for (int i = 2; i <= n; i++)
    {
        v[i] = v[i / val[i]];
        if (val[i] != val[i / val[i]])
            v[i].push_back(2);
        else
            v[i].back()++;
    }
    for (int i = 1; i <= n; i++)
        sort(v[i].begin(),v[i].end(),greater<int>());
    mp[v[1]].resize(maxm);
    mp[v[1]][1] = 0;
    for (int i = 2; i <= m; i++)
        mp[v[1]][i] = mp[v[1]][i / val[i]] + val[i] - 1;
    for (int i = 2; i <= n; i++)
    {
        if (mp.count(v[i]))
            continue;
        vi tmp = v[i];
        tmp.pop_back();
        mp[v[i]].resize(maxm);
        for (int j = 1; j <= m; j++)
            mp[v[i]][j] = mp[tmp][j] + v[i].back() - 1;
        for (int j = 1; j <= m; j++)
            for (int k = 1; k * j <= m; k++)    
                mp[v[i]][j * k] = min({mp[v[i]][j * k],mp[tmp][j] + abs(v[i].back() - k),mp[v[i]][j] + k - 1});
    }
    int t,x,y;
    scanf("%lld",&t);
    while (t--)
    {
        scanf("%lld%lld",&x,&y);
        int ans = inf;
        vi tmp1 = mp[v[x]],tmp2 = mp[v[y]];
        for (int i = 1; i <= m; i++)
            ans = min(ans,tmp1[i] + tmp2[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

Telegram
Douban
Reddit
Pocket