2022春 乙级

前言

乙级相对还是比较容易的，提前一个小时左右全部AC了；不过自身还是菜鸡，方法大概率离最优还有距离。
image.png
7-5时间.png

1 暴力破解 (15 分)

题目描述：

旅行箱上的密码锁通常都只有 3 位数字，如果忘了密码，只要有足够的耐心，哪怕用逐一枚举的办法，也可以暴力破解。如果还能隐约记得数字的范围，则可以大大降低破解的工作量。
本题就请你根据用户记忆中的数字范围，列出所有可能的密码。

输入格式：

输入第一行给出一个正整数 n（≤8），随后一行列出 n 个 0 - 9 范围内的数字，是用户记忆中可能属于密码的数字。题目保证 n 个数字没有重复，数字间以空格分隔。

输出格式：

按照密码组成的 3 位数从小到大的顺序，输出这 n 个数字能组成的所有可能的 3 位数密码。要求每行输出 10 个，同行数字以 1 个空格分隔，行首尾不得有多余空格。注意：如果有前导零，也不可忽略。

这是一个非常简单的模拟题，数字进行排序，然后枚举输出。（注意一下输出格式，10个换行，最后一个后没空格。）

AC代码

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int n;
  5. char a[8];
  6. int main()
  7. {
  8.     cin >> n;
  9.     for (int i = 0; i < n; i++)
  10.     {
  11.         cin >> a[i];
  12.     }
  13.     sort(a, a + n);
  14.     int num = 0;
  16.     for (int j = 0; j < n; j++)
  17.     {
  18.         for (int k = 0; k < n; k++)
  19.         {
  20.             for (int l = 0; l < n; l++)
  21.             {
  22.                 cout << a[j] << a[k] << a[l];
  23.                 num++;
  24.                 if (num % 10 == 0)
  25.                     cout << endl;
  26.                 else if (j < n - 1 || k < n - 1 || l < n - 1) //现在感觉可以直接j+k+l<3n-3
  27.                     cout << " ";
  28.             }
  29.         }
  30.     }
  32.     return 0;
  33. }

2 学霸 (20 分)

题目描述：

所谓“学霸”，就是每个学期选课学时最长的人。本题就给你所有课程的学时和选课名单，请你找出那个学霸。如果有总学时并列最多的情况，则选那个选课门数最多的。如果还有并列，就按学号升序输出他们吧~

输入格式：

输入在第一行中给出一个正整数：N（≤5000）为课程总数。随后 N 行，每行给出一门课的选课信息，格式如下：
学时 人数 选课人1 选课人2 ……
其中 学时 是该课程的学时，一个不超过 100 的正整数；人数 是该课程的选课人数，为不超过 200 的非负整数；选课人i 是第 i 个选课学生的编号，是一个 5 位数字。题目保证不同学生对应的编号不同，且同一门课程的选课名单中没有重复的学生。

输出格式：

首先在一行中输出学霸（们）的选课总学时和门数，随后在下一行中按照编号升序输出所有满足题面描述的学霸。编号间以 1 个空格分隔，行首尾不得有多余空格。题目保证至少存在一位学霸。

基本排序，对每个学生记录他的学号、课时、课程数（后两个需要累加），然后按题目条件写cmp函数，最后注意一下并列的情况进行输出。

AC代码

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int n;
  5. char a[8];
  6. int main()
  7. {
  8.     cin >> n;
  9.     for (int i = 0; i < n; i++)
  10.     {
  11.         cin >> a[i];
  12.     }
  13.     sort(a, a + n);
  14.     int num = 0;
  16.     for (int j = 0; j < n; j++)
  17.     {
  18.         for (int k = 0; k < n; k++)
  19.         {
  20.             for (int l = 0; l < n; l++)
  21.             {
  22.                 cout << a[j] << a[k] << a[l];
  23.                 num++;
  24.                 if (num % 10 == 0)
  25.                     cout << endl;
  26.                 else if (j < n - 1 || k < n - 1 || l < n - 1)
  27.                     cout << " ";
  28.             }
  29.         }
  30.     }
  32.     return 0;
  33. }

3 排课 (20 分)

题目描述：

排课是个世界难题。
假设每个学期有 N 个教学班的课需要排，每周有 M 个时间段可以上课，全校共有 K 间教室，不同排课组合方案的个数可能会超过整个宇宙的质子数。更为复杂的是，每个学期排课前，学校还会收集每个教学班任课老师不能上课的时间段，还要保证排课不与老师的时间安排起冲突。
当然，本题不是要求你实现一个排课算法，而是要求你实现一个排课方案检查算法。即给定每个教学班上课的时间和地点，你需要检查这个时间段和地点是否只有这一个班上课，并且这个上课时间不会正好是任课老师不能上课的时间。

输入格式：

输入在第一行中给出三个正整数：N（≤10^4）为教学班总数；M（≤40）为一周内上课时间段的个数；K（≤10^3）为教室总数。数字间以空格分隔。以下我们就将教学班、时间段、教室分别从 1 开始顺序编号。
随后 N 行，每行给出一个教学班的任课教师时间限制和排课的信息。格式如下：
L T[1] … T[L] Time Room
其中 L 是任课教师的时间限制数量（<_M_），后面给出 L 个该老师**不能**上课的时间段编号；Time 是该教学班安排的上课时间段编号，Room 是上课教室编号。我们假设每个教学班的任课老师都不一样。

