CodeForces/336B

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Vasily the Bear and Fly	★☆☆☆☆	答案正确	100	2015-02-27 12:35:20	遗漏情况（1）

• 来自寒假练习：2015 Winter Day 4 div1 G题
• 原题链接：http://codeforces.com/problemset/problem/336/B

题意

坐标轴上有2*n个R为半径两两相邻的圆，问任取圆心第(1,i)和(2,j)（i,j表示序号而非坐标）之间的最短路径的数学期望（路径要求都在圆内）。

题解

• 理解了题意确实做起来不是太难，肯定不能暴力，要优化到O(n)。
• 很容易知道:|i-j|相等距离也相等，对于一个|i-j|，其符合条件的圆心对个数是(m-|i-j|)*2（i=j时，没有*2）。
• 然后算一下距离乘下个数就好了，实际也没必要用高精度。但是被样例数据坑了。
• 样例数据是这样：

• 我以为这样也是最优：

• 其实这样也OK……

扯个题外话：java里BigDecimal的divide要求第二个参数是精度，不要漏了- -

代码

336B.java代码已折叠 展开折叠内容

import java.io.BufferedInputStream; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); int m = cin.nextInt(); BigDecimal R = cin.nextBigDecimal(); BigDecimal ans = BigDecimal.ZERO, TWO = BigDecimal.valueOf(2), s2 = new BigDecimal( Math.sqrt(2)); for (int i = 0; i != m; ++i) { BigDecimal v = BigDecimal.ONE; BigDecimal u = BigDecimal.valueOf(i); u = u.add(BigDecimal.ONE); BigDecimal dis = BigDecimal.ZERO; if (u == v) dis = R.multiply(TWO);// 2R// else if (i == 1) dis = R.multiply(BigDecimal.valueOf(i * 2)).add(s2.multiply(R));// 2iR+R// else dis = R.multiply(BigDecimal.valueOf(i * 2 - 2)).add( s2.multiply(R.multiply(TWO)));// 2iR+R// if (i != 0) ans = ans.add(dis.multiply(BigDecimal.valueOf((m - i) * 2))); else ans = ans.add(dis.multiply(BigDecimal.valueOf(m - i))); } ans = ans.divide(BigDecimal.valueOf(m), 1000, RoundingMode.HALF_DOWN); ans = ans.divide(BigDecimal.valueOf(m), 50, RoundingMode.HALF_DOWN); System.out.println(ans); return; } }