请选择 进入手机版 | 继续访问电脑版

ICPC 2020 , Shanghai Site 赛后补题

[复制链接]
西小妹谈娱 发表于 2020-12-31 20:29:22 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
很遗憾这次比赛打铁。
但还是想做完这场比赛的题目,所以看了出题人的题解,给自己写一个赛后补题。
本领有限,不能很快写完,佛系填坑吧。
题目难度评测
L. Traveling in the Grid World (Middle)

题解:
若                              g                      c                      d                      (                      n                      ,                      m                      )                      =                      1                          gcd(n,m)=1               gcd(n,m)=1,那么我们从                              (                      1                      ,                      1                      )                          (1,1)               (1,1)直线走到                              (                      n                      ,                      m                      )                          (n,m)               (n,m)就是答案了。
接下来,我们讨论                              g                      c                      d                      (                      n                      ,                      m                      )                      !                      =                      1                          gcd(n,m)!=1               gcd(n,m)!=1的情形。
首先我们可以知道,转折点越多,它的最短隔断越长。
所以我们的抱负转折点数是一个。
即:
找到一个数对                              (                      x                      ,                      y                      )                      ,                      s                      .                      t                      .                      g                      c                      d                      (                      x                      ,                      y                      )                      =                      g                      c                      d                      (                      n                      −                      x                      ,                      m                      −                      y                      )                      =                      1                      ,                      w                      h                      i                      l                      e                                                    x                               2                                      +                                       y                               2                                                 +                                         (                            n                            −                            x                                       )                               2                                      +                            (                            m                            −                            y                                       )                               2                                                     (x,y),s.t.gcd(x,y)=gcd(n-x,m-y)=1,while\sqrt{x^2+y^2}+\sqrt{(n-x)^2+(m-y)^2}               (x,y),s.t.gcd(x,y)=gcd(n−x,m−y)=1,whilex2+y2                                  ​+(n−x)2+(m−y)2                                  ​最小。

我们可以得到一个结论:当我们最小化这个隔断和时,                              g                      c                      d                      (                      x                      ,                      y                      )                          gcd(x,y)               gcd(x,y)一定是                              1                          1               1;
证明:
假设这个点是C,满意AC+BC是最小的隔断和;假设AC中存在整数点D,一定有BD
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )