牛客周赛63(C++实现)

🌈个人主页：Yui_
🌈Linux专栏：Linux
🌈C语言笔记专栏：C语言笔记
🌈数据结构专栏：数据结构
🌈C++专栏：C++

比赛链接 比赛链接

1.小红的好数

1.1 题目描述

小红定义一个正整数是“好数”，当且仅当该数满足以下两个性质：

1. 数位恰好为2。
2. 个位数和十位数相同。
   请你判断一个给定的正整数是否是好数？

1.2 思路

直接把数字当成字符串来判断

1.3 代码

#include <iostream>
#include <string>
using namespace std;int main()
{string s;cin >> s;if (s.size() == 2 && s[0] == s[1]){cout << "Yes";}else{cout << "No";}return 0;
}

2.小红的好数组

2.1 题目描述

小红定义一个数组是“好数组”，当且仅当该数组满足以下两个性质：

1. 该数组不是回文数组。
2. 修改恰好一个元素后，该数组变成回文数组。
   所谓回文数组，即将一个数组左右翻转后，和原数组相同，例如[12,3,12]是回文数组。
   现在小红拿到了一个数组，请你帮小红计算有多少个长度为kkk的连续子数组是好数组。
   

2.2 思路

因为数据量很小，直接按题目来判断就可以了，把判断回文数的思路给改一下就是了。

2.3 代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool check(vector<int>& v, int begin, int end)
{int error = 2;while (begin <= end && error != 0) {if (v[begin] != v[end]) {error -= 1;}begin += 1;end -= 1;}return error == 1;
}
int main()
{int n, k;cin >> n >> k;vector<int> v(n);for (int i = 0; i < n; ++i) cin >> v[i];int ans = 0;for (int i = 0; i <= n - k; ++i){if (check(v, i, i + k - 1)) {ans += 1;}}cout << ans << endl;return 0;
}

3.小红的矩阵行走

3.1 题目描述

小红因为太喜欢出“矩阵行走”的题，被小紫关进矩阵里了，她希望你来救救她！
现在给定了一个矩阵，小红初始站在矩阵的左上角。已知小红每次可以向右或者向下走一步，当小红经过一个格子时，她将收集该格子的正整数。小红希望到达右下角时，收集到的所有正整数都相同。你能帮帮她吗？

3.2 思路1(动态规划)

很经典的’‘走迷宫’'题目，不过这里的障碍物就变成了与数组第一个元素不同的元素的位置。了解完后，我们先创建一个dp数组（多开一行再多开一列，这样可以有效的防止越界）。dp[i][j]如果等于-1就代表可以按题目要求走到的位置。
那么我们需要先把d[0][0]初始化为-1。因为[0][0]是绝对可以走到的位置，肯定要初始化为-1.
后续我们遍历数组，当遍历的数组元素为目标元素（vv[0][0]）。判断这个位置是否可以从前一步走过了。因为小红只会向下走和向右走，所以我们只需要判断当前位置的上一行或者上一列就可以了。
最后遍历完后，判断一下dp[n][m]是否等于-1。

3.2 思路2(dfs暴搜)

需要创建与vv相同的数组来表示已经走过的路，为了防止回溯时走回已经走过的路。再创建一个方向数组int dis[2][2] = { {0,1},{1,0} };来表示接下来要走的方向。
开始从vv[0][0]进入dfs。递归的结束条件就是当递归到矩阵的最后一个元素，如果能走到就表示可以走出矩阵。
后面的代码也是回溯的经典代码，先用一个循环来表示接下来要走的方向，在判断这个方向是否合法。

3.3 代码1

#include <iostream>
#include <string>
#include <vector>
#include <cstdbool>
using namespace std;int main()
{int t;cin >> t;while (t--){int n, m;cin >> n >> m;vector<vector<int>> vv(n, vector<int>(m));for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j) cin >> vv[i][j];vector<vector<int>> dp(n+1,vector<int>(m+1));int tmp = vv[0][0];dp[1][1] = -1;for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){if(vv[i-1][j-1] == tmp&&(dp[i-1][j] == -1||dp[i][j-1] == -1)){dp[i][j] = -1;}}}if(dp[n][m] == 0){cout<<"No"<<endl;}else{cout<<"Yes"<<endl;}}return 0;
}

3.3 代码2

#include <iostream>
#include <string>
#include <vector>
#include <cstdbool>
using namespace std;int dis[2][2] = { {0,1},{1,0} };
void dfs(vector<vector<int>>& vv, int a, int b, vector<vector<bool>>& path,bool&ans) {int n = vv.size(), m = vv[0].size();if (a == n - 1 && b == m - 1)ans = true;for (int i = 0; i < 2; ++i) {int x = a + dis[i][0];int y = b + dis[i][1];if (x >= n || y >= m || vv[x][y] != vv[a][b]||path[x][y]) continue;path[x][y] = true;dfs(vv, x, y,path,ans);path[x][y] = false;}
}
int main()
{int t;cin >> t;while (t--){int n, m;cin >> n >> m;vector<vector<int>> vv(n, vector<int>(m));for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j) cin >> vv[i][j];vector<vector<bool>> path(n, vector<bool>(m,false));bool ans = false;path[0][0] = true;dfs(vv, 0, 0,path,ans);if (ans) {cout << "Yes" << endl;}else {cout << "No" << endl;}}return 0;
}

4.小红的行列式构造

4.1 题目描述

小红希望你构造一个3阶行列式，满足每个元素的绝对值不小于1，且行列式的值等于xxx。你能帮帮她吗？

4.2 思路

纯数学，在3阶行列式的计算公式。

因为答案存在很多个，可以假设很多种情况。

4.3 代码

#include <iostream>
#include <string>
#include <vector>
#include <cstdbool>
using namespace std;int main()
{int x = 0;cin>>x;if(x>=0){cout<<"1 1 1"<<endl;cout<<"1 2 1"<<endl;cout<<"1 1 ";cout<<x+1<<endl;}else{cout<<"-1 -1 -1"<<endl;cout<<"-1 -2 -1"<<endl;cout<<"-1 -1 "<<endl;cout<<x-1<<endl;}return 0;
}

文章就先到这里了，欢迎大家的点赞，评论和关注~