CF912E Prime Gift

· · 题解

这道题的核心就是一个叫做 meet-in-the-middle 的算法。

meet-in-the-middle，就是中途相遇法，其实就是一种搜索的方法。

比如说对于这道题给你 16 个素数，

你可以先搜 8 个素数，把所有乘积存在一个数组 A 中。

接着再搜另外 8 个素数，把所有乘积存在另一个数组 B 中。

最后，再利用二分答案的思想，

将 A 数组与 B 数组中的统计结果结合出来得到答案。

模拟赛出题时发现了这道题，刚好是运用了二分答案的。

二分答案的思想与上半年的绍兴市复赛的 T3 很像（那次 Licykoc dalao 去了 APIO）。

meet-in-the-middle 这个算法也在以前的模拟赛中做过。

加上 CF 2400 的难度，有做我的模拟赛 T4 的风范。

搜索的部分应该不用我讲了。

主要时搜完之后的二分部分。

二分答案搜所有 A 数组中的数字和 B 数组中的数字的乘积中第 k 小的那一个数。

先把二分的板子放在这儿：

long long l=0,r=1e18;
while (l<r) {
    long long mid=(l+r)>>1;
    if (check(mid)>=k) r=mid; // check(mid) 表示小于等于 mid 的乘积有几个
    else l=mid+1;
}

接着让我们关注一下 check 函数。

我们可以用 two-pointers 的方法。

首先将 A 数组，B 数组排序并去重。

首先 i 指针来枚举 A 数组：

for(int i=1;i<=lenA;i++)

里面可以再套一个指针 j，来枚举 B 数组。

因为 A 数组是从小到大排的，乘积相等（可以看作都是 mid），所以 j 指针肯定是递减的。

可能还是不太懂，看看代码就懂了。

inline long long check(long long mid) {
    long long ans=0; int j=lenB;
    for(int i=1;i<=lenA;i++) {
        while (j>0&&B[j]>mid/A[i]) j--; // j 表示一个数为 A[i] 时，另一个数 B[j] 最大时（满足 B[j]*A[i]<=mid）的下标
        ans+=1ll*j;
    }
    return ans; // ans 表示小于等于 mid 的乘积有几个
}

于是这道题就解决了。

其实放在 CSP-J 模拟赛中也不会被群殴。

Talk is cheap, show your code!

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define REP(a,b,c) for(int a=b;a<=c;a++)
int n,a[110],k;
LL A[5000010],B[5000010];
int lenA=0,lenB=0;
inline void dfs1(int x,LL s) {
    A[++lenA]=s;
    if (x>n) return ;
    for(LL i=1;;i*=a[x]) {
        if (1e18/i<s) break;
        dfs1(x+2,s*i);
    }
}
inline void dfs2(int x,LL s) {
    B[++lenB]=s;
    if (x>n) return ;
    for(LL i=1;;i*=a[x]) {
        if (1e18/i<s) break;
        dfs2(x+2,s*i);
    }
}
inline LL check(LL mid) {
    LL ans=0; int j=lenB;
    REP(i,1,lenA) {
        while (j>0&&B[j]>mid/A[i]) j--;
        ans+=1ll*j;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n; REP(i,1,n) cin>>a[i]; cin>>k;
    sort(a+1,a+n+1);
    dfs1(1,1); dfs2(2,1);
    LL l=0,r=1e18;
    sort(A+1,A+lenA+1);
    sort(B+1,B+lenB+1);
    lenA=unique(A+1,A+lenA+1)-A-1;
    lenB=unique(B+1,B+lenB+1)-B-1;
    while (l<r) {
        LL mid=(l+r)>>1;
        if (check(mid)>=k) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}

完结撒花! の_^