输出格式：

如果给定的课表安排是完全无冲突的，则在一行内输出：Perfect Arrangement for N classes! 其中 N 是教学班数量。
如果课表有冲突，则需要输出冲突原因。我们首先假设教学班是按照编号递增序进行排课的，教学资源先到先得。如果后面安排的教学班 A 跟前面的教学班 B 排在了同一个时间和地点，则在一行中输出 ERROR: Conflict between A and B.，此时教学班 A 暂不安排。如果教学班 A 的上课时间跟任课教师有冲突，则在一行中输出 ERROR: Conflict with instructor for A.。当两种冲突都发生时，分两行输出，先输出教学班冲突的信息。

这题把题意理解了其实本质是个模拟，时间（m）和地点（k）完全一样的时候才算是两种课冲突，因为m≤40，可以用 100×时间+地点 来为唯一确定冲突与否。如果有冲突，最后要将数据清空（不排这课，后面的课程判断时间地点是否重复，就不和清空的课程比较了），于是开一个数组判断是否要清空。然后还需要把不能上课的时间段放到一个set里，因为无需排序，只用set的查找和去重，用unordered_set即可；时间在set里查找到即有上课时间冲突。最后，有上述错误flag取1，此时不输出无冲突的话，反之输出无冲突。

AC代码

  1. #include <iostream>
  2. #include <unordered_set>
  3. using namespace std;
  4. int n, m, k, cla[10001], flag = 0, error[10001];
  5. int main()
  6. {
  7.     cin >> n >> m >> k;
  8.     int l, temp, time, place;
  9.     unordered_set<int> tl;
  10.     for (int i = 1; i <= n; i++)
  11.     {
  12.         cin >> l;
  13.         for (int ii = 0; ii < l; ii++)
  14.         {
  15.             cin >> temp;
  16.             tl.insert(temp);
  17.         }
  18.         cin >> time >> place;
  19.         cla[i] = place * 100 + time;
  20.         for (int j = 1; j <= i - 1; j++)
  21.         {
  22.             if (cla[i] == cla[j])
  23.             {
  24.                 flag = 1;
  25.                 error[i]++;
  26.                 cout << "ERROR: Conflict between " << i << " and " << j << "." << endl;
  27.             }
  28.         }
  29.         if (tl.find(time) != tl.end())
  30.         {
  31.             flag = 1;
  32.             error[i]++;
  33.             cout << "ERROR: Conflict with instructor for " << i << "." << endl;
  34.         }
  35.         tl.clear();
  36.         if (error[i])
  37.             cla[i] = 0;
  38.     }
  39.     if (!flag)
  40.         cout << "Perfect Arrangement for " << n << " classes!";
  41.     /*
  42.     这里本来想的是，如果报错就加个判断1？class：classes
  43.     然而过了，就不改了。
  44.     */
  45.     return 0;
  46. }

4 简易测谎 (20 分)

题目描述：

测谎通常使用一套准备好的问题提问被测试者，通过分析被测试者的反应得到结果。比较高级的测谎技术会使用测谎仪，监视被测试者的生理活动状况。我们这里的简易测谎则是通过对问题答案的特征分析来做出判断。
首先我们要求被测试者做完 N 道单选题，每道题有 8 个选项，由小写英文字母 a - h 来表示。这样就得到一个长度为 N 的、由 a - h 小写英文字母组成的字符串。对每个字符串打分，得分超过某个给定阈值 T 的就判断为“疑似说谎者”。打分原则如下：

  • 以 f 开头的，得分 −2；
  • 以 a 结尾的，得分 −1；
  • 对于每一段长度大于 5 的连续选择同一字母的最长子串，得分 +3；
  • a 后面紧跟 e 或 h 的，得分 −4；
  • 对于每一段长度大于 3 的连续选择相邻递增字母的最长子串（例如 abcd 或 defgh），得分 +5。

本题就请你写程序完成对被测试者的判断。

输入格式：

输入第一行给出 3 个正整数：N（6≤N≤100）为测谎问卷的题目数；T （≤100）为判断说谎的得分阈值；K（≤100）为被测试者人数。
随后 K 行，每行给出一个被测试者的答案字符串。

输出格式：

对每个被测试者的答案，在一行中输出其得分。如果分数超过阈值，则在其分数后输出 !!!。

这是真真模拟，连续相同的判定是6个相同的+3即可（递增类似）。

