Dec 252012
 

这场还是做得很糟糕。开场之后A,B,C都很快有了想法,10分钟过了A之后,剩下的时间居然都没调出来B,而且代码写的非常混乱。第二天起来一看,又掉到Div2了,好伤心。

写一下前三个的题解,后两个题比赛的时候都没看。

258A Little Elephant and Bits

很简单的贪心。 直观的想法是删除二进制串中最左的0,也很容易证明这样一定可以得到最优解。要特殊考虑一种情况,即二进制串完全由1组成。
对了,看了一下solution size排在前几名的solutions,有用haskell,ruby,perl,python等各种语言写的,都很简洁。

258B Little Elephant and Elections

首先,要统计出区间[1, m]内,含有k个lucky digits的数字个数。这可以用一个简单的(按位)DP实现。我们从m的最低位开始递推。设dp[i][k]表示在区间[0, num[i] ]内,含有k个lucky digits的数字个数,其中num[i]是m的最低i位组成的数字。
如果我们要计算dp[i][k],那么只需要枚举在第i位上,放置0~9中的哪个数字。用一个例子来说明:
设m=6139,现在我们要计算dp[4][1]。我们现在枚举第四位上放置0~9中的哪个数字:
I. 放置大于6的数,显然不可能;
II. 放置6,这种情况下对应的方案数等于dp[3][1];
III. 放置小于6的数,例如5,我们注意到,这时候后三位的取值可以是000~999中的任意值。这种情况下对应的方案数是2^{1}8^{3-1}\binom{3}{1}。也就是说,我们要从这3位中选1位放置lucky digits,然后在其余的位置放置unlucky digits。
这样就解决了问题的第一部分。问题的第二部分就很简单了:我们只要枚举Political Party的lucky digits个数,然后枚举6 other parties的lucky digits个数即可。具体实现可以用DFS+回溯。
我的代码如下,不要吐槽我的代码写的很丑T T:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef __int64 lld;
const lld mod = 1e9 + 7;
const int L = 12;

lld pow_mod(lld a, lld b)
{
    if (!b)
        return 1;
    lld half = pow_mod(a, b >> 1);
    lld ret = half * half % mod;
    if (b & 1)
        ret = ret * a % mod;
    return ret;
}

lld n, res, dp[L][L];
int l, digit[L];
void dfs(int ind, int sum, int lim, lld num)
{
    if (ind == 6 && sum < lim) //complete
    {
        res = (res + num) % mod;
        return;
    }
    for (int i = 0; i < lim; ++i) //choose a num of 4/7 for this party
        if (sum + i < lim && dp[l][i] > 0)
        {
            --dp[l][i];
            dfs(ind + 1, sum + i, lim, num * (dp[l][i] + 1) % mod);
            ++dp[l][i];
        }
}

int state[L] = {0}, cn[L][L]; //combination number
void init()
{
    memset(state, 0, sizeof(state) );
    memset(cn, 0, sizeof(cn) );
    state[4] = state[7] = 1;
    for (int i = 0; i < L; ++i)
        cn[i][0] = 1;
    for (int i = 1; i < L; ++i)
        for (int j = 1; j <= i; ++j)
            cn[i][j] = cn[i - 1][j] + cn[i - 1][j - 1];
}

int main()
{
    init();

    scanf("%I64d", &n);
    memset(dp, 0, sizeof(dp) );
    l = 0;

    dp[0][0] = 1;
    while (n)
    {
        digit[++l] = n % 10;
        n /= 10;
    }
    for (int i = 1; i <= l; ++i)
    {
        for (int x = 0; x <= i; ++x)
            for (int d = 0; d <= 9; ++d) //enum cur digit
            {
                if (d == digit[i] && x >= state[d])
                    dp[i][x] += dp[i - 1][x - state[d] ];
                else if (d < digit[i] && x >= state[d] && i + state[d] >= x + 1)
                    dp[i][x] += pow_mod(2, x - state[d]) * pow_mod(8, i + state[d] - x - 1) % mod * cn[i - 1][x - state[d] ] % mod;
            }

    }
    --dp[l][0];

    res = 0;
    for (int lim = 1; lim < L; ++lim)
    {
        if (!dp[l][lim])
            continue;
        --dp[l][lim];
        dfs(0, 0, lim, dp[l][lim] + 1);
        ++dp[l][lim];
    }
    printf("%I64d\n", res);

    return 0;
}

