[关闭]
@Dmaxiya 2020-08-24T23:48:42.000000Z 字数 4822 阅读 890

第二次集中练习题解

Hello_World

题目链接：第二次集中练习

题意链接：第二次集中练习翻译

A. 暴力

题解

判断元音字母与奇数个数的和。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 100;
  22. char str[maxn];
  23. char ch[10] = {'a', 'e', 'i', 'o', 'u', '1', '3', '5', '7', '9'};
  25. int main() {
  26.     #ifdef LOCAL
  27.     freopen("test.txt", "r", stdin);
  28. //    freopen("out.txt", "w", stdout);
  29.     #endif // LOCAL
  30.     ios::sync_with_stdio(false);
  32.     while(scanf("%s", str) != EOF) {
  33.         int ans = 0;
  34.         for(int i = 0; str[i]; ++i) {
  35.             for(int j = 0; j < 10; ++j) {
  36.                 if(str[i] == ch[j]) {
  37.                     ++ans;
  38.                 }
  39.             }
  40.         }
  41.         printf("%d\n", ans);
  42.     }
  44.     return 0;
  45. }

B. 贪心

题解

对所有线段排序后，取相邻的三条线段，判断能否构成一个非退化三角形，用加法注意爆 int。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 100000 + 100;
  22. int n;
  23. int num[maxn];
  25. int main() {
  26.     #ifdef LOCAL
  27.     freopen("test.txt", "r", stdin);
  28. //    freopen("out.txt", "w", stdout);
  29.     #endif // LOCAL
  30.     ios::sync_with_stdio(false);
  32.     while(scanf("%d", &n) != EOF) {
  33.         for(int i = 0; i < n; ++i) {
  34.             scanf("%d", &num[i]);
  35.         }
  36.         sort(num, num + n);
  37.         bool flag = false;
  38.         for(int i = 2; i < n; ++i) {
  39.             if(num[i] - num[i - 1] < num[i - 2]) {
  40.                 flag = true;
  41.                 break;
  42.             }
  43.         }
  44.         if(flag) {
  45.             printf("YES\n");
  46.         } else {
  47.             printf("NO\n");
  48.         }
  49.     }
  51.     return 0;
  52. }

C. 并查集

题解

并查集，将并查集内节点数量记到根上。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 30000 + 100;
  22. int n, m, num;
  23. int x, y;
  24. int fa[maxn];
  25. int sum[maxn];
  27. int Find(int x) {
  28.     return (x == fa[x]? x: fa[x] = Find(fa[x]));
  29. }
  31. void unit(int x, int y) {
  32.     int xx = Find(x);
  33.     int yy = Find(y);
  34.     if(xx != yy) {
  35.         fa[xx] = yy;
  36.         sum[yy] += sum[xx];
  37.     }
  38. }
  40. void Init(int n) {
  41.     for(int i = 0; i < n; ++i) {
  42.         fa[i] = i;
  43.         sum[i] = 1;
  44.     }
  45. }
  47. int main() {
  48.     #ifdef LOCAL
  49.     freopen("test.txt", "r", stdin);
  50. //    freopen("out.txt", "w", stdout);
  51.     #endif // LOCAL
  52.     ios::sync_with_stdio(false);
  54.     while(scanf("%d%d", &n, &m), n != 0 || m != 0) {
  55.         Init(n);
  56.         for(int i = 0; i < m; ++i) {
  57.             scanf("%d", &num);
  58.             scanf("%d", &x);
  59.             for(int j = 1; j < num; ++j) {
  60.                 scanf("%d", &y);
  61.                 unit(x, y);
  62.                 x = y;
  63.             }
  64.         }
  65.         printf("%d\n", sum[Find(0)]);
  66.     }
  68.     return 0;
  69. }

D. dp

题解

