A40211. 咫尺天涯
填空题
困难
知识点
题目描述
咫尺天涯
题目描述
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3 × 3 的方格中的每一个格子，最终到达右上角的一条曲线。
设每个格子的边长为 1，在上图中，有的相邻的方格（四相邻）在皮亚诺曲线中也是相邻的，在皮亚诺曲线上的距离是 1，有的相邻的方格在皮亚诺曲线中不相邻，距离大于 1。
例如，正中间方格的上下两格都与它在皮亚诺曲线上相邻，距离为 1，左右两格都与它在皮亚诺曲线上不相邻，距离为 3。
下图给出了皮亚诺曲线的 2 阶情形，它是经过一个3^2× 3 ^2 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。
下图给出了皮亚诺曲线的 3 阶情形，它是经过一个 3^3 × 3 ^3 的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。
皮亚诺曲线总是从左下角开始出发，最终到达右上角。
小蓝对于相邻的方格在皮亚诺曲线上的相邻关系很好奇，他想知道相邻的方格在曲线上的距离之和是多少。
例如，对于 1 阶皮亚诺曲线，距离和是 24，有 8 对相邻的方格距离为 1， 2 对相邻的方格距离为 3，2 对相邻的方格距离为 5。
再如，对于 2 阶皮亚诺曲线，距离和是 816。请求出对于 12 阶皮亚诺曲线，距离和是多少。
提示：答案不超过 10^18。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
参考答案
#include <bits/stdc++.h>
using namespace std;
#define POW2(X) (1 << (X))
#define CKBIT(S, X) (((S)&POW2(X)) != 0)
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T> inline void ckmin(T & a, T b) {
a = min(a, b);
}
template <class T> inline void ckmax(T & a, T b) {
a = max(a, b);
}
template <class T> inline T sqr(T x) {
return x * x;
}
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A, B) make_pair(A, B)
#define PB(X) push_back(X)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define ALL(A) A.begin(), A.end()
template <class T> int CMP(T a[], const T b[], int n) {
return memcmp(a, b, n * sizeof(T));
}
template <class T> void COPY(T a[], const T b[], int n) {
memcpy(a, b, n * sizeof(T));
}
template <class T> void SET(T a[], int val, int n) {
memset(a, val, n * sizeof(T));
}
using uint = unsigned int;
using int64 = long long;
using uint64 = unsigned long long;
using ipair = pair<int, int>;
using VI = vector<int>;
using VD = vector<double>;
using VVI = vector<VI>;
using VS = vector<string>;
const int MOD = 1000000007;
using ll = long long;
using namespace std;
int main() {
ll dots = 1;
int N = 12;
cout << endl;
unordered_map<ll, ll> h, v;
while (N-- > 0) {
unordered_map<ll, ll> ht, vt;
ht[1] = 6 * dots;
vt[3] = vt[5] = vt[1] = 2 * dots;
dots *= 9;
for (auto & p : v) {
if (p.first % 4 == 1) {
int d = (p.first - 1) * 9;
ht[d + 1] += p.second;
ht[d + 3] += p.second;
ht[d + 5] += p.second;
}
else {
int d = (p.first + 1) * 9;
ht[d - 1] += p.second;
ht[d - 3] += p.second;
ht[d - 5] += p.second;
}
}
for (auto & p : h) {
if (p.first % 4 == 1) {
int d = (p.first - 1) * 9;
vt[d + 1] += p.second;
vt[d + 11] += p.second;
vt[d + 13] += p.second;
}
else {
int d = (p.first + 1) * 9;
vt[d - 1] += p.second;
vt[d - 11] += p.second;
vt[d - 13] += p.second;
}
}
h = move(ht);
v = move(vt);
}
ll res = 0;
for (auto & p : h) res += p.first * p.second;
for (auto & p : v) res += p.first * p.second;
cout << res;
}答案解析
答案为：23769050146281024
上一题
下一题