牛客周赛63(C++实现)
1.小红的好数
1.1 题目描述
小红定义一个正整数是“好数”，当且仅当该数满足以下两个性质：
- 数位恰好为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 题目描述
小红定义一个数组是“好数组”，当且仅当该数组满足以下两个性质：
- 该数组不是回文数组。
- 修改恰好一个元素后，该数组变成回文数组。 所谓回文数组，即将一个数组左右翻转后，和原数组相同，例如[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;
}文章就先到这里了，欢迎大家的点赞，评论和关注~
腾讯云开发者
