P1429 萌新妹子学习分治遇到大问题,脑袋快破啦/kel 求助大佬!!!
  • 板块学术版
  • 楼主llooser
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/8 22:49
  • 上次更新2023/11/3 05:05:05
查看原帖
P1429 萌新妹子学习分治遇到大问题,脑袋快破啦/kel 求助大佬!!!
246609
llooser楼主2023/8/8 22:49

希望可以举一些例子,比较形象简单的(球球了

一些严谨的数学证明也可以/se

AC代码-0

  for (int i = 1, pl = 1, pr = 1; i <= ca; i++) {
    for (; pr <= cb && (b[pr].second - a[i].second) * (b[pr].second - a[i].second) < ans; pr++) {
    }
    for (; pl <= cb && a[i].second-b[pl].second >= 0 && (a[i].second - b[pl].second) * (a[i].second - b[pl].second) >= ans; pl++) {
    }
    // for (; pl <= cb  && (a[i].second - b[pl].second) * (a[i].second - b[pl].second) >= ans; pl++) {
    // }
    for (int j = pl; j < pr && j <= cb; j++) {
      D(a[i], b[j]);
      
    }

用注释掉的部分替代上一条语句会WA,这是为什么呢? 按道理来说,既然y方向的差的平方已经超过最近距离的平方ans,就不能贡献答案了,注释部分替代应该不会对最终结果造成影响呀


AC代码-1 这份代码是直接用最短距离ans的,但是为什么他的下界是这样子

  for (int i = 1, pl = 1, pr = 1; i <= ca; i++) {
    for (; pr <= cb && b[pr].second - a[i].second < ans; pr++) {
    }
    for (; pl <= cb && a[i].second - b[pl].second >= ans; pl++) {
    }
    // for (; pl <= cb && fabs(a[i].second - b[pl].second) >= ans; pl++) {
    // }
    for (int j = pl; j < pr; j++) {
      D(a[i], b[j]);
    }
  }

如果用注释掉的部分替代,也是会WA, 按道理来说,既然y方向的差的绝对值已经超过最近距离ans,就不能贡献答案了,注释部分替代应该不会对最终结果造成影响呀

2023/8/8 22:49
加载中...