Codeforces Round #691 (Div. 2) B. Move and Turn

发表于 更新于 分类于

链接

https://codeforces.com/contest/1459/problem/B

题意

一个机器人可以水平或垂直移动，不能连续水平或连续垂直移动，若移动 $n$ 步，能到达多少个不同的终点？

思路

  • 当 $n$ 为偶数时：

水平移动 $n/2$ 步，在水平方向上最多可能到达 $n/2+1$ 个终点；

垂直移动 $n/2$ 步，在垂直方向上最多可能到达 $n/2+1$ 个终点。

组合后共有 $(n/2+1)(n/2+1)$ 个点。

  • 当 $n$ 为奇数时：

水平移动 $n/2+1$ 步，在水平方向上最多可能到达 $n/2+2$ 个终点；

垂直移动 $n/2$ 步，在垂直方向上最多可能到达 $n/2+1$ 个终点。

组合后共有 $(n/2+1)(n/2+2)$ 个点。

垂直移动 $n/2+1$ 步，在垂直方向上最多可能到达 $n/2+2$ 个终点；

水平移动 $n/2$ 步，在水平方向上最多可能到达 $n/2+1$ 个终点。

组合后共有 $(n/2+1)(n/2+2)$ 个点。

这些点是不重复的，所以共有 $2(n/2+1)(n/2+2)$ 个点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
int main() {
    //freopen("E:/OneDrive/IO/in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int k=n/2;
    if(n&1) cout<<2*(k+1)*(k+2)<<'\n';
    else cout<<(k+1)*(k+1)<<'\n';
    return 0;
}