题解归档 - cf2231C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2231C
• 本地来源：problems/cf2231C/idea.md
• 题目链接：https://codeforces.com/contest/2231/problem/C
• 原始标题：cf2231C Chipmunk Theo and Equality

思路

cf2231C Chipmunk Theo and Equality

数学记录

• pattern: functional graph / common reachable state.
• claim: 一个数的可达最优链是确定的：偶数 x -> x/2，奇数 x -> x+1，直到进入 1 <-> 2。
• necessary: 最终相等的值必须出现在每个数的这条可达链上。
• sufficient: 枚举每个数链上的状态并累计步数；出现次数为 n 的状态都可作为最终值，取总步数最小。
• edge: 到达 1 或 2 后，还需要把另一点以 +1 步加入，因为 1 -> 2、2 -> 1 可互达。

做法

对每个 a_i 沿操作链走，把每个经过的值 x 的计数加一、代价加当前步数。走到 1/2 后，再把另一个值用 step+1 记录。

最后扫描哈希表，所有计数为 n 的值都是公共可达终点，答案是最小总代价。

验证

• python tools/run_exe.py cf2231C 通过官方样例。
• python tools/stress2.py cf2231C -n 500 --keep-fail 通过。
• fail.in 与 BFS brute 输出一致。
• n=100000 随机大输入冒烟通过。

代码

来源：problems/cf2231C/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        unordered_map<ll,pair<int,ll> > mp;
        mp.reserve(n*80);
        for(int i=1;i<=n;i++){
            ll x;
            scanf("%lld",&x);
            ll step=0;
            while(x>2){
                auto &p=mp[x];
                p.first++;
                p.second+=step;
                if(x&1) x++;
                else x/=2;
                step++;
            }
            auto &p=mp[x];
            p.first++;
            p.second+=step;
            x=3-x;
            auto &q=mp[x];
            q.first++;
            q.second+=step+1;
        }
        ll ans=(1LL<<62);
        for(auto &it:mp){
            if(it.second.first==n) ans=min(ans,it.second.second);
        }
        printf("%lld\n",ans);
    }
    return 0;
}