HDU/HDOJ 1030 Delta-wave(找规律)

题目传送门:

简单说下思路:

1.首先判断M,N两点所在的行及两行之差dis。

2.求出M点辐射区域,因为观察可知当N处于辐射区域内是,两点的路径为2*dis,然后再根据正三角形还是倒三角形判断是减一还是加一。

3.若不在辐射区域,则直接求2*dis及N与区域边缘之差。

这个思路也是参照网上牛人的。。。规律题Orz.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 首先判断第几行
// 再判断是正三角还是倒三角
#include <iostream>
using namespace std;
 
int M, N;
 
int hang(int n)
{
    int cnt = 0;
    for(int i=1, s=0; s<n; i+=2)
    {
        s += i;
        ++cnt;
    }
    return cnt;
}
 
bool isUP(int n)
{
    int t = hang(n);
    if(t%2 == n%2)
        return 1;
    else
        return 0;
}
 
int wei(int n)
{
    int t = hang(n)-1;
    return n - t*t;
}
int main()
{
    while(cin >> M >> N)
    {
        if(M > N)
        {
            M = M^N;
            N = M^N;
            M = M^N;
        }
        //cout << M << " " << N << endl;
        //cout << hang(M) << " " << hang(N) << endl;
        int h1 = hang(M), h2 = hang(N);
        int dish = h2 - h1;
        int tot = 0;
        if(h1 == h2)
        {
            cout << N-M << endl;
            continue;
        }
        int x1 = wei(M), x2 = wei(N);
        //cout << x1 << " " << x2 << endl;
        int w1 = M + (h2-1)*(h2-1) - (h1-1)*(h1-1);
        int w2 = w1 + 2*dish;
 
        bool flag = 0;
        if(N >= w1 && N <= w2)
        {
            tot = 2*dish;
            flag = 1;
        }
        else
        {
            if(N < w1)
                tot = 2*dish + w1-N;
            else
                tot = 2*dish + N-w2;
        }
        //cout << tot << endl;
        if(flag && !isUP(M) && isUP(N))
                tot += 1;
        else if(flag && isUP(M) && !isUP(N))
            tot -= 1;
        cout << tot << endl;
 
 
    }
    return 0;
}

我写的比较乱,网上看见一个写的比较清晰的:
http://www.cppblog.com/guodongshan/archive/2010/10/06/128797.aspx

《HDU/HDOJ 1030 Delta-wave(找规律)》有481个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注