本文主要是介绍C++笔试强训day19,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
1.小易的升级之路
2.礼物的最大价值
3.对称之美
1.小易的升级之路
链接
模拟就行,唯一可能是难点得就是gcd(最大公约数)
#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int arr[N];
int gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b);
}
signed main() {int n, init;cin >> n >> init;for (int i = 0; i < n; ++i)cin >> arr[i];for (int i = 0; i < n; ++i)if (init >= arr[i])init += arr[i];elseinit += gcd(init, arr[i]);cout << init << endl;return 0;
}
2.礼物的最大价值
链接
动态规划 - 路径问题。
typedef long long LL;
class Solution {
public:const static int N = 300;LL dp[N][N] = { 0 };int maxValue(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];return dp[n][m];}
};
3.对称之美
链接
从第1个字符串一直到第n个字符串每个串取一个字母来构成一个新字符串,新字符串的第i个字母只能从第i行的字符串中选出。
根据题意:
我们可以从两边开始(一个下标为0, 一个下标为 n - 1)开始遍历,如果一路遍历下来,所有的两边两个字符串中都有相同的字符,则返回Yes,若有一个没有则No
详细代码:
#include <iostream>
#include <vector>
using namespace std;
vector<string> vs(110);
// 哈希判断是否有相同字符
bool Check(string s, string t)
{int hash[128] = { 0 };for (auto c : s)hash[c]++;for (auto c : t)if (hash[c] != 0)return true;return false;
}
// 双指针
void solve()
{int n;cin >> n;for (int i = 0; i < n; ++i)cin >> vs[i];int flag = 1;int l = 0, r = n - 1;while (l < r){if (!Check(vs[l], vs[r]))flag = 0;l++;r--;}if (flag == 1)cout << "Yes" << endl;elsecout << "No" << endl;
}
int main() {int t;cin >> t;while (t--)solve();
}
这篇关于C++笔试强训day19的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!