Codeforces-Round #731 (Div. 3)

Author： yfx
发布时间：August 1, 2021
803 views
No comments
3359 words
Categories：算法 C/C++

<div class="tip share">请注意，本文编写于 1393 天前，最后修改于 1375 天前，其中某些信息可能已经过时。</div>

# Problem A - [Shortest Path with Obstacle](https://codeforces.com/contest/1547/problem/A)

## 方法一：思维

> 题目理解：
>
> 在一个方格中有A, B, F三个点，求从A点到B点的最短路径，其中F点不可走
>
> 分析：
>
> 先假设没有F点，那么从A到B的最短路径为$|x_a-x_b|+|y_a-y_b|$，若有F点的情况怎么办？若A,B不共线可以发现，若选的路径被F阻塞那么可以对称的找到另一条路径，若A,B共线则只需要多走2步即可

### 参考代码：

```cpp
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

using PII = pair<int, int>;

const int N = 1010;

int T;
PII A, B, F;

int main() {
  
    cin >> T;
    while (T -- ) {
        int a, b;
        scanf("%d%d", &a, &b); A = {a, b};
        scanf("%d%d", &a, &b); B = {a, b};
        scanf("%d%d", &a, &b); F = {a, b};
        int ans = abs(A.x - B.x) + abs(A.y - B.y);
        if (A.x == F.x && B.x == F.x && (A.y > F.y && F.y > B.y || A.y < F.y && F.y < B.y)) {
            ans += 2;
        } else if (A.y == F.y && B.y == F.y && (A.x > F.x && F.x > B.x || A.x < F.x && F.x < B.x)) {
            ans += 2;
        }
        printf("%d\n", ans);
    }
  
    return 0;
}
```

# Problem B - [Alphabetical Strings](https://codeforces.com/contest/1547/problem/B)

## 方法一：思维

> 题目理解：
>
> 给定一个字符串，判定其是否是通过如下方式得到：
>
> * 从字母a-z一次添加到字符串每次只能添加到字符串的左边或者右边
>
> 若满足则输出`YES`否则`NO`
>
> 分析：
>
> 设字符串的长度为n，那么该字符串只包含第1-n个小写字母才合法。我们可以从n遍历至1即当前最大的字母一定是在最外面的左边或者右边否则不合法。

### 参考代码：

```cpp
#include <bits/stdc++.h>

#define mkp(A,B) make_pair(A,B)
#define endl '\n'
#define x first
#define y second

using namespace std;

using PII = pair<int, int>;
using LL = long long;

const int N = 110;

int T;
string s;

bool solve() {
    int n = s.size();
    int l = 0, r = n - 1;
    for (int i = n - 1; i >= 0; -- i) {
        char c = 'a' + i;
        if (s[l] == c) ++ l;
        else if (s[r] == c) -- r;
        else return false;
    }
    return true;
}

int main() {
  
    cin >> T;
    while (T -- ) {
        cin >> s;
        if (solve()) puts("YES");
        else puts("NO");
    }
  
    return 0;
}
```

# Problem C - [Pair Programming](https://codeforces.com/contest/1547/problem/C)

## 方法一：贪心

> 题目理解：
>
> 给定一个正整数k，两个只包含正整数的数组a和b，长度分别为n和m。把两个数组在不改变其在原数组内的相对顺序的情况下合并成一个数组c，其中元素0表示把k加1，非0元素得满足小于当前的k。给出任意一个满足条件的数组c，若没有则输出-1
>
> 分析：
>
> 因为不能改变相对顺序所有两个数组都只能从左往右来合并，若当前元素是0若先把0放进去不会使c不满足条件，且使c更可能满足要求，所以我们设立两个指针，先把0放进队伍中然后把a和b中满足要求的放入队伍中。便可以满足要求，若此时两个元素都大于k则无法找到这样的数组c直接退出即可。

### 参考代码：

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int T;
int k, n, m;
int a[N], b[N];

bool solve(vector<int>& ans) {
    int i1 = 0, i2 = 0;
    while (i1 != n || i2 != m) {
        if (i1 != n && a[i1] == 0) {
            ans.push_back(0);
            ++ i1, ++ k;
        } else if (i2 != m && b[i2] == 0) {
            ans.push_back(0);
            ++ i2, ++ k;
        } else if (i1 != n && a[i1] <= k) ans.push_back(a[i1 ++]);
        else if (i2 != m && b[i2] <= k) ans.push_back(b[i2 ++]);
        else return false;
    }
    return true;
}

int main() {
  
    cin >> T;
    while (T -- ) {
        scanf("%d%d%d", &k, &n, &m);
        for (int i = 0; i < n; ++ i) scanf("%d", a + i);
        for (int i = 0; i < m; ++ i) scanf("%d", b + i);

vector<int> ans;
        if (solve(ans)) {
            for (int x : ans)
                printf("%d ", x);
            puts("");
        } else puts("-1");
    }
  
    return 0;
}
```

Last modification：August 18, 2021

看着给点？(●'◡'●)？

Codeforces-Round #731 (Div. 3)

yfx • 2021 年 08 月 01 日

<div class="tip share">请注意，本文编写于 1393 天前，最后修改于 1375 天前，其中某些信息可能已经过时。</div>

# Problem A - [Shortest Path with Obstacle](https://codeforces.com/contest/1547/problem/A)

## 方法一：思维

### 参考代码：

```cpp
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

using PII = pair<int, int>;

const int N = 1010;

int T;
PII A, B, F;

# Problem B - [Alphabetical Strings](https://codeforces.com/contest/1547/problem/B)

## 方法一：思维

### 参考代码：

```cpp
#include <bits/stdc++.h>

#define mkp(A,B) make_pair(A,B)
#define endl '\n'
#define x first
#define y second

using namespace std;

using PII = pair<int, int>;
using LL = long long;

const int N = 110;

int T;
string s;

int main() {
  
    cin >> T;
    while (T -- ) {
        cin >> s;
        if (solve()) puts("YES");
        else puts("NO");
    }
  
    return 0;
}
```

# Problem C - [Pair Programming](https://codeforces.com/contest/1547/problem/C)

## 方法一：贪心

### 参考代码：

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int T;
int k, n, m;
int a[N], b[N];

vector<int> ans;
        if (solve(ans)) {
            for (int x : ans)
                printf("%d ", x);
            puts("");
        } else puts("-1");
    }
  
    return 0;
}
```

Codeforces-Round #731 (Div. 3)

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

本站Handsoem主题的美化教程

宝塔网站nginx反向代理避坑

纪元1800.DLC完全解锁补丁【正版适用】-2023.11.14

LeetCode-高效制胜-两数之和

LeetCode-高效制胜-两数之和 II - 输入有序数组

算法题模板

LeetCode-高效制胜-两数之和

LeetCode-第251场周赛

LeetCode-二叉树中第二小的节点

LeetCode-二叉树中所有距离为 K 的结点

Codeforces-Round #731 (Div. 3)

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Codeforces-Round #731 (Div. 3)

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款