C. Omsk Programmers 题解

C. Omsk Programmers 题解思路操作有两种给a或b加1把a或b变成floor(value / x)。关键结论对任意一个数如果一段操作里一共做了k次除法和若干次1那么这些1都可以放到所有除法之后做答案不会变差。原因是一次1如果放在后续除法之前它对最终结果的贡献最多也只是让最终值增加1把它放到最后同样花费一次操作至少不会更差。所以对于一个初始值n我们只需要考虑n, floor(n / x), floor(n / x^2), ...如果做了i次除法当前值是A_i floor(a / x^i)如果做了j次除法当前值是B_j floor(b / x^j)。之后只需要把较小的那个数加到较大的那个数总代价为i j abs(A_i - B_j)因此枚举a和b重复除以x后能得到的所有值取上式最小值即可。因为a, b 10^9且x 2每个数最多只会产生约30个不同层级所以直接双重枚举即可。正确性证明引理 1固定一个初始值n如果某个操作序列中有k次除法和m次加一操作并且最终得到y那么存在另一个操作序列先做k次除法再做若干次加一操作花费不超过原序列并且也能得到y。证明先只看这k次除法不做任何加一操作最终值为floor(n / x^k)。原序列中的每次加一操作即使放在除法之前它对最终值的提升也最多为1。所以如果原序列最终得到y必然有y floor(n / x^k) y - floor(n / x^k) m于是我们可以先做k次除法再做y - floor(n / x^k)次加一操作花费不超过k m。引理成立。引理 2若a做i次除法得到A_ib做j次除法得到B_j那么在这两个除法次数固定时最小额外加一次数是abs(A_i - B_j)。证明除法结束后两个数分别是A_i和B_j。之后只能加一所以最终公共值不能小于二者最大值。取公共值为max(A_i, B_j)时较小者加到较大者花费正好是max(A_i, B_j) - min(A_i, B_j) abs(A_i - B_j)这是最小的。定理答案等于min(i j abs(A_i - B_j))其中A_i floor(a / x^i)B_j floor(b / x^j)。证明由引理 1存在最优方案使得每个数都是先做若干次除法再做若干次加一操作。设最优方案中a做了i次除法b做了j次除法。由引理 2在这组i, j固定时最优代价就是i j abs(A_i - B_j)枚举所有可能的i, j并取最小值就一定能得到全局最优答案。复杂度每个数最多被除到0层数为O(log_x n)。单个测试用例复杂度O(log_x a * log_x b)在本题范围内最多约31 * 31次枚举。C17 代码#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cint;while(t--){longlonga,b,x;cinabx;vectorpairlonglong,longlongva,vb;longlongcura;for(longlongcnt0;;cnt){va.push_back({cur,cnt});if(cur0)break;cur/x;}curb;for(longlongcnt0;;cnt){vb.push_back({cur,cnt});if(cur0)break;cur/x;}longlongansllabs(a-b);for(auto[av,ai]:va){for(auto[bv,bi]:vb){ansmin(ans,aibillabs(av-bv));}}coutans\n;}return0;}