题目链接(洛谷)

题目大意

\(n(n\le 10000)\)种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是购买,每次只能买一张,并且买到的邮票究竟是\(n\)种邮票中的哪一种是等概率的,概率均为\(\frac{1}{n}\)。购买第\(k\)次邮票需要支付\(k\)元钱。

求得到所有种类的邮票需要花费的钱数目的期望。

阅读全文 »

题目链接(洛谷)

题目大意

给出\(n(1\le n \le 5\times 10^5)\)个点和\(n-1\)条连着它们的路径,每一条道路都连接某两个点,且通过这些道路可以走遍所有的点。

\(m(1 \le m \le 10^5)\)组人分散在这些点上,每组有三个人。给出每组中三人的初始位置。每组确定一个位置使每组内三人到这个点的距离和最小,输出这个距离和。

阅读全文 »

题目链接(洛谷)

题目大意

\(n\)个城市\(m\)条道路,每条道路连接这\(n\)个城市中的某两个城市。任意城市之间最多只有一条道路相连。

\(m\)条道路中有一部分为单向通行的道路,一部分为双向通行的道路。双向道路在统计时记为一条。

同一商品在不同城市价格\(c\)不同,但同一商品在城市中的买入和卖出价格是相同的。商人想要通过赚差价赚出旅费,且他只进行一次贸易,求最多能赚多少。

$$

1n ,~1m

$$

阅读全文 »

题目链接(洛谷)

题目大意

给出一个有\(n\)个节点\(m\)条边的无向图,节点编号为\(1-n\),边编号为\(1-m\)。初始时小E同学在\(1\)号节点。数据可能包含重边和自环。

每条边都有一个妖怪住在边上。在节点\(1\)处有两种守护精灵A,B,每种都有无数个。无向图中每条边都有权值\(a_i\)\(b_i\),当且仅当小E身上携带的A守护精灵不少于\(a_i\),且B守护精灵不少于\(b_i\),这条边上的妖怪不会对通过这条边的人发起攻击。

求在不被妖怪袭击的情况下,到\(n\)号节点最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。

\(2\le n \le 50000, 0\le m \le 100000, 1\le a_i,b_i \le 50000\)

阅读全文 »

题目链接(洛谷)

题目大意

小a在一座雪山滑雪,这里分布着\(m\)条供滑行的轨道和\(n\)个轨道之间的交点(同时也是景点),而且每个景点都有一个编号\(i\)和一个高度\(h_i\) 。给出每条轨道的长度\(k_i\)小a能从景点\(i\)滑到景点\(j\)当且仅当存在\(i\)\(j\)之间的边,且\(i\)的高度不小于\(j\)

阅读全文 »
0%