将第一个序列的数字离散化为（映射到）对应的数字，对于没有出现的数字，映射到 ，然后对第二个序列的每个数字按照映射后的序列找最长递增子序列。对于已经 的同学，请再测试以下数据：
输入：
2
3 6 7
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9
3 1 4
1 9
1 2 7 8 9
输出：
Case 1: 4
Case 2: 2

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <queue>
  11. #include <stack>
  12. #include <map>
  13. #include <set>
  14. #include <bitset>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <iomanip>
  18. using namespace std;
  20. #define LL long long
  21. const int maxn = 300;
  22. int T, n, p, q, cnt;
  23. int *it;
  24. int f[maxn * maxn];
  25. int first[maxn * maxn], second[maxn * maxn];
  26. int num[maxn * maxn];
  28. int main() {
  29.     #ifdef LOCAL
  30.     freopen("test.txt", "r", stdin);
  31. //    freopen("out.txt", "w", stdout);
  32.     #endif // LOCAL
  33.     ios::sync_with_stdio(false);
  35.     scanf("%d", &T);
  36.     for(int cas = 1; cas <= T; ++cas) {
  37.         memset(f, 0, sizeof(f));
  38.         scanf("%d%d%d", &n, &p, &q);
  39.         for(int i = 1; i <= p + 1; ++i) {
  40.             scanf("%d", &first[i]);
  41.             f[first[i]] = i;
  42.         }
  43.         for(int i = 1; i <= q + 1; ++i) {
  44.             scanf("%d", &second[i]);
  45.             second[i] = f[second[i]];
  46.         }
  47.         cnt = 0;
  48.         for(int i = 1; i <= q + 1; ++i) {
  49.             if(second[i] != 0) {
  50.                 it = upper_bound(num, num + cnt, second[i]);
  51.                 if(it - num == cnt) {
  52.                     num[cnt++] = second[i];
  53.                 } else {
  54.                     *it = second[i];
  55.                 }
  56.             }
  57.         }
  58.         printf("Case %d: %d\n", cas, cnt);
  59.     }
  61.     return 0;
  62. }

E. 贪心 + set

题解

按照花费从大到小排序，花费大的先选择大于等于原起飞时间最小的时间，从 中删掉该时间，依次往下取。

过题代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <cstring>
  8. #include <string>
  9. #include <vector>
  10. #include <list>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include <set>
  15. #include <bitset>
  16. #include <algorithm>
  17. #include <ctime>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  22. #define LL long long
  24. const int maxn = 300000 + 100;
  25. int n, k;
  26. struct Node {
  27.     int cost;
  28.     int pos;
  29.     Node() {}
  30.     Node(int c, int p) {
  31.         cost = c;
  32.         pos = p;
  33.     }
  34. };
  35. bool operator<(const Node &a, const Node &b) {
  36.     return a.cost > b.cost;
  37. }
  38. vector<Node> vct;
  39. set<int> st;
  40. set<int>::iterator it;
  41. int cost[maxn];
  42. int ans[maxn];
  44. int main() {
  45.     #ifdef LOCAL
  46.     freopen("test.txt", "r", stdin);
  47. //    freopen("out.txt", "w", stdout);
  48.     #endif
  49.     ios::sync_with_stdio(false);
  51.     scanf("%d%d", &n, &k);
  52.     for(int i = 1; i <= n; ++i) {
  53.         scanf("%d", &cost[i]);
  54.         vct.push_back(Node(cost[i], i));
  55.     }
  56.     sort(vct.begin(), vct.end());
  57.     for(int i = 1; i <= n; ++i) {
  58.         st.insert(i + k);
  59.     }
  60.     for(int i = 0; i < n; ++i) {
  61.         it = st.upper_bound(vct[i].pos);
  62.         int abs1 = INT_MAX;
  63.         if(it != st.end()) {
  64.             abs1 = abs(*it - vct[i].pos);
  65.         }
  66.         int abs2 = INT_MAX;
  67.         if(it != st.begin()) {
  68.             --it;
  69.             abs2 = abs(*it - vct[i].pos);
  70.             ++it;
  71.         }
  72.         if(abs1 < abs2) {
  73.             ans[vct[i].pos] = *it;
  74.             st.erase(it);
  75.         } else {
  76.             --it;
  77.             ans[vct[i].pos] = *it;
  78.             st.erase(it);
  79.         }
  80.     }
  81.     LL sum = 0;
  82.     for(int i = 1; i <= n; ++i) {
  83.         sum += (LL)(abs(ans[i] - i)) * cost[i];
  84.     }
  85.     printf("%I64d\n", sum);
  86.     for(int i = 1; i <= n; ++i) {
  87.         if(i != 1) {
  88.             printf(" ");
  89.         }
  90.         printf("%d", ans[i]);
  91.     }
  93.     return 0;
  94. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注