UOJ161 【清华集训2015】园子里 题解
题目链接:#161. 【清华集训2015】园子里
题意:
cxy 在园子里过着快乐而充实的生活。突然有一天,从天而降 \(n\) 根柱子,这 \(n\) 根柱子在学堂路上排成一排,第 \(i\) 根柱子高度为 \(h_i\)(即\(h_i\) 为原始高度)米,然而,当有人站在第 \(i\) 根柱子上的时候,第 \(i\) 根柱子的高度会下降 \(t_i\)(即当有人在上面时候 \(h_i-t_i\) 就是当前高度)米,离开之后又会恢复。cxy 对这些柱子非常感兴趣,他可以从一根柱子跳到任意一个(包括他原本站着的柱子)原始高度不超过他所在柱子当前高度的柱子上,如果有多个柱子都满足,他会随机等概率地跳到一个满足条件的柱子上,如果没有柱子满足,他就会跳到地上。
cxy 想知道,如果他从第 \(i\) 个柱子开始,期望跳多少次可以跳到地上。
输入格式:
第一行一个整数 \(n\),表示柱子的数量。
第二行 \(n\) 个空格隔开的整数 \(h_i\),表示每根柱子的高度(单位:米)。
第三行 \(n\) 个空格隔开的整数 \(t_i\),表示有人站在第 \(i\) 根柱子上的时候高度会下降 \(t_i\) 米。
输出格式:
输出一行 \(n\) 个浮点数,每两个浮点数用一个空格隔开,第 \(i\) 个数表示 cxy 从第 \(i\) 根柱子开始,期望跳多少步可以跳到地上,如果期望步数为无穷,输出 \(0\) ;如果你输出的每个浮点数与标准答案的误差(此处误差定义为你的答案与标准答案差的绝对值)均不超过 \(0.001\) ,你的答案将被视为正确。
注意,我们会用一个特殊的程序来判断你的答案正确与否,你输出每个浮点数的字符串长度应该不超过 \(20\) 。
定义无穷可以参与运算,无穷 + X = 无穷,无穷 - X = 无穷,无穷 * X = 无穷,无穷 / X = 无穷(X 为任一实数,在除法中不为 0)
数据范围:
\(1 \le n \le 10^6,~1\le h_i \le 10^5,~0 \le t_i \le h_i\)
注意到这个跳的过程类似于DAG,因此考虑dp
设 \(f_i\) 表示从柱子 \(i\) 跳回地面的期望步数。记 \(h^{\prime}_i = h_i-t_i\) ,则 \[ f_i = 1 + \frac{\sum_{h_j \le h_i^{\prime}}f_j}{\sum_{h_j \le h_i^{\prime}} 1} \] 若 \(\sum_{h_j \le h_i^{\prime}} 1 = 0\) ,则定义 \(f_i=1\) (直接跳地上)。
但是观察转移方程可以发现,如果 \(h_i = h_i^{\prime}\) ,即自己可以跳到自己身上,就会导致循环转移。
考虑将所有 \(h_i=h_i^{\prime}\) 且高度相等的所有柱子一起处理。
设有 \(k\) 个「 \(h_i=h_i^{\prime}\) 且高度相等」的柱子,跳回地面的期望步数为 \(r\) ,则 \[ r = 1 +\frac{\sum_{h_j \le h_i\land h_j^{\prime} < h_i}f_j + k\times r}{\sum_{h_j \le h_i^{\prime}} 1} \] 设 \(A=\sum_{h_j \le h_i\land h_j^{\prime} < h_i}f_j,~B = \sum_{h_j \le h_i^{\prime}} 1\) ,解得 \(r=\dfrac{A+B}{B-k}\) 。
若 \(B=k\) ,则此时所有高度不超过 \(h_i\) 的柱子均为 \(h_i\) ,并且 \(h_i = h^{\prime}_i\) ,显然有 \(r=+\infty\)
时间复杂度 \(O(n \log n + h_{\max})\)
代码:(这题有点卡常)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N ((int)(1e6+15))
#define M ((int)(1e5+15))
#define F first
#define S second
int n,mx,H[N],h[N],sc[M];
double f[N],sf[M];
vector< pair<int,int> > v[M];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
// cout << fixed << setprecision(8);
read(n);
for(int i=1; i<=n; i++) read(H[i]);
for(int i=1,x; i<=n; i++)
{
read(x); h[i] = H[i] - x;
mx = max(mx, H[i]);
v[H[i]].emplace_back(h[i],i);
}
for(int i=1; i<=mx; i++)
{
sc[i] = sc[i-1] + v[i].size();
sf[i] = sf[i-1]; int x=0;
for(auto t : v[i])
{
if(t.F < i)
{
f[t.S] = (sc[t.F] ? (sf[t.F] / (double)sc[t.F]) : 0) + 1;
sf[i] += f[t.S];
}else ++x;
}
double r = (x == sc[i] ? INFINITY : 1.0 * (sf[i] + sc[i]) / (sc[i]-x));
for(auto t : v[i])
if(t.F == i) sf[i] += (f[t.S] = r);
}
for(int i=1; i<=n; i++)
printf("%.8lg%c",(isfinite(f[i]) ? f[i] : 0.0), " \n"[i==n]);
return 0;
}
参考文献:
[1] https://yhx-12243.github.io/OI-transit/records/lydsy5115%3Buoj161.html