UvaLive 7505 Hungry Game of Ants【dp】

题目链接:

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$

UvaLive 7504 Business Cycle【二分+模拟】

题目链接:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5523

题意:

$n$个数组成一个圆,给定每个数的值$v_i$,从$0$号元素开始加,如果加完一个数后总和变为了负数,则将总和改为0。给定最多加的元素个数$p$,问你初始值最少为多少才能在从$0$开始的$p$个数内加到$g$。
数据范围:$n \le 10^5, 1 \le g,p \le 10^{18}, v_i \le 10^9$