题目链接: https://atcoder.jp/contests/abc189/tasks/abc189_f.
难点在于有返回0广场时，旋转轮子次数的期望值。
【ABC189F题】代码如下：
#include
#include
using namespace std;
const int BUF = 100005;
int nCell, nMove, nBackCell;
int backCell[BUF];
void read() {cin >> nCell >> nMove >> nBackCell;
for (int i = 0;
i < nBackCell;
++i) {cin >> backCell[i];
}
}
void work() {bool isBackCell[BUF] = {
};
for (int i = 0;
i < nBackCell;
++i) {isBackCell[backCell[i]] = true;
}
double goBackP[BUF * 2], curGoBack = 0;
double ans[BUF * 2], curAns = 0;
for (int i = nCell;
i < nCell + nMove;
++i) {goBackP[i] = ans[i] = 0;
}for (int i = nCell - 1;
i >= 0;
--i) {if (isBackCell[i]) {goBackP[i] = 1.0;
ans[i] = 0;
} else {goBackP[i] = curGoBack;
ans[i] = curAns + 1;
}
curGoBack += (goBackP[i] - goBackP[i + nMove]) / nMove;
curAns += (ans[i] - ans[i + nMove]) / nMove;
if (curGoBack >= 1 - 1e-8) {cout << -1 << endl;
return;
}
}
printf("%.10lf\n", ans[0] / (1 - goBackP[0]));
}
int main() {read();
work();
return 0;
}
推荐阅读
- 游戏|2020级C语言大作业 - 小球进框
- 2022升级百度大牛带你结合实践重学C++完结无密含资料
- 牛客|牛客练习赛76
- 职场|自学Python6个月，找到了月薪8K的工作，多亏了这套学习方式
- 软件研发|V8 是什么（）
- 付费知识之数据库学习|少儿编程 | 探讨C++课程、MIT Scratch课程、python课程、Noi竞赛、蓝桥怎么引导（如何才能让小孩子飞的更高？附开发工具的下载与安装
- 洛谷|高精度算法详解 [包括高精除低精与高精除高精]
- c++|P5661 [CSP-J2019] 公交换乘
- 剑指offer第二版|剑指offer 44. 从1到n整数中1出现的次数