7-1 气球升起来
#include #include #include using namespace std; const int N = 1010; int n; string str; map mp; int main() { while (cin >> n) { for (int i = 0; i < n; i ++) { cin >> str; mp[str] ++; } string res; int cnt = 0; for (auto item : mp) { if (cnt < item.second) { res = item.first; cnt = item.second; } } cout << res << endl; mp.clear(); } return 0; }
7-2 集合A-B
#include #include #include using namespace std; int t, n, m; set arr1, arr2; int x, i; int main() { cin >> t; while (t --) { cin >> n >> m; int f = 0; for (i = 0; i < n; i ++) cin >> x, arr1.insert(x); for (i = 0; i < m; i ++) cin >> x, arr2.insert(x); set res; for (auto it : arr1) { if (arr2.find(it) != arr2.end()) { } else { res.insert(it); if (f) cout << ' '; cout << it, f = 1; } } if (!f) cout << "NULL"; cout << endl; arr1.clear(); arr2.clear(); } return 0; }
7-3 排队
#include #include using namespace std; const int N = 1010; int n, arr[N]; int x; int main() { cin >> n; for (int i = 0; i < n; i ++) { cin >> arr[i]; } cin >> x; sort(arr, arr + n); int l = 0, r = 0, f = 0; for (int i = 0; i < n; i ++) { if (arr[i] == x && f == 0) l = i + 1, f = 1; if (arr[i] == x) r = i + 1; } cout << l << ' ' << r << endl; return 0; }
7-4 办事大厅排队
#include using namespace std; const int N = 100010; string str, q[N]; int n, h, t = -1; int main() { int n; cin >> n; while (n --) { cin >> str; if (str == "in") { cin >> str; q[ ++ t] = str; } else if (str == "out"){ h ++; } else { if (h > t) cout << "NULL" << endl; else cout << q[h] << endl; } } return 0; }
#include using namespace std; const int N = 20010; int n, max_num, min_num, x; int a = -0x3f3f3f3f, b = 0x3f3f3f3f; int main() { cin >> n; for (int i = 0; i < n; i ++) { cin >> x; if (x > a) a = x, max_num = 1; else if (x == a)max_num ++; if (x < b) b = x, min_num = 1; else if (x == b) min_num ++; } cout << b << ' ' << min_num << endl; cout << a << ' ' << max_num << endl; return 0; }
#include #include using namespace std; const int N = 1010; int n, m; string str1, str2; mapmp; int main() { cin >> n >> m; for (int i = 0; i < n; i ++) { cin >> str1 >> str2; mp[str2] = str1; } for (int i = 0 ; i < m; i ++) { cin >> str1; if (mp.count(str1)) cout << mp[str1] << endl; else cout << "eh" << endl; } return 0; }
7-7 查找出现过的数字
#include #include using namespace std; int n, m, x; set s; int main() { cin >> m >> n; while (m --) { cin >> x; s.insert(x); } while (n --) { cin >> x; if (s.find(x) != s.end()) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
7-8 出现次数最多的数字和次数
#include #include using namespace std; mapmp; int n, x; int x_v, x_c; int main() { cin >> n; for (int i = 0; i < n; i ++) { cin >> x; mp[x] ++; } for (auto i : mp) { if (i.second > x_c) { x_v = i.first; x_c = i.second; } } cout << x_v << ' ' << x_c << endl; return 0; }
7-9 英雄出场王
#include #include using namespace std; const int N = 100000000; int n, x; int x_v, x_c = -1; map mp; int main() { cin >> n; for (int i = 0; i < n; i ++) { cin >> x; mp[x] ++; } for (auto i : mp) { if (i.second > x_c) { x_v = i.first; x_c = i.second; } } cout << x_v << endl << x_c << endl; return 0; }
7-10 求n个数中差的绝对值相差最小的2个数的差值
#include using namespace std; const int N = 1010; int n, x_v = 100000000; int arr[N]; int main() { cin >> n; for (int i = 0; i < n; i ++) { cin >> arr[i]; } for (int i = 0; i < n; i ++) { for (int j = i + 1; j < n; j ++) { if (abs(arr[i] - arr[j]) < x_v) { x_v = abs(arr[i] - arr[j]); } } } cout << x_v << endl; return 0; }
7-11 数列求和-加强版
#include using namespace std; int main() { int a, n; cin >> a >> n; int arr[1000010], cnt = 0, t = 0; if (!n) { cout << 0; return 0; } for (int i = 0; i < n; i ++) { arr[cnt ++] = (a * (n - i) + t )% 10; t = (a * (n - i) + t)/ 10; } if (t) arr[cnt ++] = t; for (int i = cnt - 1; i >= 0; i --) { cout << arr[i]; } return 0; }
7-12 数组循环右移（加强版）
#include using namespace std; int main() { int n, m, i, f = 0; cin >> n >> m; m %= n; int a[n]; for (i = 0; i < n; i ++) cin >> a[i]; for (i = n - m; i < n; i ++) { if (f ++) cout << ' '; cout << a[i]; } for (i = 0; i < n - m; i ++) { if (f ++) cout << ' '; cout << a[i]; } cout << endl; return 0; }
7-13 猴子选大王[加强版]
#include using namespace std; int main() { int n, k, s = 1; cin >> n >> k; for (int i = 1; i <= n; i ++ ) s = (s + k) % i; cout << s; return 0; }
7-14 最大公约数
#include #include using namespace std; int main() { int a, b, res = 0; cin >> a >> b; for (int i = 2; i < max(a, b); i ++) { if (a % i == 0 && b % i == 0) { res = i; } } res = __gcd(a, b); cout << res << endl; return 0; }
7-15 大菲波数
#include #include #include using namespace std; const int N = 1010; string f[N]; int t; vector add(vector &A, vector &B) { vector C; for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i++) { if (i < A.size()) t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { f[1] = f[2] = "1"; for (int i = 3; i < N; i ++) { string s1 = f[i - 1]; string s2 = f[i - 2]; vector A, B; for (int i = s1.size() - 1; i >= 0; i --) A.push_back((s1[i] - '0')); for (int i = s2.size() - 1; i >= 0; i --) B.push_back((s2[i] - '0')); auto C = add(A, B); string s; for (int i = C.size() - 1; i >= 0; i --) s += to_string(C[i]); f[i] = s; } cin >> t; while (t --) { int x; cin >> x; cout << f[x] << endl; } return 0; }
7-16 大数的乘法
#include #include using namespace std; typedef long long LL; vector mul(vector &A, int b) { vector C; for (LL i = 0, t = 0; i if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string s; int b; while(cin >> s >> b) { vector A; for (int i = s.size() - 1; i >= 0; i --) A.push_back(s[i] - '0'); auto C = mul(A, b); for (int i = C.size() - 1; i >= 0; i --) cout << C[i]; cout << endl; } return 0; }
7-17 大数和
#include #include using namespace std; vector add(vector &A, vector &B) { vector C; for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i ++) { if (i < A.size()) t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } while (C.back() == 0 && C.size() > 1) C.pop_back(); return C; } vector sub(vector &A, vector &B) { vector C; for (int i = 0, t = 0; i < A.size(); i ++) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.back() == 0 && C.size() > 1) C.pop_back(); return C; } bool cmp(vector &A, vector &B) { if (A.size() != B.size()) return A.size() > B.size(); for (int i = 0; i < A.size(); i ++) if (A[i] != B[i]) return A[i] > B[i]; return true; } int n; int main() { while (cin >> n, n) { int a1 = 1, ans1 = 1; vector ans = {0}; while (n --) { string a; vector A; cin >> a; if (a[0] == '-') { a1 = 0; for (int i = a.size() - 1; i > 0; i --) A.push_back(a[i] - '0'); } else { for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); a1 = 1; } if (cmp(ans, A)) { if (ans1 && a1) ans = add(ans, A), ans1 = 1; else if (ans1 && !a1) ans = sub(ans, A), ans1 = 1; else if (!ans1 && !a1) ans = add(ans, A), ans1 = 0; else ans = sub(ans, A), ans1 = 0; } else { if (ans1 && a1) ans = add(ans, A), ans1 = 1; else if (ans1 && !a1) ans = sub(A, ans), ans1 = 0; else if (!ans1 && !a1) ans = add(ans, A), ans1 = 0; else ans = sub(A, ans), ans1 = 1; } } if (!ans1 && ans[0]) cout << '-'; for (int i = ans.size() - 1; i >= 0; i --) cout << ans[i]; cout << endl; } return 0; }
7-18 求最大公约数
#include using namespace std; int f; int a, b; int gcd(int a, int b) { if (a % b == 0) return b; else { // if (f) cout << ' '; printf(" gcd(%d,%d)", b, a % b); return gcd(b, a % b); } } int main() { cin >> a >> b; printf("gcd(%d,%d)", a, b); int res = gcd(a, b); cout << ' ' << res; return 0; }
7-19 二分查找
#include using namespace std; const int N = 1010; int n, arr[N], x, cnt; int main() { cin >> n; for (int i = 0; i < n; i ++) cin >> arr[i]; cin >> x; int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) >> 1; if (arr[mid] > x) r = mid - 1,cnt ++; else if (arr[mid] < x) l = mid + 1, cnt ++; else { cnt ++; cout << mid << endl << cnt << endl; return 0; } } cout << -1 << endl << cnt << endl; return 0; }
7-20 全排列（分治）
#include using namespace std; const int N = 1010; int path[N], n; void dfs(int u) { if (u == n) { for (int i = 1; i <= n; i ++) cout << path[i] << ' '; cout < return ; } for (int i = u; i <= n; i ++) { swap(path[i], path[u]); dfs(u + 1); swap(path[u], path[i]); } } int main() { cin >> n; for (int i = 1; i <= n; i ++) path[i] = i; dfs(1); return 0; }
7-21 我是送分题
#include #include using namespace std; const int mod = 1e9 + 7; typedef long long LL; // 结论需要推 struct Mx { LL g[3][3]; Mx() { memset(g, 0, sizeof g); } }; // 矩阵乘法 3 重循环 Mx mul(Mx a, Mx b) { Mx res; for (int i = 0; i < 3; i ++) for (int j = 0; j < 3; j ++) { LL sum = 0; for (int k = 0; k < 3; k ++) sum = (sum + a.g[i][k] * b.g[k][j]) % mod; res.g[i][j] = sum; } return res; } // 矩阵快速幂 Mx Mx_pow(Mx a, LL b) { Mx res; // 构造单位矩阵 res.g[0][0] = res.g[1][1] = res.g[2][2] = 1; while (b) { if (b & 1) res = mul(res, a); // b & 1 判断 b 的末尾是否为 0 a = mul(a, a); b >>= 1; } return res; } LL n; Mx a; int main() { cin >> n; // 目标矩阵 a.g[0][0] = a.g[1][0] = a.g[2][1] = 1; a.g[0][1] = 2; a.g[0][2] = 3; a = Mx_pow(a, n - 3); LL ans[3][1], num[3][1]; num[0][0] = 3, num[1][0] = 2, num[2][0] = 1; for (int i = 0; i < 3; i ++) { LL sum = 0; for (int j = 0; j < 3; j ++) sum = (sum + a.g[i][j] * num[j][0]) % mod; ans[i][0] = sum; } cout << ans[0][0] << endl; return 0; }
7-22 二分查找
#include #include using namespace std; const int N = 1010; int n, x, t; int main() { scanf("%d%d", &n, &x); for (int i = 0; i < n; i ++) { cin >> t; if (t >= x) { cout << i + 1; return 0; } } cout << n + 1 << endl; return 0; }
7-23 程序设计综合实践 2.1
#include #include #include using namespace std; int main() { vectorans; int x; while (cin >> x) ans.push_back(x); sort(ans.begin(), ans.end()); cout << ans[0] << ',' << ans[ans.size() - 1]; return 0; }
7-24 找第k小的数
#include #include using namespace std; int main() { int n, m; cin >> n >> m; int a[n]; for (int i = 0; i < n; i ++) cin >> a[i]; sort(a, a + n); cout << a[m - 1] << endl; return 0; }
7-25 第 k 大的整数**
#include #include using namespace std; int main() { int n, m; cin >> n >> m; int a[n]; for (int i = 0; i < n; i ++) scanf("%d", &a[i]); sort(a, a + n); cout << a[n - m] << endl; return 0; }
7-26 0/1背包问题
#include using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N][N]; int maxv; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; for (int i = n; i >= 0; i --) { for (int j = 1; j <= m; j ++) { f[i][j] = f[i + 1][j]; if (j >= v[i]) { f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]); maxv = f[i][j]; } } } int j = m, t = 0; for (int i = 1; i <= n; i ++) if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) { cout << i << ' ', t = 1; j -= v[i]; } if (!t) cout << "No" << endl << 0 << endl; else cout << endl << maxv << endl; return 0; }
7-27 子集和问题
#include using namespace std; const int N = 1010; int n, m; int idx, sum; int w[N], op[N]; void dfs(int idx, int sum) { if (idx > n || sum > m) return ; else if (sum == m) { for (int i = 0; i < n; i ++) if (op[i]) cout << w[i] << ' '; cout << endl; return ; } else { op[idx] = 1; dfs(idx + 1, sum + w[idx]); op[idx] = 0; dfs(idx + 1, sum); } } int main() { cin >> n >> m; for (int i = 0; i < n; i ++) cin >> w[i]; dfs(0, 0); return 0; }
7-31 看电影
#include #include using namespace std; struct activity { int b, e, no; bool operator < (activity & t) { if (e != t.e) return e < t.e; else return b < t.b; } }a[1010]; int n, x ,y; // bool cmp (activity x, activity y) { // if (x.b != x.b) return x.b < y.b; // else return x.e < y.e; // } int main() { while (cin >> n, n != 0) { int cnt = 0, pre = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; } sort(a, a + n); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b >= pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; } } cout << cnt << endl; } return 0; }
7-28 幂集（回溯法）
#include using namespace std; const int N = 1010; int n, arr[N], cnt; int st[N]; void dfs(int a[], int n, int i, int st[]) { if (i >= n) cnt ++; else { st[i] = 1; dfs(a, n, i + 1, st); st[i] = 0; dfs(a, n, i + 1, st); } } int main() { cin >> n; for (int i = 0; i < n; i ++) cin >> arr[i]; dfs(arr, n, 0, st); cout << cnt << endl; return 0; }
7-31 看电影
#include #include using namespace std; struct activity { int b, e, no; bool operator < (activity & t) { if (e != t.e) return e < t.e; else return b < t.b; } }a[1010]; int n, x ,y; // bool cmp (activity x, activity y) { // if (x.b != x.b) return x.b < y.b; // else return x.e < y.e; // } int main() { while (cin >> n, n != 0) { int cnt = 0, pre = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; } sort(a, a + n); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b >= pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; } } cout << cnt << endl; } return 0; }
7-32 CPA招新Ⅰ
#include using namespace std; int main() { char e; int a = 0, b = 0, c = 0, d = 0; while ((e = getchar()) != '\n') { if (e == 'A') a ++; else if(e == 'B') b ++; else if (e == 'C') c ++; else if (e == 'D') d ++; } printf("Competition department %d people!\n", a); printf("Propaganda Department %d people!\n", b); printf("Office %d people!\n", c); printf("Organization Department %d people!\n", d); return 0; }
7-33 多参加活动，生活才精彩
#include #include using namespace std; struct activity { int b, e, no; // bool operator < (activity & t) { // if (e != t.e) return e < t.e; // } }a[1010]; int n, x ,y; bool cmp (activity x, activity y) { return x.e < y.e; // if (x.e != y.e) return x.e < y.e; // else return x.b < y.b; } int main() { cin >> n; int cnt = 0, pre = 0, score = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e >> a[i].no; // cout << a[i].b << ' ' << a[i].e << endl; } sort(a, a + n, cmp); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b >= pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; score += a[i].no; } } cout << cnt << ' ' << score << endl; return 0; }
7-34 装箱问题
#include using namespace std; const int N = 1010; int n, max_x = -1; int a[N], b[N]; int main() { cin >> n; for (int i = 1; i<= n; i ++) cin >> a[i], b[i] = 100; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { if (a[i] <= b[j]) { b[j] -= a[i]; cout << a[i] << ' ' << j << endl; max_x = max(max_x, j); break; } } } cout << max_x << endl; return 0; }
7-35 h0154.加勒比海盗船——最优装载问题
#include #include #include using namespace std; const int N = 1000005; int t; int main() { cin >> t; while (t --) { double c; vector a; int m, cnt = 0; cin >> c >> m; for (int i = 0; i < m; i ++) { double x; cin >> x; a.push_back(x); } sort(a.begin(), a.end()); double ans = 0; for (int i = 0; i < m; i ++) { ans += a[i]; if (ans <= c) cnt ++; else break; } cout << cnt << endl; } return 0; }
7-36 会场安排问题
#include #include using namespace std; struct activity { int b, e; // bool operator < (activity & t) { // if (e != t.e) return e < t.e; // } }a[10010]; int n; int st[10010]; bool cmp (activity x, activity y) { return x.b < y.b; // if (x.e != y.e) return x.e < y.e; // else return x.b < y.b; } int main() { cin >> n; int cnt = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; } sort(a, a + n, cmp); for (int i = 0; i < n; i ++) // cout << a[i].b << ' ' << a[i].e << endl; if (!st[a[i].e]) { cnt ++; st[a[i].e] = 1; int pre = a[i].e; for (int j = i + 1; j < n; j ++) if (!st[a[j].e] && a[j].b >= pre) { pre = a[j].e; st[a[j].e] = 1; } } cout << cnt << endl; return 0; }
7-37 h0145. 会议安排
#include #include using namespace std; struct activity { int b, e, no; bool operator < (activity & t) { if (e != t.e) return e < t.e; else return b < t.b; } }a[10010]; int n, x ,y; // bool cmp (activity x, activity y) { // if (x.b != x.b) return x.b < y.b; // else return x.e < y.e; // } int main() { int t; cin >> t; while (t --) { cin >> n; int cnt = 0, pre = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; } sort(a, a + n); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b >= pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; } } cout << cnt << endl; } return 0; }
7-38 最少失约
#include #include using namespace std; struct activity { int b, e, no; bool operator < (activity & t) { if (e != t.e) return e < t.e; else return b < t.b; } }a[10010]; int n, x ,y; // bool cmp (activity x, activity y) { // if (x.b != x.b) return x.b < y.b; // else return x.e < y.e; // } int main() { int t; cin >> t; while (t --) { cin >> n; int cnt = 0, pre = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; } sort(a, a + n); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b >= pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; } } cout << n - cnt << endl; } return 0; }
7-39 活动选择问题
#include #include using namespace std; struct activity { int b, e, no; bool operator < (activity & t) { if (e != t.e) return e < t.e; else return b < t.b; } }a[10010]; int n; // bool cmp (activity x, activity y) { // if (x.b != x.b) return x.b < y.b; // else return x.e < y.e; // } int main() { while (cin >> n) { int cnt = 0, pre = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; } sort(a, a + n); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b >= pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; } } cout << cnt << endl; } return 0; }
7-40 删数问题
// 贪心 #include using namespace std; int k; string str; int main() { cin >> str >> k; for (int i = 0; i < k; i ++) for (int j = 0; j < str.size(); j ++) if (str[j] > str[j + 1]) { str.erase(str.begin() + j); break; } cout << str << endl; return 0; }
7-41 最短路径条数
#include using namespace std; const int N = 1010; int g[N][N]; int main() { int n, m, x1, y1, x2, y2; cin >> n >> m >> x1 >> y1 >> x2 >> y2; if (x1 >= x2) swap(x1, x2); if (y1 >= y2) swap(y1, y2); for (int i = x1; i <= n; i ++) { for (int j = y1; j <= m; j ++) { if (x1 == i || y1 == i) g[i][j] = 1; else g[i][j] = g[i - 1][j] + g[i][j - 1]; } } cout << g[x2][y2] << endl; return 0; }
7-42 一步两步
#include using namespace std; const int N = 1010; int f[N], n; int main() { cin >> n; f[0] = 1; f[1] = 2; for (int i = 2; i < n; i ++) f[i] = f[i - 1] + f[i - 2]; cout << f[n - 1]; return 0; }
7-43 青蛙跳台阶
#include using namespace std; const int N = 1010; int f[N], n; int main() { cin >> n; f[0] = 1; f[1] = 2; for (int i = 2; i < 60; i ++) f[i] = f[i - 1] + f[i - 2]; while (n --) { int x; cin >> x; cout << f[x - 1] << endl; } return 0; }
7-45 让人头疼的“双十一”
#include #include using namespace std; const int N = 3010; int m ,n; int v[N], w[N]; int f[N]; int main() { int t; cin >> t; for (int k = 1; k <= t; k ++) { cin >> m >> n; for (int i = 1; i <= n; i ++) cin >> v[i]; for (int i = 1; i <= n; i ++) cin >> w[i]; for (int i = 1; i <= n; i ++) for (int j = m; j >= v[i]; j --) f[j] = max(f[j], f[j - v[i]] + w[i]); printf("Case #%d: %d\n", k, f[m]); memset(f, 0, sizeof f); } return 0; }
7-46 h0173. 01背包问题
#include using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N]; int main() { cin >> n >> m; for (int i = 0; i < n; i ++) cin >> v[i + 1] >> w[i + 1]; for (int i = 1; i <= n; i ++) for (int j = m; j >= v[i]; j --) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[m] << endl; return 0; }
7-47 最长公共子序列长度
#include using namespace std; const int N = 1010; string str1, str2; int f[N][N]; int main() { cin >> str1 >> str2; for (int i = 1; i <= str1.size(); i ++) { for (int j = 1; j <= str2.size(); j ++) { if (str1[i - 1] == str2[j - 1]) f[i][j] = f[i - 1][j - 1] + 1; else f[i][j] = max(f[i - 1][j], f[i][j - 1]); } } cout << f[str1.size()][str2.size()] << endl; return 0; }
7-48 h0215.闭区间问题
#include #include using namespace std; struct activity { int b, e, no; // bool operator < (activity & t) { // if (e != t.e) return e < t.e; // } }a[1010]; int n, x ,y; bool cmp (activity x, activity y) { return x.e < y.e; // if (x.e != y.e) return x.e < y.e; // else return x.b < y.b; } int main() { cin >> n; int cnt = 0, pre = 0; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; if (a[i].b > a[i].e) { int t = a[i].e; a[i].e = a[i].b; a[i].b = t; } } sort(a, a + n, cmp); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b > pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; } } cout << n - cnt; return 0; }
7-49 h0206. 区间选点
#include #include using namespace std; struct activity { int b, e, no; // bool operator < (activity & t) { // if (e != t.e) return e < t.e; // } }a[1010]; int n, x ,y; bool cmp (activity x, activity y) { return x.e < y.e; // if (x.e != y.e) return x.e < y.e; // else return x.b < y.b; } int main() { cin >> n; int cnt = 0, pre = -0x3f3f3f3f; for (int i = 0; i < n; i ++) { cin >> a[i].b >> a[i].e; // if (a[i].b > a[i].e) { // int t = a[i].e; // a[i].e = a[i].b; // a[i].b = t; // } } sort(a, a + n, cmp); for (int i = 0; i < n; i ++) { // cout << a[i].b << ' ' << a[i].e << endl; if (a[i].b > pre) { pre = a[i].e; // cout << a[i].b << ' ' << a[i].e << endl; cnt ++; } } cout << cnt; return 0; } Sdadaf #include #include #include using namespace std; const int MAX = 1010; int n; struct HTreeNode { char data; int weight; int parent; int lchild; int rchild; }; HTreeNode ht[MAX]; map mp; struct NodeType { int no; char data; int weight; bool operator < (const NodeType &s) { return s.weight < weight; } }; void init() { int i; map mp; for (int i = 0; i < n; i ++) mp[str[i]] ++; n = mp.size(); i = 0; for (auto it : mp) { ht[i].data = it.first; ht[i].weight = it.second; i ++; } for (int j = 0; j < 2 * n - 1; j ++) { ht[j].lchild = ht[j].rchild = ht[j].parent = -1; } } void createHTree() { NodeType e, e1, e2; priority_qeue qu; for (int i = 0; i < n; i ++) { e.no = i; e.data = ht[i].data; e.weight = ht[i].weight; qu.push(e); } for (int j = n; j < 2 * n - 1; j ++) { e1 = qu.top(); qu.pop(); e2 = qu.top(); qu.pop(); ht[j].weight = e1.weight + e2.weight; ht[j].lchild = e1.no; ht[j].rchild = e2.no; ht[e2.no].parent = j; ht[e2.no].parent = j; e.no = j; e.weight = e1.weight + e2.weight; qu.push(e); } } void CreateHCode() { string code; code reserve(MAX); } int main() { cin >> n; return 0; }
