1. 第一题,比较简单
#include <bits/stdc++.h> using namespace std; int main() { int n, k; scanf("%d %d", &n, &k); int tmp; k -= 1; for (int i = 0; i < n; i++) { scanf("%d", &tmp); if (k != 0) { printf("%d ", tmp); } k--; } }2. 第二题,求字符串字串的字典序第k小,因为就五个,所以可以直接暴力
#include <bits/stdc++.h> using namespace std; int main(void) { //freopen("data.txt", "r", stdin); char str[5000 + 10]; scanf("%s", str); int k; scanf("%d", &k); map<string, int> ms; string s(str); for (int i = 1; i < 6; i++) { for (int j = 0; j < s.size() && j + i < s.size(); j++) { ms[s.substr(j, i)] = 1; } } for (auto it = ms.begin(); it != ms.end(); it++) { k--; if (k == 0) { cout << it->first << endl; return 0; } } return 0; }
3 . 暴力a了40,用dfs写了一半没时间了
#include <bits/stdc++.h> using namespace std; typedef long long int ll; int dfs(string str) { if (str.empty()) return 0; int tmp = 0; if (str.size() > 1) { if (str[0] != '9') { tmp += 10 + str[0] - '0'; str[1] -= 1; // 需要考虑1000的情况, } else { tmp += 9; } tmp += dfs(str.substr(1, str.size() - 1)); } else { tmp += str[0] - '0'; } return tmp; } int main() { int T; freopen("data.txt", "r", stdin); scanf("%d", &T); while (T--) { ll n; scanf("%lld", &n); string str = to_string(n); reverse(str.begin(),str.end()); cout << dfs(str) << endl; } return 0; }
4. 求最少粉刷次数,递归+分治,分治的思路,就是每次按照最小的位置进行切分,比如2 2 1 2 1可以分成 2 2 和 2
#include <bits/stdc++.h> using namespace std; typedef long long int ll; vector<vector<int>> dp; int dfs(vector<ll> v, int s, int e) { if (s > e) return 0; if (dp[s][e]) return dp[s][e]; ll min_v = LLONG_MAX; for (int i = s; i <= e; i++) { min_v = min(v[i], min_v); } int cnt = min_v; int pre_pos = s; for (int i = s; i <= e; i++) { v[i] -= min_v; if (v[i] == 0) { cnt += dfs(v, pre_pos, i-1); pre_pos = i + 1; } v[i] += min_v; } cnt += dfs(v,pre_pos, e); dp[s][e] = min(cnt,e-s+1); return dp[s][e]; } int main() { int n; scanf("%d", &n); vector<ll> v(n); dp.resize(n, vector<int>(n)); for (int i = 0; i < n; i++) { scanf("%lld", &v[i]); } for (int i = 0; i < n; i++) { dp[i][i] = 1; } cout << dfs(v, 0, v.size() - 1) << endl; return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long int ll; int check(string& str, int i, int j) { int p = j - i + 1; while (i < j) { if (str[i] != str[j]) { return p; } i++; j--; } return 1; } int main() { string str; cin >> str; vector<vector<int>> dp; dp.resize(str.size(), vector<int>(str.size())); for (int i = 0; i < str.size(); i++) { for (int j = 0; j < str.size(); j++) { dp[i][j] = check(str, i, j); } } // dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]) for (int i = 0; i < str.size(); i++) { for (int j = i + 1; j < str.size(); j++) { for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); } } } int Q; scanf("%d", &Q); int l, r; while (Q--) { scanf("%d %d", &l, &r); printf("%d\n", dp[l - 1][r - 1]); } return 0; }
全部评论
(0) 回帖