题解 CF1459B 【Move and Turn】
Warriors_Cat
2020-12-23 16:37:51
[题面传送门](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;
}
```