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

B. Adjacency List（排序）

题意：

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

思路：

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

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;vector 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;
}

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());for (int i = 1; i <= n; i++)cout << a[i] << ' ';cout << endl;return 0;
}

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

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

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

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

代码如下所示：

#include 
using namespace std;
const int N = 310;int main()
{int n;cin >> n;vector 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;
}

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

题意：

给定 n 个数 a1∼ana_1∼a_na1​∼an​ ，一次操作可以任选一个数除以 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;
}

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