脚本宝典收集整理的这篇文章主要介绍了第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
F.Fireworks
思路：
由于是最优策略，所以并不是单纯的求期望，而再分析下题目，说做一个烟花是n分钟，放所有烟花是m分钟，那对于最优策略我们可以求一个k，表示每制作k个烟花放一次，那么每一轮时间花费就是k * n + m，由于成功的概率是p，所以失败的概率是(1 - p)，因此至少有一个成功的烟花的概率就是(1 - (1 - p) ^ k)，显然这是一个几何分布，所以期望就为1 / (1 - (1 - p) ^ k)，表示进行了多少轮，再乘以每一轮的时间花费就是
(k * n + m) / (1 - (1 - p) ^ k)
求二阶导可知这是一个单峰函数，所以可以三分出答案
然后就是要注意开long double，输出long double 的时候是%Lf
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <map> #include <unordered_set> #include <unordered_map> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 200010; const double PI = acos(-1); int n, m; long double p; long double f(int k)//(k*n+m) / (1-(1-p)^k) { return 1.0 * (k * n + m) / (1 - pow(1 - p, k)); } int main() { IOS; int T = 1; cin >> T; while(T -- ) { cin >> n >> m >> p; p *= 1e-4; int l = 1, r = 0x3f3f3f3f; while(l < r) { int mid = l + (r - l) / 3, midmid = r - (r - l) / 3; if(f(mid) < f(midmid)) r = midmid - 1; else l = mid + 1; } printf("%.10Lfn", f(l)); } return 0; }
L.Let's Play Curling
思路：
题目中说找到一个c很具有迷惑性，其实具体思路就是在两个b之间找到最多数量的a，我们可以用lower_bound来做，因此我们可以先排序，然后找出所有连续的两个b之间的a的数量，但需要注意的是，我们还需要考虑第一个b之前是否有一些a和最后一个b之后是否有一些a，因此我们可以先在原b数组增加两个数，一个最小值一个最大值然后再找
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <vector> #include <map> #include <unordered_set> #include <unordered_map> #define x first #define y second #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 100010; const double PI = acos(-1); int a[N], b[N]; int main() { IOS; int T = 1; cin >> T; while(T -- ) { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int i = 1; i <= m; i ++ ) cin >> b[i]; b[++m] = 0, b[++m] = 0x3f3f3f3f; sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + m); int res = 0; for (int i = 1; i <= m; i ++ ) { int l = lower_bound(a + 1, a + 1 + n, b[i] + 1) - a;//下标 int r = lower_bound(a + 1, a + 1 + n, b[i + 1]) - a;//下标 res = max(res, r - l); } if(res > 0) cout << res << endl; else cout << "Impossible" << endl; } return 0; }
以上是脚本宝典为你收集整理的第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）全部内容，希望文章能够帮你解决第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。