Menu
Article DP

UVALive 7505 Hungry Game of Ants

NodeKey

NodeKey

• 2 min read

老实说，这题我在现场赛大概写不出来。

感觉还是比较需要脑洞。

题意：
一排不同重量的蚂蚁按重量排成一排玩饥饿游戏，每只蚂蚁最开始选择一个方向，左或者右，大蚂蚁吃小蚂蚁，并且使自己增加小蚂蚁的重量，如果重量相同，左吃右。
问 n 只蚂蚁，第 k 只活到最后的方案数。

思路：

直接切入正解。
首先第k只蚂蚁必须选择左边，不然只能被吃。( $n \neq k $ )
如果想要第 k 只蚂蚁获胜，必须满足以下两个条件

  1. $ weight[ max(p_1), k ] > weight[ 0, max(p_1) ) $
  2. $ weight[ 1, min(p_2) ] <= weight( min(p_2), n ] $

其中，$ max(p_1) $ 是指，满足第一条不等式的最大的 $p_1$
同理，$ max(p_2) $ 是指，满足第二条不等式的最小的 $p_2$

而其中，只要满足第一条不等式，则 $ [1, max(p_1)) $ 的方向任意，所以数量为 $ 2^{max(p_1)-1} $ 。同时这也是 k 只蚂蚁 k 胜出 的方案数。

下面有一个关键地方，就是如何通过 k 只蚂蚁 k 胜出来推出 n 只蚂蚁 k 胜出。
让第 n-1 选择左边，方案数减少一半，但是第 n 只选择任意，方案数增加一倍。故方案数不变。
以此类推。得 $ dp[n] = \sum_{i=w}^{n-1} dp[i]$ 其中 $(w = min(sum[w] \geq sum[n] – sum[w] ) ) $
这个地方只要求一下后缀和就好了。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;

ll sum[maxn], dp[maxn], texp[maxn], tot[maxn];
int bit[maxn];

void init()
{
    texp[0] = 1;
    for (int i = 1; i < maxn; i++) {
        sum[i] = sum[i - 1] + i;
        texp[i] = texp[i - 1] * 2 % mod;
        bit[i] = lower_bound(sum, sum + i + 1, (sum[i] + 1) / 2) - sum;
    }
}

int main()
{
    int n, k, T;
    init();
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d", &n, &k);
        if (n == 1 && k == 1) {
            puts("2");
            continue;
        }
        ll s = k;
        memset(dp, 0, sizeof(dp));
        for (int i = k - 1; i >= 1; i--) {
            if (s > sum[i]) {
                tot[k] = dp[k] = texp[i + 1];
                break;
            }
            s += i;
        }
        for (int i = k + 1; i <= n; i++) {
            int tmp = bit[i];
            if (tmp - 1 >= k)
                dp[i] = ((tot[i - 1] - tot[tmp - 1]) % mod + mod) % mod;
            else
                dp[i] = tot[i - 1];
            tot[i] = (tot[i - 1] + dp[i]) % mod;
        }
        printf("Case #%d: %lld\n", cas, dp[n]);
    }
    return 0;
}
Share