258C Little Elephant and LCM

我觉得这个题要比B题好写,要是当时先做这个就好了。
我们先观察一下good sequence的含义。我们设:
lcm(b_{1}, b_{2}, ..., b_{n}) = max(b_{1}, b_{2}, ..., b_{n}) = k
那么很容易发现,b_{1}, b_{2}, ..., b_{n}必然都是k的因子,而且其中至少有一个数等于k(否则这些数的最大值就不是k了)。
观察到这一点之后,做法就比较明显了。对于给定的上界a_{1}, a_{2}, ..., a_{n},我们首先枚举k的值。之后,将k的因子从小到大排序,设为f_{1}, f_{2}, ..., f_{t}(当然有f_{t}==k)。那么对于所有满足f_{j}\leq a_{i}<f_{j+1}a[i],它所对应的k的因子就有j种选择,即f_{1}, f_{2}, ..., f_{j}。 但是,如果我们对于每个上界a_{i}都做这样的计算,显然复杂度是无法接受的。稍微转变一下思路,我们统计出区间[f_{1}, f_{2}), [f_{2}, f_{3}), ..., [f_{t-1}, f_{t}), [f_{t}, +\infty)中各含有多少个上界,设为s_{1}, s_{2}, ..., s_{t}。这样,最终的结果就是1^{s_{1}}2^{s_{2}}...(t^{s_{t}}-(t-1)^{s_{t}})。注意最后一项是为了保证至少有一个数等于k,所以用全部方案数-每个数都小于k的方案数。 总体的复杂度是O(Nlog^{2}N)。在具体实现的时候,可以先预处理出[1, 10^{5}]区间内所有数的因子并排好顺序。我们可以借助筛法的思想很容易的实现预处理,代码如下:

for (int i = 1;i < N;++i)
        for (int j = i;j < N;j += i)
            factor[j].push_back(i);

完整代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef __int64 lld;
const lld mod = 1000000007;
const int N = 100005;

vector <int>factor[N];
int cnt[N], psum[N]; //partial sum

void pre()
{
    for (int i = 1;i < N;++i)
        for (int j = i;j < N;j += i)
            factor[j].push_back(i);
}

lld pow_mod(lld a, lld b) //a^b % mod
{
    if (!b)
        return 1;
    lld half = pow_mod(a, b / 2);
    lld ret = half * half % mod;
    if (b & 1)
        ret = ret * a % mod;
    return ret;
}

int main()
{
    pre();
    int n, a;

    scanf("%d", &n);
    memset(cnt, 0, sizeof(cnt) );
    psum[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a);
        ++cnt[a];
    }
    for (int i = 1; i < N; ++i)
        psum[i] = psum[i - 1] + cnt[i];
    lld res = 0;
    for (int i = 1; i < N; ++i) //enum max number
    {
        int si = factor[i].size();
        lld tp = 1, tp1, tp2;
        for (int j = 0; j < si - 1; ++j)
            tp = tp * pow_mod(j + 1, psum[factor[i][j + 1] - 1]- psum[factor[i][j] - 1]) % mod;
        tp1 = tp * pow_mod(si, psum[N - 1] - psum[factor[i][si - 1] - 1]);
        res = (res + tp1) % mod;
        tp2 = tp * pow_mod(si - 1, psum[N - 1] - psum[factor[i][si - 1] - 1]);
        res = (res - tp2) % mod;
        res = (res + mod) % mod;
    }
    printf("%I64d\n", res);
    return 0;
}

  11 Responses to “CodeForces Round#157 Div1”

  1. 公式很赞,但是字体有点异样。。。看起来像是印刷的有点问题。。。

  2. ym学长。
    顺便看看有没有头像

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)