L2-2 口罩发放 (25分)
1.题意
某市出于给市民发放口罩的需要，推出了一款小程序让市民填写信息，方便工作的开展。小程序收集了各种信息，包括市民的姓名、身份证、身体情况、提交时间等，但因为数据量太大，需要根据一定规则进行筛选和处理，请你编写程序，按照给定规则输出口罩的寄送名单。输入格式:输入第一行是两个正整数 D 和 P，表示有 D 天的数据，市民两次获得口罩的时间至少需要间隔 P 天。接下来 D 块数据，每块给出一天的申请信息。第 i 块数据的第一行是两个整数Ti，Si，表示在第 i 天有Ti条申请，总共有Si个口罩发放名额。随后Ti行，每行给出一条申请信息，格式如下：
姓名 身份证号 身体情况 提交时间
给定数据约束如下：
姓名 是一个长度不超过 10 的不包含空格的非空字符串；
身份证号 是一个长度不超过 20 的非空字符串；
身体情况 是 0 或者 1，0 表示自觉良好，1 表示有相关症状；
提交时间 是 hh:mm，为24小时时间（由 00:00 到 23:59。例如 09:08。）。注意，给定的记录的提交时间不一定有序；
身份证号 各不相同，同一个身份证号被认为是同一个人，数据保证同一个身份证号姓名是相同的。
能发放口罩的记录要求如下：
身份证号 必须是 18 位的数字（可以包含前导0）；
同一个身份证号若在第 i 天申请成功，则接下来的 P 天不能再次申请。也就是说，若第 i 天申请成功，则等到第 i+P+1 天才能再次申请；
在上面两条都符合的情况下，按照提交时间的先后顺序发放，直至全部记录处理完毕或 Si个名额用完。如果提交时间相同，则按照在列表中出现的先后顺序决定。
输出格式:
对于每一天的申请记录，每行输出一位得到口罩的人的姓名及身份证号，用一个空格隔开。顺序按照发放顺序确定。在输出完发放记录后，你还需要输出有合法记录的、身体状况为 1 的申请人的姓名及身份证号，用空格隔开。顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。
2.题解
用结构体存市民的信息，一个全局vector存有症状的市民，一个局部vector存每一天的市民信息，根据题意筛选排序后发放口罩，并记录有症状的市民。
3.代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long; 4 const int maxn = 1000 + 5; 5 const int INF = 0x7FFFFFFF; 6 struct mmp { 7 string name; 8 string idcard; 9 int shen; 10 int times; 11 int index; 12 }; 13 map<string, int> mp; 14 set<string> smp; 15 set<string> vHave; 16 vector<mmp> v; 17 bool cmp(mmp a, mmp b) { 18 if(a.times == b.times) { 19 return a.index < b.index; 20 } 21 return a.times < b.times; 22 } 23 int main() { 24 int D, P; 25 scanf("%d %d", &D, &P); 26 for(int day = 1; day <= D; day++) { 27 int ti, si; 28 cin >> ti >> si; 29 vector<mmp> use; 30 for(int i = 1; i <= ti; i++) { 31 string name; 32 string idcard; 33 int shen; 34 int hh; 35 int mm; 36 cin >> name; 37 cin >> idcard; 38 cin >> shen; 39 scanf("%d:%d", &hh, &mm); 40 bool flag = true; 41 if(idcard.length() != 18) { 42 continue; 43 } 44 for(int j = 0; j < idcard.size(); j++) { 45 if (!(idcard[j] >= '0' && idcard[j] <= '9')) { 46 flag = false; 47 } 48 } 49 if(flag) { 50 if(shen && vHave.find(idcard) == vHave.end()) { 51 v.push_back(mmp{name, idcard, shen, hh * 60 + mm, i}); 52 vHave.insert(idcard); 53 } 54 use.push_back(mmp{name, idcard, shen, hh * 60 + mm, i}); 55 } 56 } 57 sort(use.begin(), use.end(), cmp); 58 int now = 0; 59 for(int i = 0; i < use.size() && now < si; i++) { 60 if(mp[use[i].idcard] == 0 || day >= P + mp[use[i].idcard] + 1) { 61 now++; 62 mp[use[i].idcard] = day; 63 cout << use[i].name << " " << use[i].idcard << endl; 64 } 65 } 66 } 67 for(int i = 0; i < v.size(); i++) { 68 cout << v[i].name << " " << v[i].idcard << endl; 69 } 70 71 return 0; 72 }
L2-3 完全二叉树的层序遍历 (25分)
1.题意
给出一棵完全二叉树的后序遍历，输出对应层序遍历。
2.题解
因为是后序遍历序列，所以最后一个元素是树的根节点，可以使用递归建树。若当前结点的右子树不为空则继续将右子树遍历，若右子树为空则判断当前结点是否存在右儿子，右儿子的编号为 this.num*2+1，如果右儿子的编号小于等于结点的数量n则表示存在右儿子，在此新建结点；若右子树不满足条件则考虑左子树，同样是假如当前结点的左子树不为空则继续向左子树遍历，否则判断当前结点是否存在左儿子，左儿子的编号为 this.num*2，如果左儿子的编号小于等于结点的数量n则表示存在左儿子，在此新建结点。最后使用队列实现层序遍历。
3.代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n; 4 int a[35]; 5 struct node { 6 int value; 7 int level; 8 node* l; 9 node* r; 10 node(int value) { 11 this->value = value; 12 this->l = NULL; 13 this->r = NULL; 14 this->level = 1; 15 } 16 }; 17 bool flag; 18 void build(node* root, int a, int num) { 19 if(flag) { 20 return ; 21 } 22 if(root->r) { 23 build(root->r, a, num * 2 + 1); 24 } else if(num * 2 + 1 <= n) { 25 flag = true; 26 root->r = new node(a); 27 return; 28 } 29 if(flag) { 30 return ; 31 } 32 if(root->l) { 33 build(root->l, a, num * 2); 34 } else if(num * 2 <= n) { 35 flag = true; 36 root->l = new node(a); 37 return; 38 } 39 } 40 int res[50]; 41 int cnt=0; 42 void levelOrder(node* root) { 43 queue<node*> q; 44 node* now = root; 45 q.push(now); 46 while(q.size()) { 47 now = q.front(); 48 res[cnt++] = now->value; 49 q.pop(); 50 if(now->l) { 51 q.push(now->l); 52 } 53 if(now->r) { 54 q.push(now->r); 55 } 56 } 57 } 58 int main() { 59 cin >> n; 60 for(int i = 1; i <= n; i++) { 61 cin >> a[i]; 62 } 63 reverse(a + 1, a + n + 1); 64 node* root = new node(a[1]); 65 for(int i = 2; i <= n; i++) { 66 flag = false; 67 build(root, a[i], 1); 68 } 69 levelOrder(root); 70 for(int i = 0; i < cnt; i++) { 71 cout << res[i] << (i == n - 1?' ':' '); 72 } 73 74 return 0; 75 }
L2-4 网红点打卡攻略 (25分)
1.题意
大家来网红点游玩，俗称“打卡”。在各个网红点打卡的方法称为“攻略”。你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。
输入格式：
首先第一行给出两个正整数：网红点的个数 N和网红点之间通路的条数 M。随后 M 行，每行给出有通路的两个网红点、以及这条路上的旅行花费（为正整数），格式为“网红点1 网红点2 费用”，其中网红点从 1 到 N 编号；同时也给出你家到某些网红点的花费，格式相同，其中你家的编号固定为 0。再下一行给出一个正整数 K，是待检验的攻略的数量。随后 K 行，每行给出一条待检攻略，格式为：n V1 V2 ⋯ Vn，其中 n是攻略中的网红点数，Vi是路径上的网红点编号。这里假设你从家里出发，从V1开始打卡，最后从Vn回家。
输出格式：
在第一行输出满足要求的攻略的个数。
在第二行中，首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号（从 1 开始），然后输出这个攻略的总路费，其间以一个空格分隔。如果这样的攻略不唯一，则输出序号最小的那个。
2.题解
用一个二维数组存无向图的信息，bool数组判断是否去了每一个地点一次，更新最低花费。
3.代码
1 #include<bits/stdc++.h> 2 #define N 205 3 using namespace std; 4 int n, m, k, nk; 5 int g[N][N]; 6 int V[N]; 7 bool vis[N]; 8 int cnt, ans_i, ans_w = 0x3f3f3f3f; 9 int main() { 10 memset(g, -1, sizeof(g)); 11 cin >> n >> m; 12 for(int i = 0; i < m; i++) { 13 int u, v, w; 14 cin >> u >> v >> w; 15 g[u][v] = w; 16 g[v][u] = w; 17 } 18 cin >> k; 19 for(int i = 1; i <= k; i++) { 20 memset(vis, false, sizeof(vis)); 21 cin >> nk; 22 bool flag = true; 23 for(int j = 1; j <= nk; j++) { 24 cin >> V[j]; 25 vis[V[j]] = true; 26 } 27 V[0] = V[nk+1] = 0; 28 if(nk != n) { 29 continue; 30 } 31 for(int j = 1; j <= nk; j++) { 32 if(!vis[j]) { 33 flag = false; 34 break; 35 } 36 } 37 if(!flag) { 38 continue; 39 } 40 int sumw = 0; 41 for(int j = 0; j <= nk; j++) { 42 if(g[V[j]][V[j+1]] > 0) { 43 sumw += g[V[j]][V[j+1]]; 44 } else { 45 flag = false; 46 break; 47 } 48 } 49 if(!flag) { 50 continue; 51 } 52 cnt++; 53 if(ans_w > sumw) { 54 ans_w = sumw; 55 ans_i = i; 56 } 57 } 58 cout << cnt << endl; 59 cout << ans_i << " " << ans_w << endl; 60 61 return 0; 62 }