题解 CF1459B 【Move and Turn】

[题面传送门](https://www.luogu.com.cn/problem/CF1459B)。 题意可以从上面看。 --- ### $Solution:$ ~~众所周知，看到这种输入量少的题，我们应当找规律。——WYXkk~~ 考虑将小数据[打表](https://www.luogu.com.cn/paste/x2c9bwl4)，观察其性质。 然后我们就会发现： 当 $n$ 是奇数时，能到达的点和不能到达的点刚好交错开来，这时答案为 $\dfrac{(n + 2) * (n + 2) - 1}{2}$； 当 $n$ 是偶数时，将这些 `1` 压缩刚刚好成一个正方形，其边长为 $\dfrac{n}{2}+1$，于是答案为 $(\dfrac{n}{2}+1)^2$。 证明的话，直接归纳即可。对于每一个 $n$，$n + 2$ 的情况就相当于 $n$ 的所有 `1` 走一个 $2 \times 2$ 的对角线。 over，时间复杂度为 $O(1)$。 --- ### $Code:$ 以下为赛时代码。 ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> #include <cmath> using namespace std; #define ll long long #define fi first #define se second #define y1 y_csyakioi_1 #define y0 y_csyakioi_0 #define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1; inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); } return x * f; } const int N = 1010; int n; inline void work(){ n = read(); if(n & 1) printf("%d\n", ((n + 2) * (n + 2) - 1) / 2); else printf("%d\n", (n / 2 + 1) * (n / 2 + 1)); } int main(){ int t = 1; while(t--) work(); return 0; } ```