目录
7-1 气球升起来... 1
7-2 集合A-B.. 2
7-3 排队... 3
7-4 办事大厅排队... 3
7-5 天梯赛的善良... 4
7-6 词典... 5
7-7 查找出现过的数字... 5
7-8 出现次数最多的数字和次数... 6
7-9 英雄出场王... 6
7-10 求n个数中差的绝对值相差最小的2个数的差值... 7
7-11 数列求和-加强版... 7
7-12 数组循环右移（加强版）... 8
7-13 猴子选大王[加强版] 8
7-14 最大公约数... 9
7-15 大菲波数... 9
7-16 大数的乘法... 10
7-17 大数和... 11
7-18 求最大公约数... 13
7-19 二分查找... 13
7-20 全排列（分治）... 14
7-21 我是送分题... 15
7-22 二分查找... 16
7-23 程序设计综合实践 2.1. 17
7-24 找第k小的数... 17
7-25 第 k 大的整数**. 17
7-26 0/1背包问题... 18
7-27 子集和问题... 19
7-28 幂集（回溯法）... 20
7-32 CPA招新Ⅰ... 22
7-33 多参加活动，生活才精彩... 22
7-34 装箱问题... 23
7-35 h0154.加勒比海盗船——最优装载问题... 24
7-36 会场安排问题... 24
7-37 h0145. 会议安排... 25
7-38 最少失约... 26
7-39 活动选择问题... 27
7-40 删数问题... 28
7-41 最短路径条数... 28
7-42 一步两步... 29
7-43 青蛙跳台阶... 29
7-45 让人头疼的“双十一”... 30
7-46 h0173. 01背包问题... 30
7-47 最长公共子序列长度... 31
7-48 h0215.闭区间问题... 31
7-49 h0206. 区间选点... 32
7-1 气球升起来
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1010;
int n;
string str;
map<string, int> 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 <iostream>
#include <set>
#include <algorithm>
using namespace std;
int t, n, m;
set<int> 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<int> 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 <iostream>
#include <algorithm>
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 <iostream>
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;
}
7-5 天梯赛的善良
#include <iostream>
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;
}
7-6 词典
#include <iostream>
#include <map>
using namespace std;
const int N = 1010;
int n, m;
string str1, str2;
map<string, string>mp;
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 <iostream>
#include <set>
using namespace std;
int n, m, x;
set<int> 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 <iostream>
#include <map>
using namespace std;
map<int, int>mp;
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 <iostream>
#include <map>
using namespace std;
const int N = 100000000;
int n, x;
int x_v, x_c = -1;
map<int, int> 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 <iostream>
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 <iostream>
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 <iostream>
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 <bits/stdc++.h>
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 <iostream>
#include <algorithm>
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 <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010;
string f[N];
int t;
vector<int> add(vector<int> &A, vector<int> &B) {
vector<int> 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<int> 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 <iostream>
#include <vector>
using namespace std;
typedef long long LL;
vector<LL> mul(vector<LL> &A, int b) {
vector<LL> C;
for (LL i = 0, t = 0; i <A.size() || t; 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<LL> 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 <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B) {
vector<int> 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<int> sub(vector<int> &A, vector<int> &B) {
vector<int> 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<int> &A, vector<int> &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<int> ans = {0};
while (n --) {
string a;
vector<int> 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 <iostream>
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 <iostream>
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 <iostream>
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 <<endl;
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 <iostream>
#include <cstring>
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 <iostream>
#include <cstring>
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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int>ans;
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 <iostream>
#include <algorithm>
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 <iostream>
#include <algorithm>
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 <iostream>
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 <iostream>
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 <iostream>
#include <algorithm>
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 <iostream>
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 <iostream>
#include <algorithm>
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 <iostream>
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 <iostream>
#include <algorithm>
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 <iostream>
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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1000005;
int t;
int main() {
cin >> t;
while (t --) {
double c;
vector<double> 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 <iostream>
#include <algorithm>
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 <iostream>
#include <algorithm>
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 <iostream>
#include <algorithm>
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 <iostream>
#include <algorithm>
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 <iostream>
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 <iostream>
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 <iostream>
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 <iostream>
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 <iostream>
#include <cstring>
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 <iostream>
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 <iostream>
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 <iostream>
#include <algorithm>
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 <iostream>
#include <algorithm>
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 <iostream>
#include <map>
#include <queue>
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<char, string> mp;
struct NodeType {
int no;
char data;
int weight;
bool operator < (const NodeType &s) {
return s.weight < weight;
}
};
void init() {
int i;
map<char, int> 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<NodeType> 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;
}
