4A - Horse

佚名 6年前 (2019-04-19) 随笔 2122人围观抢沙发百度已收录

打表找规律

#include <iostream>
#include <queue>
using namespace std;
bool vis[2002][2002];
int dx[8]{1, 1, 2, 2, -1, -1, -2, -2};
int dy[8]{2, -2, 1, -1, 2, -2, -1, 1};
struct point
{
    int x;
    int y;
    int deep;
};
queue<point> q;

int bfs(int n)
{
    while (!q.empty())
        q.pop();
    memset(vis, false, sizeof(vis));
    point head;
    head.x = head.y = 1000;
    head.deep = 1;
    q.push(head);
    vis[head.x][head.y] = true;


    int sum = 1;
    while (!q.empty()) {
        head = q.front();
        q.pop();
        point np;
        for (int i = 0; i < 8; i++) {
            np.x = head.x + dx[i];
            np.y = head.y + dy[i];
            np.deep = head.deep + 1;
            if (np.x >= 0 && np.x <= 2000 && np.y >= 0 && np.y <= 2000 && !vis[np.x][np.y] && np.deep <= n) {
                vis[np.x][np.y] = true;
                q.push(np);
                sum++;
            }
        }
    }
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int arr[20];
    for (int i = 1; i <= 20; i++) {
        arr[i] = bfs(i);
        cout << arr[i] << ' ';
    }
    cout << endl;
    int b[10];
    int k = 0;
    for (int i = 2; i <= 20; i++) {
        b[k] = arr[i] - arr[i - 1];
        cout << b[k++] << ' ';
    }
    cout << endl;
    for (int i = 2; i < k; i++)
        cout << b[i] - b[i - 1] << ' ';
    cout << endl;
    return 0;
}

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

打表发现第五项205开始，后一项减前一项的差值(第二排)，再与之后的差值做差值，值都是28.

最终结果:

#include <iostream>
using namespace std;
typedef unsigned long long ull;
int arr[] {0, 1, 9, 41, 109};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        ull n;
        cin >> n;
        if (n < 5)
            cout << arr[n] << endl;
        else {
            ull diff = n - 5;
            cout << 205 + diff * 120 + (diff - 1) * diff * 14 << endl;
        }
    }
    return 0;
}