ACM/ICPC2016 青岛区域赛

A（hdu5982）、（模拟）

　　题意：输入n对数，将每对数相乘并相加

　　分析：模拟

B（hdu5983）、（模拟）

　　题意：给你一个二阶魔方，问能否通过一次旋转使得给定魔方的每个面颜色相同

　　分析：模拟

C(hdu5984)、（数学，微分方程）

　　题意：有一个长为d的木棒，最右端有长为L的区域（L<=d），每次操作从木棒的某个部位切，左边的部分就全扔掉，右边的部分保留下来视为新的木棒，一直到切到右端的L区域为止才停止才做，求操作次数的数学期望。

　　分析：先考虑离散的，f[i]表示长为i的木棒的数学期望，则f[i]=Σ(f[k]+1)/(i-L) (L<=i<=d,L<=k<=i)，尝试将小数扩大成整数，但发现精度不够。

　　　　　然后把他写成积分形式：f(x)=∫f(i)di/x（0<=i<=x) + 1，于是问题就是解这个微分方程，解出f'(x)=1/x，所以f(x)=lnx+C，代入原式解得C=1-lnL

　　　　　所以结果就是lnd+1-lnL=ln(d/L)+1

D(hdu5985)、（概率、递推）

　　题意：有n种硬币，每种硬币有ai个，每个硬币有p的概率正面朝上，每次操作后将背面朝上的硬币全部丢掉，直到只剩下一种硬币，称这种硬币为幸运硬币，求每种硬币成为幸运硬币的概率

　　分析：每种硬币都是独立的，分开考虑

　　　　　f[i][k]表示第i种硬币，第k轮投完后硬币全部丢弃的概率

　　　　　则f[i][k]=(1-p+(1-p)p+(1-p)p^2+.....)^a[i]=(1-p^k)^a[i]

　　　　　那么第k轮后至少存在一枚硬币的概率就是1-f[i][k]

　　　　　ans[i]=Σ(k=0..+无穷) f[1][k]*f[2][k]*...*f[i-1][k]*f[i+1][k]*....*f[n][k]*(1-f[i][k]-1+f[i][k+1]) 这里是为了防止重复

　　　　　然后根据精度和时限要求，k只要取几百就行了。

G(hdu5988)、（费用流）

　　题意：给你个图，每个点上都有人的数量和包的数量，要求人通过走动满足每个点的包的数量>=人的数量，每条边有容量和一个走动破坏概率pi，表示如果一个人走这条边，那么有pi的概率破坏这条边（但这条边被首次经过的时候破坏概率是0），求最小的破坏概率

　　分析：明显的费用流，这里是乘积所以取对数变成加法

　　　　　将问题看作要求不破坏概率最大

　　　　　对于人的数量>=包的数量的点i，S->i，容量为差值，费用为0，对于人的数量<=包的数量的点i，i->S，容量为差值，费用为0

　　　　　另外原图中的每条边都要拆一条出来，容量为1，费用为0，保证先走这个第一次走不破坏的

　　　　　然后就是求S->T的最大费用最大流

　　　　　注意事项：

　　　　　　　由于精度问题，不能取ln，可以取log2或者log10

　　　　　　　实数spfa的时候，松弛操作一定要加eps！不然会TLE

K(hdu5992)、(kdtree)

　　题意：给你n个宾馆的坐标和价格，有m个询问，表示每个人的坐标和手上的钱，对于每个人找出离他最近的且价格小于等于手中钱的宾馆，如果有多个，输出顺序靠前的宾馆。

　　分析：一个kdtree的题，可以开到三维，但计算距离时候只计算两维。

　　　　　在搜索最近点的时候，更新答案时候加上第三维的判断就行

　　　　　注意这里要用上第三维的mn[i]数组，代表它所管辖的矩形中钱数的最小值

　　　　　如果某个节点管辖矩形中钱数的最小值>当前人手里的钱，那么就不需要进去找了

　　　　　如果不加这个优化，那么很容易会TLE/爆栈（hdu容易爆栈）

巴特西