「2018 集训队互测 Day 2」神秘货币 题解

题目概述

这是一个交互题，我们需要通过询问来推断一个货币系统的构成。货币系统中有 $n$ 种面值的货币，其中面值 $\leq 1000$ 的是硬币，面值 $> 1000$ 的是纸币。我们需要通过调用 query(v) 询问价格 $v$ 是否能被组合出来，最终调用 answer(n, a) 提交答案。

解题思路

核心思想

根据不同的数据类型采用不同的策略：

1. 类型 1 和 2：使用质因数分解和最小公倍数的思想
2. 类型 3：处理只有一种硬币和一种纸币的情况
3. 类型 4：只有硬币的情况，使用动态规划和贪心
4. 类型 5 和 6：使用同余类和最短路思想

关键算法详解

类型 1 和 2 的解法

void sol1() {
    // 预处理质数和最小公倍数
    for(ll i=2;i<=42;i++) fir[i]=lcm(fir[i-1],i);
    
    // 生成质数列表
    for(ll i=2;i<=n;i++) if(!vis[i]) {
        for(ll j=i+i;j<=n;j+=i) vis[j]=1;
        p.push_back(i);
    }
    
    // 通过特定数值的查询来推断最小面值
    // 使用二分查找确定质因数的幂次
}

类型 3 的解法（1 硬币 + 1 纸币）

// 找到唯一的硬币面值
for(ll i=501;i<=1000;i++) if(query(i)) {
    x = i;
    // 检查是否是硬币的倍数
    for(ll j=1;j<i;j++) if(i%j==0&&query(j)) {
        x = j; break;
    }
    break;
}

// 使用大数查询确定纸币面值
ll s1 = find(x,1,d); // 二分查找满足条件的纸币面值

类型 4 的解法（只有硬币）

// 直接查询小面值
for(ll i=1;i<=n;i++) vis[i]=query(i);

// 贪心选择最小基
ll top=0;
for(ll i=1;i<=n;i++) if(vis[i]==1) {
    for(ll j=1;j+i<=n;j++) if(vis[j]) 
        vis[i+j]=2; // 标记可组合出的面值
    a[top++]=i; // 加入基
}

类型 5 和 6 的解法

void sub5() {
    // 找到所有小面值的基
    for(ll i=1;i<=n;i++) if(vis[i]!=2) {
        vis[i]=query(i);
        if(!vis[i]) continue;
        // 标记所有可组合的面值
        for(ll j=1;j+i<=n;j++) if(vis[j]) 
            vis[i+j]=2;
        a[top++]=i;
    }
    
    ll x=a[0];
    // 使用同余类最短路算法
    for(ll i=1;i<top;i++) if(a[i]<s[a[i]%x]) {
        ll d=__gcd(x,a[i]);
        // 更新同余类的最短路
        for(ll j=0;j<d;j++) 
        for(ll now=j,cc=0;cc<3;now=(now+a[i])%x) {
            cc+=(now==j);
            s[(now+a[i])%x]=min(s[now]+a[i],s[(now+a[i])%x]);
        }
    }
    
    // 二分查找大面值货币
    for(ll i=1;i<x;i++) if(s[i]>1000) {
        if(!query(min(get(mx,x,i),s[i]-x))) continue;
        // 二分确定具体面值
        while(l<=r) {
            ll mid=(l+r)>>1;
            if(query(mid*x+i)) r=mid-1,mx=mid*x+i;
            else l=mid+1;
        }
    }
}

数学原理

1. 同余类最短路：对于模 $x$ 的每个剩余类，记录能组合出该剩余类的最小值
2. Frobenius 硬币问题：当所有面值互质时，存在一个最大不可表示数
3. 基的选择：选择最小的不可由已有基表示的面值作为新的基

复杂度分析

• 查询次数：根据不同类型从 40 到 22000 次不等
• 时间复杂度：主要取决于同余类最短路和二分查找
• 空间复杂度：$O(n)$

实现技巧

1. 交互优化：尽量减少查询次数，利用已知信息推导
2. 边界处理：注意大数运算的溢出问题
3. 错误处理：确保在限制内完成所有操作

总结

本题综合运用了数论、动态规划、二分查找和交互策略，需要根据不同的数据类型采用针对性的算法。关键在于理解货币系统的数学性质，特别是同余类在组合问题中的应用。