传送门酱:E Prime Gift
题意:给定一个集合
$$S = \{x|x=p_1^{k_1}p_2^{k2}..p_n^{k_n}, k_i \in N_+\}$$
其中$p_i$是给定的素数,$n<=16$,求这个集合里的第$k$小元素,保证这个数小于$10^{18}$

(抱着今天的CF网络咕咕+B题被Hack的咕咕心态来补之前的题QAQ)
首先二分答案是很显然的,验证的话。。。我会dfs(逃
考虑如何优化验证的过程
我们并不容易发现,我们可以把16个数分成两份,然后分别dfs记录到两个数组里,接着用双指针来计数就行了。(就是一个meet in the middle的思想)
现在就出现了一个问题,怎么分会不超时。
直觉告诉你肯定是平均分成两份舒服啦,而且要分得尽量平均(我的代码是第奇数个数为一组,第偶数个数为一组)
接着就要验证这样分会不会超时的问题。
易知笔算是没有用的,因为上下界差距太悬殊了,根本估不了,只能打代码dfs
经过验证,8个因子分别是$2,5,11,17,23,31,41,47$,所有小于$10^{18}$的数有$1119429$个,显然这种复杂度是可以接受的,因此我们就可以码代码了。
看了别的题解还有取前六个小一点的数一组,后10个数为一组的搞法,反正只要数字总数能接受就行。
鉴于这种东西并没有有效的用笔计算方法,因此我们要熟练掌握用meet in the middle爆搜的方法才能到考试的时候想到这样做。特别是复杂度是指数级别的时候,可以用这样的办法减少一半指数或者给指数开根号(开根号的有一个著名的栗子就是求最大团)
我感觉这篇好水呀QAQ。。。
代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define N 3000015
#define ll long long
#define up 1e18
#define int long long
int n, c[2][10], cnt1, cnt2;
ll a[N], b[N], tot1, tot2, k;
inline void dfs (bool type, int cnt, ll now, int last)
{
//  printf("%lld\n", tot1);
    if (type) b[++tot2] = now; else a[++tot1] = now;
    fo (i, last, cnt)
        if (now <= up / c[type][i])
            dfs(type, cnt, now * c[type][i], i);
}
inline bool check (ll x)
{
    ll ret = 0;
    int j = std::upper_bound(b + 1, b + tot2 + 1, x) - b - 1;
    fo (i, 1, tot1)
    {
        while (j > 0 && a[i] > x / b[j])
            --j;
        if (!j) break;
        ret += (ll)j;
    }
    return ret < k;
}
main() { 
    scanf("%lld", &n);
    fo (i, 1, n)
    {
        if (i & 1)
            scanf("%lld", &c[0][++cnt1]);
        else
            scanf("%lld", &c[1][++cnt2]);
    }
    scanf("%lld", &k);
    dfs(0, cnt1, 1, 1);
    dfs(1, cnt2, 1, 1);
    std::sort(a + 1, a + tot1 + 1);
    std::sort(b + 1, b + tot2 + 1);
    ll l = 0, r = up + 5, ans = l;
    while (l <= r)
    {
        ll mid = l + r >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1, ans = mid;
    }
    printf("%lld", ans);
    return 0;
}
分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *