A - Rightmost
题意：
给定一个字符串，确定字母a，最后出现的位置，若字符串中没有出现字母a，则输出-1
思路：
遍历统计
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int ans = -1;
for (int i = 0; i <= s.size(); i ++ ) {
if(s[i] == 'a') {
ans = i;
}
}
if(ans == -1) cout << -1 << endl;
else {
cout << ans + 1 << endl;
}
return 0;
}
B - Adjacency List
题意：
在一个n个点，m条边的图中，打印每个点直接相连的点（升序）
思路：
用vector存储每个边的直接相邻点
时间复杂度：O（m）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector<int> v[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i ++ ) {
int a, b;
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
for (int i = 1; i <= n; i ++ ) {
cout << v[i].size() << " ";
sort(v[i].begin(), v[i].end());
for (int j = 0; j < v[i].size(); j ++ ) {
cout << v[i][j] << " ";
}
cout << "\n";
}
return 0;
}
C - Previous Permutation
题意：
按照规定给予一个序列，打印按照字典序从小到大排序该序列的上一个序列
思路：prev_permutation直接过，（手动模拟的思路有些问题，只能过一半的数据）
时间复杂度：prev_permutation和next_permutation的时间复杂度是O（n）
代码；
#include <bits/stdc++.h>
using namespace std;
const int N = 200;
int a[N];
bool vis[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
prev_permutation(a + 1, a + 1 + n);
for (int i = 1; i <= n; i ++ ) {
cout << a[i];
if(i == n) cout << endl;
else cout << " ";
}
return 0;
}
Divide by 2 or 3
题意：
给定一个数组，对于数组的每一个元素你这可以执行两种操作
1、若a[i] % 2 == 0,你可以用 a[i] / 2 代替 a[i]
2、若a[i] % 3 == 0,你可以用 a[i] / 3 代替 a[i]
若是使得数组中所以元素都相同，你所需的最小操作数是多少，若不行则输出-1
思路：
如果最后能一样，说明a1~an中都可以化为 a1 = b1 * x...。因此a1an中肯定有一个最小的公倍数并且是公共的。而且如果最后能化成一样，说明b1bn都是2的倍数或者3的倍数否则无法除到x。
时间复杂度：O（n）
代码：
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a % b);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
bool flag = false;
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
}
int ans = 0;
int temp = 0;
for (int i = 0; i < n; i ++ ) {
temp = gcd(temp, a[i]);
}
for (auto &x : a) {
x /= temp;
for (; x % 2 == 0; x /= 2) {
ans ++ ;
}
for (; x % 3 == 0; x /= 3) {
ans ++ ;
}
if(x != 1) flag = true;
}
if(flag) {
cout << -1 << endl;
}
else {
cout << ans << endl;
}
return 0;
}
E - Round Trip
题意：
在一个H * W的矩阵中，有障碍物、路和起点，问是否存在一个简单路径重新回到起点，并且路径的长度要大于等于4
思路：
由于数据给定比较特殊所以使用vector来存储，保证图的完整，然后从起点dfs，注意这里的需要排除一些特殊情况，
当离开起点1个单位的时候，若是下一个点在沿着这个方向走回来，那路径就是2，所以需要排除这种情况
时间复杂度：O（H * M）
代码：
#include <bits/stdc++.h>
using namespace std;
#define inf 1e9
const int N = 1e6 + 5;
vector<char> a[N];
vector<int> dis[N];
vector<int> vis[N];
int n, m;
int xx, yy;
int ans;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void dfs(int x, int y, int s) {
//找到了
if(x == xx && y == yy && s >= 4) {
ans = 1;
return ;
}
if(s <= dis[x][y]) return ;
dis[x][y] = s;
for (int k = 0; k < 4; k ++ ) {
int i = x + dx[k];
int j = y + dy[k];
if(i < 1 || i > n || j < 1 || j > m) continue;
if(a[i][j] == '#' || vis[i][j]) continue;
if((!(i == xx && j == yy)) || s + 1 >= 4) {
vis[i][j] = 1;
dfs(i, j, s + 1);
vis[i][j] = 0;
}
if(ans) return ;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
a[i].push_back(' ');
vis[i].push_back(0);
dis[i].push_back(0);
for (int j = 1; j <= m; j ++ ) {
char str;
cin >> str;
a[i].push_back(str);
vis[i].push_back(0);
dis[i].push_back(-inf);
if(str == 'S') {
xx = i, yy = j;
dis[i][j] = -1;
}
}
}
dfs(xx, yy, 0);
if(ans) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}