http://codeforces.com/problemset/problem/1009/E   把n从2到5的情况都列出来会发现n每次加1 就只是在最高位加一个数字 n=2 即1 3 n=3 即1 3 8 n=5 即1 3 8 20 48 规律就是cs[k]=cs[k-1]*3-(k-2)的前缀和     #include<map>#include<stack>#incl

Problem - 1009E - Intercity Travelling 题意： 从0走到n，休息后走的第 i km 的难度为 ai ，刚开始从 a1 开始每次经过休息点重新置一 休息点的个数和分布是随机的，并且概率相同 求从 0 到 n 的难度的期望   题解： 每个点是休息点和不是休息点的概率都为0.5 第 i km的难度概率分布为， P(Xi = a1) = 0.5 (

题目：戳这里 题意：从0走到n，难度分别为a1~an，可以在任何地方休息，每次休息难度将重置为a1开始。求总难度的数学期望。 解题思路： 跟这题很像，利用期望的可加性，我们分析每个位置的状态，不管怎么休息位置1的难度永远是a1，因此其期望为a1*2^(n-1)，其他点出现a1的话，说明上一个点绝对休息过，剩下的都与其无关，也就是2^(n-2)，所有的统计起来，则a1的出现次数为2^(n-1)+(

数学题(期望+概率)CodeForces 1009E-Intercity Travelling 题目链接：E. Intercity Travelling 思路： 路程为n,给定困难度（a1~an），过程中(1~n-1)都可能有休息站，概率为1/2，如果第k点有休息站，那么下一站困难度从a1开始，否则困难度加一，求到终点困难度的期望值*2^(n-1) 推算规律 竖着看，对路