来追梦-D1295 小F过河

永恒的久其六亿 發表於 2025-10-11 15:39:00

<h1 id="前言">前言</h1>
依旧是固定的前言。 
拿下了第四名，和第三名同分结果提交次数多了。 
发现第三名是我的同学并且比我弱之后大胆猜测他使用的奇怪的方法。 
结果看了他T3的代码，的确如此，他居然转移的时候只转移前面和后面的 \(500\) 个，然后数据太水过了。 
显然是在模仿CCF，数据也太好了（确信。
话不多说，我的得分情况：90+100+20+0=210，第一题没有做出来挺离谱的，所以我写T2题解 
接下来开始我们的正题
<h1 id="题目意思">题目意思</h1>
你现在有两种操作，一种是将你现在手持的数字加上 \(x_1\) 耗费 \(c_1\) 的价值，另一种是将手持的乘上 \(x_2\) 耗费 \(c_2\) 的价值，要你从 \(1\) 变到 \(N\) 的最小价值，如果不行就报告不可能。
<h1 id="题目思考">题目思考</h1>
这是我在草稿纸上面的思路： 
首先我们可以将多次的加合并为 \(+ tx_1\)，多次的乘合并为 \(\times x_2^t\) 
我尝试证明操作序列为 \(+ \times +\) 或者 \(\times + \times\)，但是发现不能证明，所以这说明他可能进行了若干次 \(+ \times\) 的操作，所以不妨设我们依次进行了 \(n_1\) 次 \(+\) 操作，\(m_1\) 次 \(\times\) 操作，\(n_2\) 次 \(+\) 操作，\(m_2\) 次 \(\times\) 操作，以此类推。 
此时我们考虑他的最终数字，经过 \(n_1\) 次 \(+\) 操作后变为 \(1+n_1x_1\)，经过 \(m_1\) 次操作后变为 \((1+n_1x_1)x_2^{m_1}\)，经过 \(n_2\) 次 \(+\) 操作，\(m_2\) 次 \(\times\) 后变为
<div class="math display">\[((1+n_1x_1)x_2^{m_1}+n_2x_1)x_2^{m_2}
\]</div><div class="math display">\[=x_2^{m_1+m_2}+n_1x_1x_2^{m_1+m_2}+n_2x_1x_2^{m_2}
\]</div><div class="math display">\[=x_2^{m_1+m_2}+x_1(n_1x_2^{m_1+m_2}+n_2x_2^{m_2})
\]</div><div class="math display">\[=x_2^t+x_1(n_1x_2^{t-1}+n_2x_2^{t-2}+\cdots)
\]</div>接下来式子就化的差不多了，我们去看经过这些操作时候他的代价是多少，经过 \(n_1\) 次 \(+\) 操作，\(m_1\) 次 \(\times\) 操作后，代价是 \(n_1c_1+m_1c_2\)，现在还看不出什么，但经过 \(n_2\) 次 \(+\) 操作，\(m_2\) 次 \(\times\) 后，代价变为 \(n_1c_1+m_1c_2+n_2c_1+m_2c_2=(n_1+n_2)c_1+(m_1+m_2)c_2\) 然后观察 \(c_1\) 前面的系数，发现 \((n_1+n_2)\) 就是最后变成的数字里面，含有 \(x_1\) 的项前面的系数！观察 \(c_2\) 的系数，发现 \((m_1+m_2)\) 就是最高次项的次数，也就是所谓的 \(t\)，所以正确思路就出来了。
<h1 id="思路">思路</h1>
我们发现 \(x_2^{m_1+m_2}\le n\) 所以我们枚举 \(m_1+m_2\) 的值，除非 \(x_2=1\) 这个值必然小于 \(64\)，所以首先我们特判 \(x_2\) 的值，接着我们对于每一个枚举的 \(m_1+m_2\)，\(c_2\) 的贡献已经固定了，所以我们要使 \(c_1\) 的贡献尽量小，观看式子 \(x_1x_2^t>x_1x_2^{t-1}\) 所以我们要让 \(x_1x_2^t\) 的系数尽可能大，接着是 \(x_1x_2^{t-1}\) 的系数尽可能大，这样就能让系数之和尽可能小了，具体的可以尝试借助代码理解，我就使用了 \(int128\) 存储，不然可能炸掉。
<h1 id="代码">代码</h1>
<pre><code class="language-cpp">#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cmath>
#define ll __int128

using namespace std;
const ll Inf=0x3f3f3f3f3f3f3f3f,N=1e5+9;
ll n,x,xx,c,cc,a,ans;

int main(){
int garbage,T;
cin>>garbage>>T;
while(T--){
long long inputn,inputx,inputc,inputcc,inputxx;
cin>>inputn>>inputx>>inputc>>inputxx>>inputcc;
n=inputn;x=inputx;c=inputc;xx=inputxx;cc=inputcc;
 if(xx<=1){
if(x==0){
cout<<"-1\n";
continue;
}
 if((n-1)%x==0) cout<<(long long)(c*(n-1)/x)<<endl;
 else cout<<"-1\n";
 continue;
}
ll cnt=1;a=1;ans=Inf;
while(a<=n) a=a*xx,cnt++;
cnt--;
for(int i=cnt;i>=0;i--){
ll nn=n-a,nans=i*cc;
if(nn<0) continue;
for(int j=i;j>=0;j--){
if(a>(n+x-1)/x) continue;
if(nn>=x*a){
ll tmp=nn/(x*a);
nans+=tmp*c;
nn%=(x*a);
}
}
if(nn!=0) continue;
ans=min(ans,nans);
}
if(ans==Inf) cout<<"-1\n";
else cout<<(long long)ans<<endl;
}
return 0;
}
</code></pre>
<h1 id="后记">后记</h1>
剩下的就是这个题目的思考了，写完了我仍然十分震撼我做出了这个题目，每一步仿佛都是机缘巧合，但是最后我还是死磕出来了，挺幸运的吧，如果下次没有这么幸运的话我还是希望我能通过我的努力把这种题目做出来，总结一下，以后遇到这种题目要愿意去推式子，求价值，不要怕就好了。 
来源：https://www.cnblogs.com/zhongyq-with-yuanqiu/p/19007855

頁: [1]

琼殿技术论坛's Archiver

来追梦-D1295 小F过河