主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:CF331C3 The Great Julya Calendar
最后更新于 2025-07-31 09:17:22
作者
Milthm
分类
题解
题解
CF331C3
复制 Markdown
查看原文
删除文章
更新内容
有一个朴素的 dp 是直接设 $dp_i$ 表示把 $i$ 删到 $0$ 的最小次数,可以转移:$dp_i=\min(dp_{i-d})+1$,其中 $d$ 存在于 $i$ 的数位中。 进一步观察性质发现,dp 数组是递增的,简单说明一下:设 $q(i)$ 为 $i$ 的最大数位的数,那么有 $q(i-1)\ge q(i)-1$(可以自己举几个例子验证),所以可以数学归纳法证明原式。 也就是说转移方程变为了 $dp_i=dp_{i-D}+1$,其中 $D$ 为 $i$ 的最大数位,但是此时还是很难解决。不过看到 $n\le 10^{18}$,以及转移和数位有关,大方向是数位 dp 没错了。 数位 dp 通常从高到低考虑,每次考虑到一位时递归下一位的状态,完成转移并使得总状态数可以接受。我们按照这个方式来走的话,可以设 $dp_{mx,n}$ 表示当前处理的数为 $n$,转化到 $n$ 之前的数位最大值为 $mx$,使 $n$ 变为 $0$ 的最小操作次数。这样设计状态好像就可以按照我们的方式转移:设 $n$ 除去最高位为 $a$,那么我们就可以往下递归 $a$,接下来我们可能会尝试向下递归 $n-a$(即把除了最高位都变成 $0$ 的 $n$),但是这里没有办法转移了,仔细想想,我们好像还需要知道递归的 $a$ 减完以后剩下了什么。 于是把 dp 数组的值改成一个二元组,这样终于可以成功转移了。转移到最后,我们可能会转移到 $n\le 9$ 的情况,这个时候根据数位 dp 的经验需要特判。但是还有一个地方需要注意,就是如果说遇到 $2001$ 这样的数,我们向下递归,此时递归到了状态 $mx=2,n=1$,那么这个时候使用操作了以后得到的数就是 $1-2=-1$,但是不能舍弃它,因为这对应着 $2001-2=1999$。也就是说,我们的 dp 状态的第二维“减完了以后剩下什么”可能是一个负数。 同时这也提醒我们注意一个细节,在最后特判 $n\le 9$ 的时候,即使 $n=0$ 也不一定步数为 $0$,他可能对应着类似 $2000-2=1998$ 这种,所以只有 $mx=n=0$ 的时候,步数才可以是 $0$。 现在我们保证了做法的正确性,但是没有说明做法的复杂度是否合理。但是分析一下,从 $n$ 的角度考虑,每次转移都会转移到什么样的数: - 读入的数的后缀。 - 一个个位数后面一堆 $9$,最后一个个位数。 - 一个个位数后面一堆 $0$,最后一个个位数。 第一种状态的量级为 $O(\log n)$,而后面两种情况因为开头的个位数是根据读入的 $n$ 可以确定的,所以变化的只有最后一位数,量级为 $O(\alpha \log n)$,其中 $\alpha$ 为进制,这里为 $10$。最后因为状态还包含了一个 $mx$,所以总的状态数为 $O(\alpha^2 \log n)$。 实现的时候我们要用 map 对状态进行记录,可能会再填一个 log,但是采用哈希表就不会。这里还是实现前者。 ```cpp #include<bits/stdc++.h> #define int long long #define pi pair<int,int> using namespace std; map<pi,pi>qwq; int n; pi dfs(int mx,int n){ if(qwq.count({mx,n}))return qwq[{mx,n}]; if(n<=9)return {n>0||mx>0,n-max(mx,n)}; int hd=1; while(hd<=n/10)hd*=10; pi low=dfs(max(mx,n/hd),n%hd); pi hi=dfs(mx,n-n%hd+low.second); return qwq[{mx,n}]={low.first+hi.first,hi.second}; } signed main(){ cin>>n; cout<<dfs(0,n).first; return 0; } ```
正在渲染内容...
点赞
1
收藏
0