目錄
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();
}
