2019.10.03解题报告

总体来说能打的暴力都打了
期望\(100 + 40 + 30 = 170\)
实际\(100 + 40 + 10 = 180\)
数据良心（）

T1

第一眼觉得就是要找规律，然后直接找找不出来，所以用暴力搜一下

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 2011;

int vis[N][N];

struct node {
    int x, y, num;
};

const int dx[8] = {-2,-2,-1,1,2,2,1,-1};
const int dy[8] = {-1,1,2,2,1,-1,-2,-2};

queue <node> q;

int sum = 0;

int main() {
    for(int T = 0; T <= 100; T++) {
        int n = T;
        sum = 0;
        memset(vis, 0, sizeof(vis));
        while(!q.empty()) q.pop();
        node st;
        st.x = 1000;
        st.y = 1000;
        vis[st.x][st.y] = 1;
        st.num = 0;
        q.push(st);
        while(!q.empty()) {
            node top = q.front();
            q.pop();
            sum++;
            for(int i = 0; i < 8; i++) {
                node tmp;
                tmp.x = top.x + dx[i];
                tmp.y = top.y + dy[i];
                tmp.num = top.num + 1;
                if(!vis[tmp.x][tmp.y] && tmp.x >= 0 && tmp.y >= 0 && tmp.x <= 2000 && tmp.y <= 2000 &&tmp.num <= n) {
                    vis[tmp.x][tmp.y] = tmp.num;
                    q.push(tmp);
                }
            }
        }
        cout  << sum << '\n';
    }
}

找不到什么规律，于是求一下差值，还是没什么规律，用差值再求一下差值，发现前五项的差值是特别的，所以直接特别输出，其他的发现差值恒定为\(28\)，规律就找到啦

\(if(n > 5)\ n \ \ -= 4\)

\(a\)数组表示原数列
\(a[1] = 325\)
\(a[2] = 473\)
\(a[3] = 649\)
\(a[4] = 853\)
\(a[5] = 1085\)

\(b\)数组表示差
\(b[1] = 148\)
\(b[2] = 176\)
\(b[3] = 204\)
\(b[4] = 232\)
\(.................\)
\(b[n] = 120 + n * 28\)

显然
\(b[2] = b[1] + 28\)
\(b[3] = b[2] + 28\)
\(....................................\)
\(b[n] = b[n - 1] + 28\)

有
\(a[2] - a[1] = b[1]\)
\(a[3] - a[2] = b[2]\)
\(a[4] - a[3] = b[3]\)
\(a[5] - a[4] = b[4]\)
\(.............................\)
\(a[n] - a[n - 1] = b[n - 1]\)

加起来
\(a[2] - a[1] + a[3] - a[2] + a[4] - a[3] + .......... a[n] - a[n - 1] = b[1] + b[2] + b[3] + ......... b[n - 1]\)

去掉多余项，得
\(a[n] - a[1] = \sum_{i = 1}^{n - 1} b[i]\)
设\(x = \sum_{i = 1}^{n - 1} b[i]\)

所以\(a[n] = x + a[1]\)
x是个等差数列，然后等差数列求和公式为\(\frac{首项 + 尾项}{2} *数量\)

这里就是\(\frac{b[1] + b[n - 1]}{2} *(n - 1)\)

所以就是\(\frac{b[1] + b[n - 1]}{2} *(n - 1) + a[1]\)

就等于\(\frac{120 + 28 + 120 + 28 * （n - 1）}{2} *(n - 1) + 325\)

然后化简一下，可能爆\(long\ long\)，保险起见用\(unsigned\ long\ long\)，然后就做完了

//知识点:宽搜打表找规律
/*
By:Loceaner
找到神奇规律之后发现是等差数列……
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#define ull unsigned long long
using namespace std;

int T;
ull n;
ull a[5] = {1, 9, 41, 109, 205};

int main() {
    freopen("horse.in", "r", stdin);
    freopen("horse.out", "w", stdout);
    scanf("%d", &T);
    while(T--) {
        cin >> n;
        if(n < 5) {
            cout << a[n] << "\n";
            continue;
        }
        else {
            n -= 4;
            ull ans = 120 * (n - 1) + 14 * n * (n - 1) + 325;
//          ull ans = (240 + 28 * n) / 2 * (n - 1) + 325;
            cout << ans << '\n';
        }
    }
    return 0;
}