https://vjudge.net/contest/439155

C - Pocky

 

题意:给定一个长为 LL 的棍子,当棍子长度小于等于 dd 时停止操作,每次操作随机选择一个位置切开,扔掉左部分,在右部分上继续操作。问期望操作次数。

积分方程

设长度为 xx 时的期望操作次数为 f(x)f(x).

则有

f(x)=dxf(t)dtx+1    f(x)=xf(x)dxf(t)dtx2    dxf(t)dt=xf(x)x2f(x)\begin{align} &f(x)=\frac{\int_d^x {f(t)} \,{\rm d}t}{x}+1\\ \implies &f'(x)=\frac{xf(x)-\int_d^x {f(t)} \,{\rm d}t}{x^2}\\ \implies&\int_d^x {f(t)} \,{\rm d}t=xf(x)-x^2f'(x)\\ \end{align}

由原式得 dxf(t)dt=xf(x)1\int_d^x {f(t)} \,{\rm d}t=xf(x)-1

所以有

xf(x)1=xf(x)x2f(x)    f(x)=1x    f(x)=lnx+C\begin{align} &xf(x)-1=xf(x)-x^2f'(x)\\ \implies & f'(x)=\frac{1}{x}\\ \implies & f(x)=\ln x+C\\ \end{align}

代入 f(d)=1f(d)=1

f(d)=lnd+C=1    C=1lnd    f(x)=lnx+1lnd    f(x)=1+lnxd\begin{align} &f(d)=\ln d+C=1\\ \implies & C=1-\ln d\\ \implies & f(x)=\ln x+1-\ln d\\ \implies & f(x)=1+\ln\frac{x}{d}\\ \end{align}

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

 

题意:给定二维平面上 nn 个点,每点有坐标和 c[i] 值,mm 次询问,每次给定一个询问点,有坐标和 c 值,问 c 值小于等于询问点的最近的给定点。

K-D树

最近点的问题显然是KD树,但是本题还有 c 值的限制。

把 c 作为第三维,查询时若节点的第三维大于查询,则规定距离为无穷大。

KD树的复杂度比较玄学,用nth_element找中位数的复杂度期望 O(n)O(n),则建树复杂度为 O(nlogn)O(n\log n),但如果sort,则根据主定理的拓展,复杂度就是 O(nlog2n)O(n\log^2n),而单次查询最近点的复杂度为 O(n11k)O(n^{1-\frac{1}{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
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

 

题意:有 nn 种硬币,每种有 aia_i 个,正面向上的概率为 pip_i。不断重复:同时扔所有硬币并扔掉所有反面向上的硬币,直到只剩下一种硬币。问对于每种硬币,最后只剩下它的概率。

dp[i][j]dp[i][j] 表示到第 ii 轮,第 jj 种硬币还有存活的概率。

dp[i][j]=(1p[j]i)a[j]dp[i][j]=(1-p[j]^i)^{a[j]}.

枚举到 100 轮,可以近似估计答案。

在第 ii 轮,只有第 jj 种硬币存活的概率等于 dp[i][j]1kn,kj(1dp[i][k])dp[i][j]\cdot \prod\limits_{1\le k\le n,k\neq j}(1-dp[i][k])

但是这样直接求和会导致重复,因为除了 jj 以外的硬币可能在第 ii 轮以前就全部扔掉了,也就是说游戏并不能进行到第 ii 轮。

假设现在处于第 11 轮,第一轮除 jj 之外所有硬币都死亡的概率为 1kn,kj(1dp[1][k])\prod\limits_{1\le k\le n,k\neq j}(1-dp[1][k]),设为 SS,则 jj 在第一轮胜出的概率为 dp[1][j]Sdp[1][j]\cdot S。在计算第二轮时,SS 同样可能出现,要把这种情况从答案里去掉,所以要减去 dp[2][j]Sdp[2][j]\cdot S,不需要再继续减了,因为这种情况在第二轮不出现,第三轮就更不会出现。

以此类推,在第 jj 种硬币获胜的概率为 i=1100(dp[i][j]dp[i+1][j])1kn,kjdp[i][k]\sum\limits_{i=1}^{100}(dp[i][j]-dp[i+1][j])\cdot\prod\limits_{1\le k\le n,k\neq 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;
}