自动搬运

查看原文

来自洛谷，原作者为

	AzusaShirasu アンデッドになりたいか

搬运于2025-08-24 22:38:22，当前版本为作者最后更新于2022-08-12 18:30:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

理解题意后，不难发现一个事实：可以把硬币分成两堆称，然后合并起来。容易证明这是无后效性的。

所以就能根据题意推出方程。设 $f_i$ 表示 $i$ 个硬币中找假币的最小代价，有：

$$f_x=\operatorname{min}_{i=1}^{x-1}\{f_i+ai+b\lceil\frac{x}{i}\rceil\} $$

根据这个式子算就好了。但是这样 1D/1D 的转移是 $O(n^2)$ 的，过不去。优化？单调队列似乎不适用于这题。

正解是找性质：发现转移的时候出现 $b\lceil \frac{x}{i} \rceil$，熟悉整除分块套路的都知道可以对 $x-1$ 做整除分块。然后就显然了：对于每一块，取最左端点肯定是最优的。所以转移的时候只要转移每一块的左端点即可。

$x$ 范围很大，数组存不了。不过很容易发现，$x$ 是很稀疏的。但用 map 会带一个 $\log$ 铁定过不去；赛时出现了 unordered_map 通过的提交，但是赛后被出题人卡掉了。官方题解的解决方案是：使用特殊的方式把 $x$ 映射到坐标 $v$：

$$v(x)=\begin{cases} x & x\leq\lfloor\frac{n-1}{x}\rfloor\\ k+\lfloor\frac{n-1}{x}\rfloor & x>\lfloor\frac{n-1}{x}\rfloor \end{cases}$$

$k$ 是一个常数，取值范围大约在 $[\sqrt n,\inf)$，官方取的是 $10^5$。

有没有更优美的做法？其实有：C++ pbds 里有一个比 unordered_map 效率更高的容器 hash_table，用哈希值存储元素，平均下是 $O(1)$ 的。使用方式：

• 头文件（有两个）：

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

• 命名空间：using namespace __gnu_pbds;。

• 声明方式：有两种哈希表：

cc_hash_table<int,int> cc;//链表
gp_hash_table<int,int> gp;//开放寻址

一般开放寻址会快一点，效率瓶颈主要是在处理哈希冲突的方式上。虽然如此，由于这题的特殊性质，使用链表哈希表会更快一些（最慢测试点比开放寻址法快了约 500ms）。

然后就可以用记忆化搜索通过本题了。略微卡常后最慢的点能跑进 $0.8$ 秒，也算是稳定的了。

#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
// 省略快读模板
using namespace fastio;
ll n,a,b;
cc_hash_table<ll,ll> gp;//关键
cc_hash_table<ll,ll> pre;//关键
ll dp(ll x){
	auto at=gp.find(x);
	if(at!=gp.end())return at->second;
	ll ans=0x7fffffffffffffffll;
	ll N=x-1,p;
	for(ll L=1,R;L<=N;L=R+1){//整除分块
		R=N/(N/L);
		ll cur=dp(L)+(N/L+1)*b+x*a;
		if(cur<ans)ans=cur,p=L;
	}
	pre[x]=p;
	return gp[x]=ans;
}
const int maxn=10000000+5;
ll path[maxn],loc;
int main(){
	cin>>n>>a>>b;
	gp[1]=0,dp(n);
	int cur=n,v;
	while(v=pre[cur])path[++loc]=v,cur=v;
	wr(gp[n],' '),wr(loc);//wr 是快读输出函数
	for(int i=1;i<=loc;i++)wr(path[i],' ');
	io::flush();//快读刷新缓冲区
	return 0;
}