hdu1030 - Delta-wave

朴灿烈づ我的快乐病毒、 2022-07-13 08:18 100阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=1030][http_acm.hdu.edu.cn_showproblem.php_pid_1030]

# 定位 #

*  找规律
 *  三角形坐标系

# 分析 #

*  看完题目后，感觉不是一般的最短路径问题。诚然，将此三角形的连通性抽象成图，运用最短路径算法，理论上可以解题。但是，1≤N≤1000000000(10亿)，问题规模太大了，明显不能用常规做法。
 *  参考一些解题报告后，才有了思路。我将解题关键归结为三点：
    
     *  三角形坐标系。观察整个三角形，由三个方向的直线将区域分割，横线、左斜线、右斜线。这是一个三维坐标系，三个方向的直线标定三个维度，每个区域(小三角形的标号)都可以由一组三维坐标唯一确定。
     *  两点间距离。在这种三角形坐标系下，重新定义两点间距离，两点之间的曼哈顿距离即为两点间的最短路径。
     *  找规律。仅由小三角形标号就可以确定其坐标，推倒过程依赖等差数组求和和找规律。
 *  层数z。前z层区域数量和sum(z)=1\+3\+⋯\+(2z−1)=z2，因此，z−1=a−1−−−−√。

z=a−1−−−−√\+1

*  左坐标。z层最大标号z2，最大标号与标号a差值z2−a，2个一组。

l=z2−a2\+1

*  右坐标。z-1层最大标号(z−1)2，标号a与上一层最大标号差值a−(z−1)2，2个一组。

l=a−(z−1)22

# 代码 #

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    struct node
    {
        int l,r,z;
    };
    
    struct node resolve(int tmp)
    {
        struct node n;
        n.z = sqrt(tmp-1) + 1;
        n.l = (n.z * n.z - tmp) / 2 + 1;
        n.r = (tmp - (n.z - 1) * (n.z - 1) + 1) / 2;
        return n;
    }
    
    int main()
    {
        struct node n1,n2;
        int a,b;
        while(scanf("%d*c",&a) != EOF)
        {
            scanf("%d*c",&b);
            n1 = resolve(a);
            n2 = resolve(b);
            printf("%d\n",abs(n1.z - n2.z) + abs(n1.l - n2.l) + abs(n1.r - n2.r));
        }
        return 0;
    }

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">0MS</td> 
   <td align="center">1404K</td> 
   <td align="center">567B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

## 三角形坐标系 ##

查阅了一些资料，没有找到关于这种三角形坐标系的数学说明。反而，地理学中经常用到这种表达方式，称之为三角形统计图。

## 两点间距离 ##

*  欧几里得距离(直线距离)

d=(x1−x2)2\+(y1−y2)2−−−−−−−−−−−−−−−−−−√

*  曼哈顿距离，两个点在标准坐标系上的绝对轴距总和

d=|(x1−x2)|\+|(y1−y2)|

*  切比雪夫距离，各坐标数值差的最大值

d=max(|(x1−x2)|,|(y1−y2)|)

Thanks everyone!

[http_acm.hdu.edu.cn_showproblem.php_pid_1030]: http://acm.hdu.edu.cn/showproblem.php?pid=1030