Logo CloudLunar

“CodeForces/336B”的版本间的差异

（以“分类:整数处理 ==摘要== {{信息题|Vasily the Bear and Fly|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70748#problem/G|1|100|输出顺序|1...”为内容创建页面）
 
小 （补充）
 
第1行： 第1行：
 
[[分类:整数处理]]
 
[[分类:整数处理]]
 
==摘要==
 
==摘要==
−
{{信息题|Vasily the Bear and Fly|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70748#problem/G|1|100|输出顺序|1|time=2015-02-27 12:35:20}}
+
{{信息题|Vasily the Bear and Fly|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70748#problem/G|1|100|遗漏情况|1|time=2015-02-27 12:35:20}}
 
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70748 2015 Winter Day 4 div1] G题
 
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70748 2015 Winter Day 4 div1] G题
 
*原题链接：http://codeforces.com/problemset/problem/336/B
 
*原题链接：http://codeforces.com/problemset/problem/336/B
 
==题意==
 
==题意==
−
坐标轴上有2*n个R为半径两两相邻的圆，问任取圆心第(1,i)和(2,j)<small>（i,j表示序号而非坐标）</small>之间的最短路径的数学期望（路径要求都在圆内。
+
坐标轴上有2*n个R为半径两两相邻的圆，问任取圆心第(1,i)和(2,j)<small>（i,j表示序号而非坐标）</small>之间的最短路径的数学期望（路径要求都在圆内）。
 
==题解==
 
==题解==
 
*理解了题意确实做起来不是太难，肯定不能暴力，要优化到O(n)。
 
*理解了题意确实做起来不是太难，肯定不能暴力，要优化到O(n)。

2015年3月1日 (日) 23:51的最后版本

摘要

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

题意

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

题解

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

336B_1.jpg

  • 我以为这样也是最优：

336B_2.jpg

  • 其实这样也OK……

336B_3.jpg

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

代码

336B.java代码已折叠
展开折叠内容
显示/移除行号
  1. import java.io.BufferedInputStream;
  2. import java.math.BigDecimal;
  3. import java.math.RoundingMode;
  4. import java.util.Scanner;
  5. public class Main {
  6.  public static void main(String[] args) {
  7.   Scanner cin = new Scanner(new BufferedInputStream(System.in));
  8.   int m = cin.nextInt();
  9.   BigDecimal R = cin.nextBigDecimal();
  10.   BigDecimal ans = BigDecimal.ZERO, TWO = BigDecimal.valueOf(2), s2 = new BigDecimal(
  11.     Math.sqrt(2));
  12.   for (int i = 0; i != m; ++i) {
  13.    BigDecimal v = BigDecimal.ONE;
  14.    BigDecimal u = BigDecimal.valueOf(i);
  15.    u = u.add(BigDecimal.ONE);
  16.    BigDecimal dis = BigDecimal.ZERO;
  17.    if (u == v)
  18.     dis = R.multiply(TWO);// 2R//
  19.    else if (i == 1)
  20.     dis = R.multiply(BigDecimal.valueOf(i * 2)).add(s2.multiply(R));// 2iR+R//
  21.    else
  22.     dis = R.multiply(BigDecimal.valueOf(i * 2 - 2)).add(
  23.       s2.multiply(R.multiply(TWO)));// 2iR+R//
  24.    if (i != 0)
  25.     ans = ans.add(dis.multiply(BigDecimal.valueOf((m - i) * 2)));
  26.    else
  27.     ans = ans.add(dis.multiply(BigDecimal.valueOf(m - i)));
  28.   }
  29.   ans = ans.divide(BigDecimal.valueOf(m), 1000, RoundingMode.HALF_DOWN);
  30.   ans = ans.divide(BigDecimal.valueOf(m), 50, RoundingMode.HALF_DOWN);
  31.   System.out.println(ans);
  32.   return;
  33.  }
  34. }
取自“https://blog.CloudLunar.com/index.php?title=CodeForces/336B&oldid=1288”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]