题目链接：
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5527
题意：
已知$n$个蚂蚁初始排列在一条直线，第$i$只蚂蚁位于距离左端点$i$个单位的位置，重量为$i$千克。现每只蚂蚁随机选择向左或向右，以相同的速度前进，遇到端点则掉头，两只蚂蚁相遇时，重量大的蚂蚁吃掉重量小的蚂蚁，如果两只蚂蚁重量一样则左边来的吃掉右边的。问最后有多少种情况最后只有第$k$只蚂蚁存活。
数据范围：$1 \le n \le 10^6$
分析：
对于目标第$k$号蚂蚁，初始必须向左，且要吃掉左边所有蚂蚁。
考虑$i属于[1,k]$，假设最终$[1,i)$构成一只大蚂蚁$A$，$[i,k]$构成一只大蚂蚁$B$，$B$吃掉$A$，为包含所有情况我们要找到最大的$i$使得$\sum_{j=1}^{i} j\le \sum_{j = i+1}^{k-1}j$。其中$[1,i)$之间的蚂蚁随便走，第$i$号蚂蚁必须向左走，$(i,k)$之间的蚂蚁不能乱走必须向右走，方案数为$2^{i-1}$。
现在$k$号蚂蚁和其左边所有蚂蚁构成了一只大蚂蚁，且向右走。
考虑$i属于(k, n]$，假设$i$向左走，$j属于(k,i]$，假设最终$[k,j)$构成一只大蚂蚁$A$，$[j,i]$构成一只大蚂蚁$B$，$A$吃掉$B$。
若设$dp[i]$表示$i$向左走且$[1,i]$之间的蚂蚁都被$k$号蚂蚁吃掉的方案数，不同的$j$表示将$[k,i]$之间的蚂蚁最终分成两只不同大蚂蚁，那么对于该$i$我们要找到最小的$j$使得$\sum_{a=1}^{j-1} a \le \sum_{a=j}^{i}a$，则$dp[i] = \sum_{a=j}^{a=i-1}dp[a]$。
最后求出$dp[n]$，由于第$n$只蚂蚁可以向右走，因此答案即为$dp[n] \times 2$。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| > File Name: ecfinal.cpp > Author: jiangyuzhu > Mail: 834138558@qq.com > Created Time: 2016/12/4 18:27:36 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<set> #include<map> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 1e6 + 5, mod = 1e9 + 7; ll dp[maxn]; ll two[maxn]; ll pre[maxn]; int n, k; void init() { two[1] = 2; pre[1] = 1; for(int i = 2; i < maxn; ++i){ two[i] = two[i - 1] * 2 % mod; pre[i] = pre[i - 1] + i; } } int main (void) { int T;scanf("%d", &T); init(); for(int tt = 1; tt <= T; ++tt){ scanf("%d%d", &n, &k); if(n == 1 && k == 1){ printf("Case #%d: 2\n", tt); continue; } memset(dp, 0, sizeof(dp)); int t1; for(t1 = 1; t1 <= k; ++t1){ if(pre[t1] >= pre[k] - pre[t1]) break; } ll ans = two[t1 - 1]; dp[k] = ans; int l = k; for(int i = k + 1; i <= n; ++i){ while(l < i && pre[l] < pre[i] - pre[l]) ans = (ans - dp[l++] + mod) % mod; dp[i] = ans; ans = (ans + dp[i]) % mod; } printf("Case #%d: %lld\n", tt, dp[n] * 2 % mod); } return 0; }
|
