【AtCoder】Handstand 2

題目連結

時間複雜度

• $O(N)$

解題想法

這題我一開始在解的時候就想到可以枚舉頭尾了，但一直想不到怎麼去實作會比較好。後來去看了別人的題解再終於知道枚舉的細節

完整做法

1. 從 1 開始掃到
   $N$ 並將每一個數字存進 arr[最高位的數字][最低位的數字] 中，其中 arr[i][j] 表示
   $i$ 為最高位數且
   $j$ 為最低位數的所有能性
2. 從 arr 中枚舉頭尾 1 ~ 9 的所有可能（共 81 種）
   1. 每枚舉一個
      $i$ 跟
      $j$ 時，結果就加上 arr[i][j] x arr[j][i]

完整程式

/* Question : AtCoder Beginner Contest 152 - D - Handstand 2 */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#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 = 1e4 + 50;
const int Mod = 1e9 + 7;
int n, ans, arr[MAXN][MAXN];

int topN( int val ){
    while( val >= 10 ) val /= 10;
    return val;
}


signed main(){
    opt;
    cin >> n;
    for( int i = 1 ; i <= n ; i++ ){
        int t = topN(i);
        int b = i % 10;
        arr[t][b]++;
    }

    for( int i = 1 ; i <= 9 ; i++ ){
        for( int j = 1 ; j <= 9 ; j++ ){
            ans += arr[i][j] * arr[j][i];
        }
    }

    cout << ans << "\n";
}