https://vjudge.net/contest/439155
C - Pocky
题意:给定一个长为 L 的棍子,当棍子长度小于等于 d 时停止操作,每次操作随机选择一个位置切开,扔掉左部分,在右部分上继续操作。问期望操作次数。
积分方程
设长度为 x 时的期望操作次数为 f(x).
则有
⟹⟹f(x)=x∫dxf(t)dt+1f′(x)=x2xf(x)−∫dxf(t)dt∫dxf(t)dt=xf(x)−x2f′(x)
由原式得 ∫dxf(t)dt=xf(x)−1
所以有
⟹⟹xf(x)−1=xf(x)−x2f′(x)f′(x)=x1f(x)=lnx+C
代入 f(d)=1 得
⟹⟹⟹f(d)=lnd+C=1C=1−lndf(x)=lnx+1−lndf(x)=1+lndx
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| #include<bits/stdc++.h> #define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i) #define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i) #define per(i, l, r) for (int i = l, i##end = r; i >= i##end; --i) using namespace std;
const int N = 2e6; int T;
int main(){ scanf("%d", &T); while(T--){ double x, y; scanf("%lf%lf", &x, &y); if (x <= y) puts("0.000000"); else printf("%.6f\n", 1+ log(x / y)); } return 0; }
|
K - Finding Hotels
题意:给定二维平面上 n 个点,每点有坐标和 c[i] 值,m 次询问,每次给定一个询问点,有坐标和 c 值,问 c 值小于等于询问点的最近的给定点。
K-D树
最近点的问题显然是KD树,但是本题还有 c 值的限制。
把 c 作为第三维,查询时若节点的第三维大于查询,则规定距离为无穷大。
KD树的复杂度比较玄学,用nth_element找中位数的复杂度期望 O(n),则建树复杂度为 O(nlogn),但如果sort,则根据主定理的拓展,复杂度就是 O(nlog2n),而单次查询最近点的复杂度为 O(n1−k1).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long #define ull unsigned ll const int N = 2e6 + 10; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; const ll inv2 = (mod + 1) / 2; const double eps = 1e-8; const double PI = acos(-1); int T; int n, m; #define DIM 3 int d[DIM]; int cmp_d, root; struct P { int id; ll d[DIM], mx[DIM], mn[DIM]; int lc, rc; }a[N]; bool cmp(P a, P b) { return a.d[cmp_d] < b.d[cmp_d]; } void up(int u, int v) { for (int i = 0; i < DIM; i++) { a[u].mn[i] = min(a[u].mn[i], a[v].mn[i]); a[u].mx[i] = max(a[u].mx[i], a[v].mx[i]); } } int build(int l, int r, int D) { cmp_d = D; int mid = (l + r) / 2; nth_element(a + l + 1, a + mid + 1, a + r + 1, cmp); for (int i = 0; i < DIM; i++)a[mid].mn[i] = a[mid].mx[i] = a[mid].d[i]; if (l != mid)a[mid].lc = build(l, mid - 1, (D + 1) % DIM); else a[mid].lc = 0; if (r != mid)a[mid].rc = build(mid + 1, r, (D + 1) % DIM); else a[mid].rc = 0; if (a[mid].lc)up(mid, a[mid].lc); if (a[mid].rc)up(mid, a[mid].rc); return mid; } int idx; ll dis; ll getdis(int p) { ll res = 0; if (a[p].d[2] > d[2])return inf + 1; for (int i = 0; i < 2; i++) { if (d[i] < a[p].mn[i])res += (d[i] - a[p].mn[i])*(d[i] - a[p].mn[i]); if (d[i] > a[p].mx[i])res += (d[i] - a[p].mx[i])*(d[i] - a[p].mx[i]); } return res; } void qry(int p) { ll d0 = 0, dl = inf + 1, dr = inf + 1; if (a[p].d[2] <= d[2]) { for (int i = 0; i < 2; i++) { d0 += (d[i] - a[p].d[i])*(d[i] - a[p].d[i]); } if (d0 < dis) { dis = d0; idx = p; } else if (d0 == dis) { if (a[idx].id > a[p].id)idx = p; } } if (a[p].lc)dl = getdis(a[p].lc); if (a[p].rc)dr = getdis(a[p].rc); if (dl < dr) { if (dl <= dis)qry(a[p].lc); if (dr <= dis)qry(a[p].rc); } else { if (dr <= dis)qry(a[p].rc); if (dl <= dis)qry(a[p].lc); } } int main() { scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &a[i].d[0], &a[i].d[1], &a[i].d[2]); a[i].id = i; } root = build(1, n, 0); while (m--) { scanf("%d%d%d", &d[0], &d[1], &d[2]); dis = inf; qry(root); printf("%lld %lld %lld\n", a[idx].d[0], a[idx].d[1], a[idx].d[2]); } } return 0; }
|
D - Lucky Coins
题意:有 n 种硬币,每种有 ai 个,正面向上的概率为 pi。不断重复:同时扔所有硬币并扔掉所有反面向上的硬币,直到只剩下一种硬币。问对于每种硬币,最后只剩下它的概率。
设 dp[i][j] 表示到第 i 轮,第 j 种硬币还有存活的概率。
dp[i][j]=(1−p[j]i)a[j].
枚举到 100 轮,可以近似估计答案。
在第 i 轮,只有第 j 种硬币存活的概率等于 dp[i][j]⋅1≤k≤n,k=j∏(1−dp[i][k])。
但是这样直接求和会导致重复,因为除了 j 以外的硬币可能在第 i 轮以前就全部扔掉了,也就是说游戏并不能进行到第 i 轮。
假设现在处于第 1 轮,第一轮除 j 之外所有硬币都死亡的概率为 1≤k≤n,k=j∏(1−dp[1][k]),设为 S,则 j 在第一轮胜出的概率为 dp[1][j]⋅S。在计算第二轮时,S 同样可能出现,要把这种情况从答案里去掉,所以要减去 dp[2][j]⋅S,不需要再继续减了,因为这种情况在第二轮不出现,第三轮就更不会出现。
以此类推,在第 j 种硬币获胜的概率为 i=1∑100(dp[i][j]−dp[i+1][j])⋅1≤k≤n,k=j∏dp[i][k].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long #define ull unsigned ll const int N = 2e6 + 10; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; const ll inv2 = (mod + 1) / 2; const double eps = 1e-8; const double PI = acos(-1); int T; int n; int a[20]; double p[20], dp[110][20]; int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &a[i]), scanf("%lf", &p[i]); if (n == 1) { puts("1.000000"); continue; } for (int i = 1; i < 110; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = 1.0 - pow(1.0 - pow(p[j], i), a[j]); } } for (int i = 1; i <= n; i++) { double ans = 0; for (int j = 1; j <= 100; j++) { double tmp = 1; for (int k = 1; k <= n; k++) { if (k == i)tmp = tmp * (dp[j][i] - dp[j + 1][i]); else tmp = tmp * (1 - dp[j][k]); } ans += tmp; } printf("%.6f%c", ans, " \n"[i == n]); } } return 0; }
|