AtCoder Beginner Contest 276 (A~E)

A. Rightmost（遍历）

题意：

给定一个全是小写字母的字符串，问最后一个 a 出现的位置。

思路：

遍历字符串，有 a 就更新位置，没有则输出 -1.

代码如下：

#include 
using namespace std;

int main()
{
    string s;
    cin >> s;
    int len = s.size();
    int res = -1;
    for (int i = 0; i < len; i++){
        if (s[i] == 'a')
            res = i + 1;
    }

    cout << res << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

B. Adjacency List（排序）

题意：

给定 n 个点（编号从 1 ~ n）和 m 条边，每条边连接两个顶点。要求判断每个顶点所对应的边数，若有则输出边数并将所能到达的点按编号升序输出，否则输出 0.

思路：

二维 vector 存储每个点所连的边，并将每条边对应的点依次从小到大排序即可。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;

vector<int> v[N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for (int i = 1; i <= n; i++){
        sort(v[i].begin(), v[i].end());
    }

    for (int i = 1; i <= n; i++){
        if (v[i].size() == 0){
            cout << 0 << endl;
        }
        else {
            cout << v[i].size() << ' ';
            for (int j = 0; j < v[i].size(); j++)
                cout << v[i][j] << ' ';
            cout << endl;
        }
    }

    return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38

---

C. Previous Permutation（全排列）

题意：

给定 n，接着给定一个长度为 n 的全排列，要求输出该全排列的按 字典序 排列的上一个全排列。

思路：

按字典序排列的全排列，必定是依次对于每个数的升序排列，所以只需要找到非升序排列的元素位置，将其替换为上一个数，而后面的数按照降序来排列即可。

先遍历一遍，找到最后一个 前一个元素大于后一个元素 的位置，记录下前一个数的位置 pos ，接着从后往前遍历，找到后面元素中第一个小于 a[pos] 的数，交换两个数，再对 a[pos] 后面的全部元素按降序排列即可。

代码如下：

#include 
using namespace std;
const int N = 310;

int a[N];

int main()
{
    int n;
    cin >> n;

    int pos = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (a[i - 1] > a[i]){
            pos = i - 1;
        }
    }

    for (int i = n; i >= 1; i--){
        if (a[i] < a[pos]){
            swap(a[i], a[pos]);
            break;
        }
    }

    sort(a + pos + 1, a + n + 1, greater<int>());

    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    cout << endl;
    
    return 0;
}
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
27
28
29
30
31
32
33
34

当然 C++ 强大的 STL 提供了一种直接跳题的方法：

next_permutation() 用于求前一个全排列

prev_permutation() 用于求后一个全排列（均按照字典序排列）

如果排的是结构体需要重载 < 运算符

代码如下所示：

#include 
using namespace std;
const int N = 310;

int main()
{
    int n;
    cin >> n;

    vector<int> v;

    for (int i = 0; i < n; i++){
        int x;
        cin >> x;
        v.push_back(x);
    }

    prev_permutation(v.begin(), v.end());

    for (auto x : v)
        cout << x << ' ';
    cout << endl;

    return 0;
}
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

---

D. Divide by 2 or 3（分解质因数）

题意：

给定 n 个数 $a_1\sim a_n$ ，一次操作可以任选一个数除以 2 或 3 ，要求使得所有数都相等的最小操作次数。

思路：

首先，使得所有数都相等的最优方案一定是它们的 最大公约数，所以我们先将整体的最大公约数求出来。

然后对于剩下的数，依次进行拆分，分别除以 2 和 3 并记录次数，如果能被完全分解则代表满足要求，输出次数即可。只要有一个数不能被完全分解，则代表不可行，输出 -1.

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 1010;

int gcd(int a, int b)  //辗转相除法求最大公约数
{
    return b ? gcd(b, a % b) : a;
}

int a[N];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int g = 0;
    for (int i = 1; i <= n; i++)
        g = gcd(g, a[i]);

    int f = true;
    int res = 0;
    for (int i = 1; i <= n; i++){
        a[i] /= g;
        while (a[i] % 2 == 0){
            a[i] /= 2;
            res++;
        }
        while (a[i] % 3 == 0){
            a[i] /= 3;
            res++;
        }

        if (a[i] != 1) f = false;
    }

    if (f) cout << res << endl;
    else cout << -1 << endl;
    
    return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

E. Round Trip（DFS）

题意：

给定一个大小为 n × m 的网格图，起点为 S，道路为 .，障碍物为 #。

每次只能上下左右四个方向移动，询问是否能够从起点出发，不经过重复的点回到起点。

思路：

DFS 搜索即可。

用二维数组 mp[N][N] 存图，用 vis[N][N] 作为标记数组，表示走过的点。

先在起点判断四个方向是否可走，再用 DFS 从四个方向依次搜索即可。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 3e4 + 10;

int n, m;
char mp[N][N];
bool vis[N][N];
int sx, sy;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

bool dfs(int x, int y, int res)
{
    if (vis[x][y] || mp[x][y] == '#') return false;
    if (x == sx && y == sy && res > 1) return true;

    vis[x][y] = true;
    for (int i = 0; i < 4; i++){
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            if (xx == sx && yy == sy && res == 0) continue;
            if (mp[xx][yy] == '#' || mp[x][y] == '#') continue;
            if (dfs(xx, yy, res + 1)) return true;
        }
    }

    return false;
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> mp[i][j];
            if (mp[i][j] == 'S'){
                sx = i;
                sy = j;
            }
            if (mp[i][j] == '#')
                vis[i][j] = true;
        }
    }

    for (int i = 0; i < 4; i++){
        int x = sx + dx[i], y = sy + dy[i];
        if (x >= 1 && x <= n && y >= 1 && y <= m){
            if (dfs(x, y, 0)){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;

    return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

---