当前位置：首页 > web >正文

Codeforces Round 1043 (Div. 3)

web 2025/8/24 18:00:09

The Cunning Seller (hard version)

第一段：把 nnn 拆成 3 的幂和（相当于三进制）

for(int i=0;n>0;i++) { while(n%3) { n-=1; mn+=1; use[i]++; } n/=3; }

这段等价于把 nnn 写成三进制：
n=∑di⋅3in=\sum d_i \cdot 3^in=∑di⋅3i，其中 di∈{0,1,2}d_i\in\{0,1,2\}di∈{0,1,2}。

对第 i 位：n%3 是这一位的值（1 或 2）。
while(n%3){ n--; use[i]++; mn++; }：把这位的余数“扣掉”并记在 use[i]，相当于用了 d_i 次“买 3i3^i3i”的交易。这样处理完后该位变成 0。
然后 n/=3，进入更高一位。

因此循环结束后：

use[i] = d_i（三进制每一位就是用了多少个 3i3^i3i 的交易）；
mn = sum d_i：能凑出 n 的最少交易数。

可行性判定

if(mn>k){ cout<<-1; return; }

若最少交易数都超过 k，必然不可能，直接 -1。

第二段：计算还能“拆分”的预算

ll t=(k-mn)/2;

一次拆分指：把 1 个“买 3i3^i3i”的交易，换成 3 个“买 3i−13^{i-1}3i−1”的交易：

交易数从 1 变 3，+2 次交易；
买到的西瓜总数不变（仍是 3i3^i3i）；
费用会下降（见下节）。

由于每次拆分会额外消耗 2 次交易额度，因此最多可拆分次数是

t=⌊k−mn2⌋.t=\left\lfloor \frac{k-mn}{2}\right\rfloor.t=⌊2k−mn⌋.

第三段：从高位到低位贪心拆分（为什么这样最省钱）

for(int i=use.size()-1;i>0;i--){ ll b=min(t,use[i]); // 在第 i 位最多拆 b 次 use[i]-=b; use[i-1]+=3*b; t-=b; // 消耗 b 次“拆分配额” }

为什么拆分会降费？

设“买 3i3^i3i”的费用为 cic_ici。题意给的价格化成通用式是

ci={3,i=03 i+1+i⋅3 i−1,i≥1c_i= \begin{cases} 3, & i=0\\ 3^{\,i+1}+i\cdot 3^{\,i-1}, & i\ge 1 \end{cases}ci={3,3i+1+i⋅3i−1,i=0i≥1

把 1 个 3i3^i3i 拆成 3 个 3i−13^{i-1}3i−1 的费用差：

ci−3ci−1=(3i+1+i3i−1)−3(3i+(i−1)3i−2)=3i−1 > 0.c_i - 3c_{i-1} = \big(3^{i+1}+i3^{i-1}\big) - 3\big(3^{i}+(i-1)3^{i-2}\big) = 3^{i-1} \;>\; 0.ci−3ci−1=(3i+1+i3i−1)−3(3i+(i−1)3i−2)=3i−1>0.

也就是说：单买 1 个 3i3^i3i 比买 3 个 3i−13^{i-1}3i−1 贵 3i−13^{i-1}3i−1 金币。所以拆分一次就能省下 3i−13^{i-1}3i−1 金币。

为什么“从高到低拆”是最优？

一次拆分能省的钱是 3i−13^{i-1}3i−1，随 iii 单调增。
在“可拆分次数 t 固定”的前提下，要最大化总节省，自然应该优先用在最大的 iii 上（贪心正确性可用交换论证：若存在最佳解中先拆小位，改成先拆高位不会变差）。

于是代码从 i=最高位 往下，把能拆的都拆（受限于 t 和 use[i] 的个数）。

第四段：按最终方案计算最小费用

ll res=0, x=1; // x = 3^i for(int i=0;i<20;i++) { ll c = 3*x + i*(x/3); // c_i res += use[i]*c; x *= 3; } cout<<res<<endl;

这里 x = 3^i，于是

ci=3⋅3i+i⋅3i−1=3 i+1+i⋅3 i−1.c_i = 3\cdot 3^i + i\cdot 3^{i-1} = 3^{\,i+1} + i\cdot 3^{\,i-1}.ci=3⋅3i+i⋅3i−1=3i+1+i⋅3i−1.

当 i=0i=0i=0 时，x/3=0，得到 c0=3c_0=3c0=3。
所以这一式子统一兼容 i=0i=0i=0 与 i≥1i\ge1i≥1 情况。

把每一位的数量 use[i] 乘以对应费用 c_i 累加，就是最小总费用。

小例子快速过一遍

n=3, k=3：
三进制 10 → use[1]=1, mn=1；
t=(3-1)/2=1；
在 i=1 拆 1 次：use[1]=0, use[0]+=3；
费用 = 3 * 3 = 9（比直接用一次 313^131 的 10 更省）。
n=8, k=3：
三进制 22 → mn=4 > k，输出 -1。
n=9, k=1：
三进制 100 → mn=1，t=0，不能拆；
费用 = c2=3⋅9+2⋅3=33c_2 = 3\cdot 9 + 2\cdot 3 = 33c2=3⋅9+2⋅3=33。

复杂度与边界

三进制长度 ≤20\le 20≤20（对 n≤109n\le 10^9n≤109），每段都是 O(位数)；每组数据 O(20)O(20)O(20)。
费用与中间量均在 64 位整数范围内安全。
代码里 use 开 30，而最后费用循环到 20，n\le 1e9 实际最高位 ≤19\le 19≤19，所以也安全；更工整可以统一都用 20。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{ll n,k;cin>>n>>k;ll re=n,mn=0;vector<ll> use(30);for(int i=0;n>0;i++){while(n%3){n-=1;mn+=1;use[i]++;}n/=3;}n=re;if(mn>k){cout<<-1<<endl;return ;}ll t=(k-mn)/2;for(int i=use.size()-1;i>0;i--){ll b=min(t,use[i]);use[i]-=b;use[i-1]+=3*b;t-=b;}ll res=0,x=1;for(int i=0;i<20;i++){ll c=3*x+i*(x/3);res+=use[i]*c;x*=3;}cout<<res<<endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T=1;cin>>T;while(T--)solve();return 0;
}

查看全文

http://www.xdnf.cn/news/18729.html