Znzryb's Blog
0%

P2239 [NOIP2014 普及组] 螺旋矩阵（CRH-I）

Posted on Edited on

AC代码

本来不是想做这题的，但想不到赛氪竟然连补题都不支持，离谱。

这题和赛氪的题还不完全一样，两者螺旋矩阵的顺序有稍许不同

然后比赛的时候不要光想，笔也要动起来，比赛完后我造了个数据6 3 3，结果输出了38，就发现问题了，但赛中没造6的数据。只能说不要停下来呀！！！

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstdio>
#include <cctype>

// https://oj.saikr.com/problem/detail/1854
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,I,J;
// 行号，列号

int main()
{
    cin>>n>>I>>J;
    ll cen=min(min(I,n+1-I),min(J,n+1-J));
    if(cen==(n/2+1)) {
        cout<<n*n<<endl;
        return 0;
    }
    ll cnt=0;
    for(int i=1;i<cen;++i) {
        cnt+=4*(n+2-2*i)-4;
    }
    for(int j=cen;j<=n+1-cen;++j) {   // 从左上走到右上
        if(I!=cen) {
            cnt+=(n+1-cen)-(cen)+1;
            break;
        }
        ++cnt;
        if(I==cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int i=cen+1;i<=n+1-cen;++i) {   // 从右上走到右下
        if(J!=n+1-cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==i && J==n+1-cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int j=n-cen;j>=cen;--j) {     // 从右下走到左下
        if(I!=n+1-cen) {
            cnt+=(n-cen)-(cen)+1;
            break;
        }
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int i=n-cen;i>=cen+1;--i) { // 从左下走到左上
        if(J!=cen) {
            cnt+=(n+1-cen)-cen+1;
            break;
        }
        ++cnt;
        if(I==i && J==cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    return 0;
}
// AC https://www.luogu.com.cn/record/188066061

心路历程（WA，TLE，MLE……）

还是声明一下，下面的WA代码不是此题的

主要这段代码出问题了

1
2
3
for(int i=1;i<cen;++i) {
        cnt+=4*(n+1-i)-4;
 }

应该写成这样

1
2
3
for(int i=1;i<cen;++i) {
        cnt+=4*(n+2-2*i)-4;
    }

这种涉及所有东西推导的代码还是不能够仅靠观察，理性论证也很重要

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstdio>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=3010;
ll n,I,J;
// 行号，列号

int main()
{
    cin>>n>>I>>J;
    ll cen=min(min(I,n+1-I),min(J,n+1-J));
    if(cen==(n/2+1)) {
        cout<<n*n<<endl;
        return 0;
    }
    ll cnt=0;
    for(int i=1;i<cen;++i) {
        cnt+=4*(n+1-i)-4;
    }
    for(int i=n+1-cen;i>=cen;--i) {
        if(J!=cen) {
            cnt+=(n+1-cen)-cen+1;
            break;
        }
        ++cnt;
        if(I==i && J==cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int j=cen+1;j<=n+1-cen;++j) {
        if(I!=cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int i=cen+1;i<=n+1-cen;++i) {
        if(J!=n+1-cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==i && J==n+1-cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int j=n-cen;j>=cen+1;--j) {
        if(I!=n+1-cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    return 0;
}

注意！！！TLE不仅代表算法时间复杂度过高，还有可能是死循环（特别是你觉得TLE不可思议时，相信自己的判断，大概率是死循环）

1
2
3
4
5
6
7
for(int j=n+1-cen;j>=cen+1;++j) {
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

像这段代码，是 —j 的，写成了++j，就会死循环TLE

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstdio>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=3010;
ll n,I,J;
// 行号，列号

int main()
{
    cin>>n>>I>>J;
    ll cen=min(min(I,n+1-I),min(J,n+1-J));
    if(cen==(n/2+1)) {
        cout<<n*n<<endl;
        return 0;
    }
    ll cnt=0;
    for(int i=1;i<cen;++i) {
        cnt+=4*(n+1-i)-4;
    }
    for(int i=n+1-cen;i>=cen;--i) {
        ++cnt;
        if(I==i && J==cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    for(int j=cen+1;j<=n+1-cen;++j) {
        ++cnt;
        if(I==cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    for(int i=cen+1;i<=n+1-cen;++i) {
        ++cnt;
        if(I==i && J==n+1-cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    for(int j=n+1-cen;j>=cen+1;++j) {
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    return 0;
}