娱乐 每 期 算 法 挑 战 #0

[弧光]

sstm居然还有算法板块，惊了（

题目来自蓝桥杯第九届省赛-螺旋折线

描述

对于整点 (x,y)，我们定义它到原点的距离dis(x,y) 是从原点到 (x,y) 的螺旋折线段的长度。

例如 dis(0,1)=3,dis(−2,−1)=9

那么你能计算出dis(13,-15)吗？

[yhz012]

注意到：

(0, 0) => 0
(-1, 0) => 1
(0, 1) => 1 + 2
(1, 0) => 1 + 2 + 2
(0, -1) => 1 + 2 + 2 + 2
(-2, 0) => 1 + 4 * 2 + 1

因此，坐标轴上的点有

(-n, 0) => 1 + sum( 4 * 2 * i + 1), i = 1, 2 ..., n - 1
(0, n) => d(-n, 0) + 2 * n
(n, 0) => d(-n, 0) + 2 * 2 * n
(0, -n) => d(-n, 0) + 3 * 2 * n

对于第四象限点(13, -15)，因为在y=-x直线下方，所以

d(13, -15) = d(15, -15) + 2
           = d(15, 0) + 15 + 2
           = d(-15, 0) + 2 * 2 * 15 + 15 + 2
           = 1 + sum(4 * 2 * i + 1) + 77
           = 855 + 77 = 932

没验算，随便写的，写错了别打我（x

 

 

 

想了下，把两步看成一起作为一个L型会容易点

八月 7, 2021，由yhz012修改

[默宇千穹]

将左下轴偏转90度构成n个正方形

构成等差数列8 16 24 32 ....则点dis(13,-15)为数列前14项和加上第15项-2为14*8+14*{14-1}*8/2+8+{8-1}*8-2=840+62=932

八月 7, 2021，由moyuqianqiong修改
刚才没写完点到提交回复了

[fdcrane]

首先计算螺旋折线拐点距离原点的距离，
从最简单计算的第二和第四象限开始:
第四象限，对于第n个拐点(-n,n)，其距离原点的距离等于从1到(2n-1)代数和的两倍;
第二象限，对于第n个拐点(n,-n)，其距离原点的距离等于从1到2n代数和的两倍;
第一象限第n个拐点(n,n)距离是在第四象限距离基础上加上一个2n;
第三象限第n个拐点(-n-1,-n)距离是在第二象限距离基础上加上一个(2n+1);

(13,-15)最近的拐点(15,-15)距离原点的距离为1到30代数和的两倍930。
因此(13,-15)距离原点的距离则是930+2=932。

[弧光]

33 分钟前, moyuqianqiong 说道:

将左下轴偏转90度构成n个正方形

构成等差数列8 16 24 32 ....则点dis(13,-15)为数列前14项和加上第15项-2为14*8+14*{14-1}*8/2+8+{8-1}*8-2=840+62=932

当时模拟赛就用的这个方法，大佬强

[黔驴技穷]

盯了半天才算看出来

图形大概是由L （奇数长度）和 7（偶数长度） 的形状组成，每隔一个L或7长度就会+1，一对L和7可以看成一圈

坐标处于哪一圈可以从数值最大的x或y得出，这里-15最大

如果是从下移动的话，坐标就是处于一个圈的L正下方 ，然后第一圈的L长度是1，第二圈加了2是3，-15是第16圈所以是1+（2*15）=31的长度

然后从图形可以看出如果直线往下的话，坐标处于的是中间偏右一格，所以-15是处于16 | 15 的右边区域

到了这里根据x的数值13，又要再往右挪13格，所以15就先减个13变成2，剩下的就简单了，先算出完整15圈的长度

(30+1)*15*2=930

补上第十六圈的2就等于932

看的糊里糊涂，偷看了别人的答案才确定没问题

[弧光]

sstm真的是卧虎藏龙啊，题目不是很难，但是细节验算还是稍微有点麻烦

个人做法和某个答案一样，一圈一个区域划分，用x y的最大值判断在哪个圈，最后分四个方向分别判断，附上本人的垃圾代码（

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt(),y = sc.nextInt();
        long n = Math.max(Math.abs(x),Math.abs(y));
        long res = 4 * (n - 1) * n;
        if(x == -n) {
            if(y == -n) {
                res += (8 * n);
            } else {
                res += (n + y);
            }
        } else if(y == n) {
            res += (2 * n) + (n + x);
        } else if(x == n) {
            res += (4 * n) + (n - y);
        } else if(y == -n) {
            res += (6 * n) + (n - x);
        }
        System.out.println(res);
    }
}

答案就是932

 

[弧光]

1 小时前, yhz012 说道:

注意到：

(0, 0) => 0
(-1, 0) => 1
(0, 1) => 1 + 2
(1, 0) => 1 + 2 + 2
(0, -1) => 1 + 2 + 2 + 2
(-2, 0) => 1 + 4 * 2 + 1

因此，坐标轴上的点有

(-n, 0) => 1 + sum( 4 * 2 * i + 1), i = 1, 2 ..., n - 1
(0, n) => d(-n, 0) + 2 * n
(n, 0) => d(-n, 0) + 2 * 2 * n
(0, -n) => d(-n, 0) + 3 * 2 * n

对于第四象限点(13, -15)，因为在y=-x直线下方，所以

d(13, -15) = d(15, -15) + 2
           = d(15, 0) + 15 + 2
           = d(-15, 0) + 2 * 2 * 15 + 15 + 2
           = 1 + sum(4 * 2 * i + 1) + 77
           = 855 + 77 = 932

没验算，随便写的，写错了别打我（x

 

 

 

想了下，把两步看成一起作为一个L型会容易点

对的，思路很清晰

[风爱]

3 小时前, 弧光 说道:

sstm居然还有算法板块，惊了（

题目来自蓝桥杯第九届省赛-螺旋折线

描述

对于整点 (x,y)，我们定义它到原点的距离dis(x,y) 是从原点到 (x,y) 的螺旋折线段的长度。

例如 dis(0,1)=3,dis(−2,−1)=9

那么你能计算出dis(13,-15)吗？

？？？草，蓝桥杯

看到标题我啪的一下就点进来了

[弧光]

24 分钟前, 风爱 说道:

？？？草，蓝桥杯

看到标题我啪的一下就点进来了

灌水杯~300大洋混个奖状

[qq2253238]

ss论坛居然有蓝桥杯，不过话说都入职银行了，计算机神马的已经与我无关了

[风爱]

于 2021/8/7 于 PM3点25分, 弧光 说道:

灌水杯~300大洋混个奖状

？呜呜呜

我只拿到了300大洋和一张证书。莫得奖状

但是报名费好像就要三百来着？我在蓝桥杯报名页面看到的报名费就是三百诶。比赛开赛之前的训练赛好像是16？

所以基本是抱着拿回报名费的心态去打的比赛哈哈哈哈哈