【CSES】1071. Number Spiral

題目連結

時間複雜度

$O (N)$

解題想法

結論

這題的想法很簡單，只要經過以下幾個步驟就可以精準查詢到題目要的數字

觀察 x 跟 y 哪一個比較大
1. 如果 x 比較大
  1. 當 x 是偶數
    - 答案就會是
      $x^{2} - (y - 1)$
  2. 當 x 是奇數
    - 答案就會是
      $(x - 1)^{2} + y$
2. 如果 y 比較大
  1. 當 y 是偶數
    - 答案就會是
      $(y - 1)^{2} + x$
  2. 當 y 是奇數
    - 答案就會是
      $y^{2} - (x - 1)$

分析

這個規則是觀察題目的數列得出來的結論，如果真的要證明的話可以將數列拆成這樣

只要邊長是偶數的話，那段數列中數字的數量就會放在右下角的位置

EX1.

1 2
4 3

EX2.

1  2  9  10
4  3  8  11
5  6  7  12
16 15 14 13

反之，如果是奇數的話就會放在左上角

因為在最一開始的時候有先比較 x 跟 y 的大小，所以在一開始的時候就會把數字的範圍框在一個特定大小的正方形裡面了，這時候再透過 ± x 或 y 的值就可以達到查詢數字的目的了

完整程式














































/* Question : CSES 1071. Number Spiral */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int t, x, y, ans;

signed main(){
    opt;
    cin >> t;
    while( t-- ){
        cin >> x >> y;
        if( x == 1 && y == 1 ){
            cout << "1\n";
        }else if( x > y ){
            if( x % 2 == 0 ){
                ans = x * x;
                ans -= (y-1);
            }else{
                ans = (x-1) * (x-1);
                ans += y;
            }
            cout << ans << "\n";
        }else{
            if( y % 2 == 1 ){
                ans = y * y;
                ans -= (x-1);
            }else{
                ans = (y-1) * (y-1);
                ans += x;
            }
            cout << ans << "\n";
        }
    }
}