HDU 1030 Delta-wave

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1030

解题思路：

题目大意是求解任取两个小三角形，不通过顶点，只跨越边的最少次数是多少。

这是一道周赛的题目，当时没有思路。后来讨论的时候，给出了思路。大概说一下。

先举一个例子看看。

那么最后的结果也就是三个差的和了 1+1+1=3

定义一个结构体里面包含数值本身还有自身在三中颜色下的层数（红色层数用ii表示，黄色层数用jj表示，蓝色层数用kk表示）

下面就是ii,jj,kk的计算了。

从红色颜料的角度看，每一行的最后一个数都是完全平方数。并且等于行数的平方。

所以ii就等于数值本身-1开平方之后再加1，即p.ii=(int)sqrt(p.num - 1) + 1;

计算jj用到了ii的值。jj的计算方法是在红色颜料的角度下观察该数值从左往右看在该行的第几个。然后在黄色颜料的角度下观察到红色颜料2个数位于同一行。例如:

所以，p.jj=(p.num - (p.ii - 1)*(p.ii - 1) + 1) / 2 //依据上一行的最后的一个完全平方数来计算该数值在该行的第几个。

最后计算kk也是同样的道理。方向是从右往左看位于该行的第几个。根据该行的完全平方数来确定是第几个。当然也是两个为一组。

下面给出kk的计算公式：p.kk = ((p.ii)*(p.ii) - p.num) / 2 + 1;

分开求解的思想，get。

源代码：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string>
 5 #include<string.h>
 6 #include<math.h>
 7 #include<map>
 8 #include<vector>
 9 #include<algorithm>
10 using namespace std;
11 #define MAX 0x3f3f3f3f
12 #define MIN -0x3f3f3f3f
13 struct node
14 {
15     int num;
16     int ii;
17     int jj;
18     int kk;
19 };
20 void calculate(node &p)
21 {
22     p.ii = (int)sqrt(p.num - 1) + 1;
23     p.jj = (p.num - (p.ii - 1)*(p.ii - 1) + 1) / 2;
24     p.kk = ((p.ii)*(p.ii) - p.num) / 2 + 1;
25 }
26 int main()
27 {
28     int sum;
29     node m, n;
30     while (scanf("%d%d", &n.num, &m.num) != EOF)
31     {
32         calculate(n);
33         calculate(m);
34         sum = 0;
35         sum = abs(n.ii - m.ii) + abs(n.jj - m.jj) + abs(n.kk - m.kk);
36         printf("%d
", sum);
37     }
38     return 0;
39 }

View Code