误操作删帖了,惨。
1. 白给
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using LL = long long; const int maxn = 1001000; int n, k, val; signed main() { // freopen("in", "r", stdin); // freopen("out", "w", stdout); while (~scanf("%d%d",&n,&k)) { int x; for (int i = 1; i <= n; i++) { scanf("%d", &x); if (i == k) continue; printf("%d ", x); } printf("\n"); } return 0; }
2. top k的k小于等于5,所以需要维护一个数据结构保留字典序最小的5个,但是要考虑去重。n^2logn惨遭卡常,于是我把内层的循环砍掉一半竟然hack过去了。。。
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using LL = long long; const int maxn = 5050; char s[maxn]; int n, k; vector<int> pos[257]; signed main() { // freopen("in", "r", stdin); // freopen("out", "w", stdout); while (~scanf("%s", s + 1)) { scanf("%d", &k); n = strlen(s + 1); set<string> vis; for (int i = 1; i <= n; i++) { string tmp; for (int j = i; j <= min(n, 2500); j++) { tmp += s[j]; if (vis.find(tmp) != vis.end()) continue; vis.emplace(tmp); if (vis.size() > k) vis.erase(*vis.rbegin()); } } printf("%s\n", vis.rbegin()->c_str()); } return 0; }
3. 贪心,令一个数的形式为999...999,另一个数就无所谓了,不过不会证明。
#include <bits/stdc++.h> using namespace std; using LL = long long; LL n; LL gao(LL x) { LL ret = 0; while (x) { ret += x % 10; x /= 10; } return ret; } signed main() { // freopen("in", "r", stdin); // freopen("out", "w", stdout); int T; scanf("%d", &T); while (T--) { scanf("%lld", &n); LL a = 0; while (a <= n) { a = a * 10 + 9; } a /= 10; printf("%lld\n", gao(a) + gao(n - a)); } return 0; }
4. 一开始想区间dp,维护f(l,r)为粉刷区间[l,r]内的最少步数,转移的时候直接考虑每一个都竖着刷(r-l+1次)以及横着刷min{a[k]}次,发现是n^3,其实每次如果横着刷这个区间肯定都被刷完了,所以直接刷掉就行,于是这个问题就不用区间dp了。
#include <bits/stdc++.h> using namespace std; using LL = long long; const int maxn = 5050; int n; int a[maxn]; int f[maxn][maxn]; int dfs(int l, int r) { if (l > r) return 0; if (~f[l][r]) return f[l][r]; int k = l; for (int i = l + 1; i <= r; i++) { if (a[i] < a[k]) k = i; } int ret = a[k]; for (int i = l; i <= r; i++) { a[i] -= ret; } return f[l][r] = min(r - l + 1, dfs(l, k - 1) + dfs(k + 1, r) + ret); } signed main() { // freopen("in", "r", stdin); // freopen("out", "w", stdout); while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } memset(f, -1, sizeof f); printf("%d\n", dfs(1, n)); } return 0; }
5. 维护f(l,r)表示字符串从l起始,并且长度为r时所能构成的最少回文串数,每次枚举l,在以l为起点的后缀串做DP,当[i,j]为一个回文串时更新f[i] = min(f[i], f[j - 1] + 1). 判字符串回文可以用字符串哈希,也可以马拉车。整体复杂度为n^3
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using LL = long long; using ULL = unsigned long long; const ULL M = 1145141919810; const int maxn = 440; int n, q; string s; vector<vector<int>> f; void gao(const string& s, vector<int>& f) { int n = s.length(); for (int i = 0; i <= n; i++) { f[i] = i; } vector<ULL> h1(n + 1, 0), h2(n + 1, 0), mul(n + 1, 0); mul[0] = 1, mul[1] = M; for (int i = 2; i <= n; i++) { mul[i] = mul[i - 1] * M; } for (int i = 0; i < n; i++) { h1[i + 1] = h1[i] * M + s[i] - 'a'; h2[i + 1] = h2[i] * M + s[n - i - 1] - 'a'; } auto ok = [&](int i, int j) { int len = j - i + 1; ULL a = h1[j + 1] - h1[i] * mul[len]; ULL b = h2[n - i] - h2[n - j - 1] * mul[len]; return a == b; }; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { if (ok(j - 1, i - 1)) { f[i] = min(f[i], f[j - 1] + 1); } } } } signed main() { // freopen("in", "r", stdin); // freopen("out", "w", stdout); while (cin >> s) { n = s.length(); for (int i = 0; i <= n; i++) { f.emplace_back(vector<int>(n + 1, 1E6)); } for (int k = 1; k <= n; k++) { string t; for (int i = k; i <= n; i++) { t += s[i - 1]; } gao(t, f[k]); } scanf("%d", &q); while (q--) { int l, r; scanf("%d %d", &l, &r); printf("%d\n", f[l][r - l + 1]); } } return 0; }
全部评论
(3) 回帖