AC代码

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. int a[101], n, t, k, grade;
  5. int main()
  6. {
  7.     string temp;
  8.     cin >> n >> t >> k;
  9.     for (int i = 0; i < k; i++)
  10.     {
  11.         grade = 0;
  12.         int aaa = 1, abcd = 1;
  13.         cin >> temp;
  14.         for (int j = 0; j < temp.length(); j++)
  15.         {
  16.             a[j] = temp[j] - 'a';    //当时都换成了数字，其实没必要。
  17.         }
  18.         if (a[0] == 5)
  19.             grade -= 2;
  20.         for (int j = 1; j < temp.length(); j++)
  21.         {
  22.             if ((a[j] == 4 || a[j] == 7) && a[j - 1] == 0)
  23.                 grade -= 4;
  24.             if (a[j] == a[j - 1])
  25.             {
  26.                 aaa++;
  27.             }
  28.             else
  29.                 aaa = 1;
  30.             if (a[j] - a[j - 1] == 1)
  31.                 abcd++;
  32.             else
  33.                 abcd = 1;
  34.             if (aaa == 6)
  35.                 grade += 3;
  36.             if (abcd == 4)
  37.                 grade += 5;
  38.         }
  39.         if (a[temp.length() - 1] == 0)
  40.             grade--;
  41.         cout << grade;
  42.         if (grade > t)
  43.             cout << "!!!";
  44.         cout << endl;
  45.     }
  46.     return 0;
  47. }

5 前K大数 (25 分)

题目描述：

本题目标非常简单：给定 N 个整数，找出前 K 个最大的数，并按递减序输出。

输入格式：

输入第一行给出 2 个正整数 N (≤10^6) 和 K (≤5)。随后一行给出 N 个整数键值，范围在区间 [−2^30,2^30] 内，以空格分隔。

输出格式：

按递减序在一行中输出前 K 个最大的数。
注意：一行中输出的数字间须以 1 个空格分隔，行首尾不得有多余空格。

这题的限制条件是：150 ms（时间）、2 MB（内存），能放2^19个int（题目整数范围是int），但N最大大约有2^20个。直接sort后面四个测试点过不了。
首先防止k比n大，需要k=min(k,n)。一开始用的办法是multiset放k个数，然后对剩下n-k个数，加一个数进set，再erase begin()，最后把k个数取出来倒置输出。
代码是这样的：

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4. using namespace std;
  5. int n, k, temp;
  6. multiset<int> seq;
  7. /*bool cmp(int a, int b)
  8. {
  9.     return a > b;
  10. }*/
  11. int main()
  12. {
  13.     cin >> n >> k;
  14.     k = min(n, k);
  15.     int ans[k];
  16.     for (int i = 0; i < k; i++)
  17.     {
  18.         cin >> temp;
  19.         seq.insert(temp);
  20.     }
  21.     //  sort(num, num + n, cmp);
  22.     for (int i = 0; i < n - k; i++)
  23.     {
  24.         cin >> temp;
  25.         seq.insert(temp);
  26.         seq.erase(seq.begin());
  27.     }
  28.     int cnt = 0;
  29.     for (multiset<int>::iterator it = seq.begin(); it != seq.end(); it++)
  30.     {
  31.         ans[cnt++] = (*it);
  32.     }
  33.     reverse(ans, ans + k);
  34.     for (int i = 0; i < k; i++)
  35.     {
  36.         if (i)
  37.             cout << " ";
  38.         cout << ans[i];
  39.     }
  40.     return 0;
  41. }

因为每次插入set里都是k个，k很小（5以内），复杂度大概认为是O(1)，n次插入就是O(n)，删除每次是O(1)。n次是O(n)。k个数reverse和遍历认为是O(1)。但是，超时。

后来的办法索性是用sort：开个vector放k个数然后排序（cmp从大到小），对后面n-k个数，先判断是不是比vertor最后一个大，不是的话直接跳过（set本质红黑树，不能随机访问），是的话push_back再排序，再把最小的pop_back。由于超了时用scanf不用cin（其实我怀疑是主要原因orz…）。复杂度方面k很小，排序还是认为O(1)，类似之前的分析总体O(n）（但不少数据直接跳过了）。

AC代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cstdio>
  5. using namespace std;
  6. int n, k, temp;
  7. vector<int> seq;
  8. bool cmp(int a, int b)
  9. {
  10.     return a > b;
  11. }
  12. int main()
  13. {
  14.     cin >> n >> k;
  15.     k = min(n, k);
  16.     for (int i = 0; i < k; i++)
  17.     {
  18.         scanf("%d", &temp);
  19.         seq.push_back(temp);
  20.     }
  21.     sort(seq.begin(), seq.end(), cmp);
  22.     for (int i = 0; i < n - k; i++)
  23.     {
  24.         scanf("%d", &temp);
  25.         if (temp <= seq[k - 1])
  26.             continue;
  27.         else
  28.         {
  29.             seq.push_back(temp);
  30.             sort(seq.begin(), seq.end(), cmp);
  31.             seq.pop_back();
  32.         }
  33.     }
  34.     /*int cnt = 0;
  35.     for (multiset<int>::iterator it = seq.begin(); it != seq.end(); it++)
  36.     {
  37.         ans[cnt++] = (*it);
  38.     }
  39.     reverse(ans, ans + k);*/
  40.     for (int i = 0; i < k; i++)
  41.     {
  42.         if (i)
  43.             cout << " ";
  44.         cout << seq[i];
  45.     }
  46.     return 0;
  47. }