2022.7.11全盘题解

题解"/>

2022.7.11全盘题解

序言

  又是靓仔无语的一天。
  Nothing to say.
  (投放 My blogs😃。)
  上题！（对题有疑问可以直接问）

---

2022.7.11

A. 性格公交车(bus.cpp)

你个 shy boy！（13 班老梗）

「我的做题历程」：

step1：观察题面。
  「内向的人总是选择两个座位都是空的一排。在这些空座位排当中，选择一排座位宽度最小的，并占了其中的一个座位」，可以得到大概率需要排序。
  「外向的人总是选择一个内向的人所占的那排座位。在这些座位排当中，选择一排座位宽度最大的，并在其中占据了空位」，进一步得出这道题需要同时模拟，而不能分别作决断。

step2：思考解法。
  我的想法：先将座位宽度从小到大排序，压入队列。若乘客为内向，选择当前最窄的座位（弹出队首）、输出，并把内向乘客选择过的座位压入栈（因为先进栈的一定比后进栈的宽度小，这样能保证栈顶一定是最宽的）；若乘客为外向，选择内向乘客选择过的座位中最宽的座位（弹出栈顶）、输出。

step3：完成代码：

代码（抵制学术不端行为，拒绝 Ctrl + C）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
int n, l, la, vis[M];
char ch;
struct node {int id, l;
} a[N];
bool cmp(node x, node y) { return x.l < y.l; }
stack<node> s;
queue<node> q;
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &l);a[++la].id = i;a[la].l = l;}sort(a + 1, a + la + 1, cmp);for (int i = 1; i <= la; i++) {q.push(a[i]);}scanf("\n");for (int i = 1; i <= n << 1; i++) {scanf("%c", &op); // 注意样例里面每个乘客的性格之间是没有空格的，因此 "%d" 输入是不可取的if (!(ch - '0')) {node t;t.id = q.front().id;t.l = q.front().l;printf("%d ", q.front().id);q.pop();s.push(t);} else {printf("%d ", s.top());s.pop();}}return 0;
}

从 shy boy \text{shy boy} shy boy 手中夺取 Accepted

---

B. 表达式求值

1 + 1 = ？

「我的做题历程」：

step1：观察题面。
  「给定一个只包含加法和乘法的算术表达式，请编程计算表达式的值」，没什么好说的，一个模拟。
  「当答案长度多于 4 位时，请只输出最后 4 位，前导 0 不输出。」，提醒我们，要取模。

step2：思考解法。
  这道题是中缀表达式，所以逆波兰式的求法肯定是行不通的。
  那么我们需要考虑计算的优先级——先乘，后加。加很容易，可以直接处理，问题在于乘。
  乘需要先算，即连乘的部分是一个整体。换个角度想，我们可以将乘法部分算出来后再当加减一样处理。
  连乘，可理解为是其他因数连续与第一个因数相乘的过程。为了保存前面的加数及保存第一个因数用于连乘，我们想到了栈——它后进先出的性质完美满足了我们只取出第一个因数而不干扰其他加数的需求。我们可以利用栈反复取出第一个因数与其他因数相乘的积，与当前因数相乘再放回去，而加数呢，直接塞进去即可。

step3：完成代码：

代码（抵制学术不端行为，拒绝 Ctrl + C）：

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int N = 1e5 + 5;
ll x, sum; 
char op;
stack<ll> s;
int main() {scanf("%lld", &x);s.push(x);while (~scanf("%c", &op)) {if (op == '\n') break;scanf("%lld", &x);if (op == '+') {s.push(x);} if (op == '*') {ll t = s.top();s.pop();s.push((t * x) % 10000);}}while (s.size()) {sum += s.top();sum %= 10000;s.pop();}printf("%lld", sum % 10000);return 0;
}

1 + 1 = Accepted （好耶）ヾ(≧▽≦*)o

---

C. 题海战

某信息学奥赛教练 gm 经验丰富

「我的做题历程」：

step1：观察题面。
  「对于每场比赛，他要保证所出的题没有任何一道已有任何一个学生做过；而对于每场训练，他要保证所出的所有题都被每一个参赛学生做过」，读到这里基本模拟定死。
  「可以重复做同一道题」「可能有学生重复报名」，都在疯狂暗示我们用 set。它可以去重，以及有方便的查找、修改和删除函数，使用它完成这道题再合适不过。

step2：思考解法。
  暴力模拟即可， 唯一的问题在于 set 的遍历。
   set 不比数组，不能使用 [] 来访问其中的元素。于是引进一个概念——迭代器（iterator），它可以遍历所用容器上的每一个接口，迭代器的值是该接口的地址，若要访问该接口的值，只需要引用一下就好。\

示例：

set<int>::iterator it = s.begin();  // 定义
for (it; it != s.end(); it++) // 遍历
// 由于迭代器返回的是地址，所以迭代器与迭代器之间是不能比较大小的，
// 但可以自增、自减、判断相等或不等。

step3：完成代码。

代码（抵制学术不端行为，拒绝 Ctrl + C）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2 + 5, M = 1e4 + 5;
int n, m, k, op, q, p, pro, pl[M];
set<int> stu[N], all, temp;
int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &p);for (int j = 1; j <= p; j++) {scanf("%d", &pro);stu[i].insert(pro);}}for (int i = 1; i <= m ; i++) {all.insert(i);}temp = all;scanf("%d", &k); for (int i = 1; i <= k; i++) {scanf("%d %d", &op, &q);for (int j = 1; j <= q; j++) {scanf("%d", pl + j);}if (op != 1) { // 比赛 for (int j = 1; j <= q; j++) {set<int>::iterator it = stu[pl[j]].begin();for (it; it != stu[pl[j]].end(); it++) {all.erase(*it);}}set<int>::iterator it1 = all.begin();for (it1; it1 != all.end(); it1++) {printf("%d ", *it1);}all = temp;} else { // 训练 bool can;for (int j = 1; j <= m; j++) {can = true;for (int k = 1; k <= q; k++) {if (stu[pl[k]].find(j) == stu[pl[k]].end()) {can = false;break;}}if (can) {printf("%d ", j);}}}puts("");}return 0;
}

某信息学奥赛教练拿出了珍藏已久的 Accepted

---

D. 四色地图（含 SPJ）

古德里：为何如此之晦

「我的做题历程」：

step1：观察题面。
  「四色定理」 ，数学问题？？
  「为了防止混乱，规定彼此搜索的区域互不相邻，请尝试如何分配」 ，哦， 知道了——用程序模拟四色填色。
  更值得注意的是，题目并没有说每块区域只有两块相邻的区域。也就是说，对于每行输入，数量是不确定的。如果用无限输入的话，是显然无法识别换行的；用字符的话过于麻烦。再引进一个工具——getline()。
  getline 用于接收一个字符串，且可以接收空格并输出，用法为 getline(cin,str)。

step2：思考解法。
  明显的，这个大小何不爆搜。

step3：完成代码。

代码（抵制学术不端行为，拒绝 Ctrl + C）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 26 + 5;
int n, id, color[N];
bool beside[N][N];
queue<int> q[N];
string x;
void dfs(int id) {if (id > n) {for (int i = 1; i <= n; i++) {printf("%d ", color[i]);}exit(0);}if (color[id] != 0) return ;bool NOT = false;for (int i = 1; i <= 4; i++) {color[id] = i;NOT = false;for (int j = 1; j <= n; j++) {if (beside[id][j] && color[id] == color[j]) {NOT = true;break;} }if (!NOT) {dfs(id + 1);}}return;
}
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &id);getline(cin, x);int len = x.length();for (int j = 0; j < len; j++) {if (x[j] >= '0' && x[j] <= '9') {int t = x[j] - '0';if (x[j + 1] >= '0' && x[j + 1] <= '9') {t = t * 10 + x[j + 1] - '0';}j++;if (t != i) {beside[i][t] = true;}}}} dfs(1);return 0;
}

（从地图里翻出 Accepted ）

---

E. 潜水员

（海底语言：咕噜咕噜咕噜）

  这道 dp 惨遭吐槽：「鬼知道最多能多带多少气体啊喂！！1」
   潜水员（危）。

「我的做题历程」：

step1：观察题面。
  「潜水员有一定数量的气缸，每个气缸都有重量和气体容量。……他所需气缸的总重量最少是多少？如果不能恰好带这么多气体，允许多带一些(先考虑氧气最小，再考虑氮气最小)」，很明显是一道二维费用背包。
  「如果无法凑齐，输出-1」，看来这个变种背包可能无解。若是总气体不小于所需气体，那绝对是可以是可以凑齐的。所以我们只需要判总的气体是否少于所需气体的量即可。
  针对上述解读，我们发现，二维费用背包我们都会，但如果能多带些气体的话，最多能多带多少呢？如果是气体总和的话——
，，，

  很明显行不通 （实在是太损了） ，转念一想 a i , b i ai,\ bi ai, bi 是 u , v u,\ v u, v 的十分之一，那么最多比目标气体多带一份 a i , b i ai,\ bi ai, bi 就一定可以凑够气体。我们可以直接写成目标气体的量加上气缸气体的最大值 100 100 100。最大值有了，这道题瞬间没了难度。

step2：思考解法。
  第一步思考 dp 状态：

d p i , j , k ( i ∈ [ 1 , n ] , j ∈ [ 1 , u + 100 ] , k ∈ [ 1 , v + 100 ] ) dp_{i, j, k}(i \in [1, n],\ j \in [1, u + 100],\ k \in [1, v + 100]) dpi,j,k​(i∈[1,n], j∈[1,u+100], k∈[1,v+100])
  表示前 i i i 个气缸里，凑出 j j j 数量的氧气和 k k k 数量的氮气所需带的气缸的最小重量。
  由于 i i i 本来就是从 1 1 1 到 n n n 循环，而且我们的关注点在氧气和氮气上，所以第一维可以抹掉。于是，dp 状态变成了——
d p i , j ( i ∈ [ 1 , u + 100 ] , j ∈ [ 1 , v + 100 ] ) dp_{i, j}(i \in [1, u + 100],\ j \in [1, v + 100]) dpi,j​(i∈[1,u+100], j∈[1,v+100])
  凑出 j j j 数量的氧气和 k k k 数量的氮气所需带的气缸的最小重量。

  第二步思考状态转移方程：
  对于每一个气缸，只有带或不带两种选择。所以状态转移方程是——
d p [ j ] [ k ] = m i n ( d p [ j ] [ k ] , d p [ j − a [ i ] . a i ] [ k − a [ i ] . b i ] + a [ i ] . c i ) ( i ∈ [ 1 , n ] , j ∈ [ 1 , u + 100 ] , k ∈ [ 1 , v + 100 ] ) dp[j][k] = min(dp[j][k], dp[j - a[i].ai][k - a[i].bi] + a[i].ci)\ (i \in [1, n],\ j \in [1, u + 100],\ k \in [1, v + 100]) dp[j][k]=min(dp[j][k],dp[j−a[i].ai][k−a[i].bi]+a[i].ci) (i∈[1,n], j∈[1,u+100], k∈[1,v+100])

step3：完成代码。\

代码（抵制学术不端行为，拒绝 Ctrl + C）：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int u, v, n, dp[N][N], sum_u, sum_v;
struct node {int ai, bi, ci;
} a[N];
int main() {scanf("%d %d %d", &u, &v, &n);for (int i = 1; i <= n; i++) {scanf("%d %d %d", &a[i].ai, &a[i].bi, &a[i].ci); sum_u += a[i].ai;sum_v += a[i].bi;}if (sum_u < u || sum_v < v) {printf("-1");return 0;}sum_u = min(sum_u, u << 1);sum_v = min(sum_v, v << 1);memset(dp, 0x3f, sizeof dp);dp[0][0] = 0;for (int i = 1; i <= n; i++) {for (int j = sum_u; j >= a[i].ai; j--) {for (int k = sum_v; k >= a[i].bi; k--) {dp[j][k] = min(dp[j][k], dp[j - a[i].ai][k - a[i].bi] + a[i].ci);}}}for (int i = u; i <= sum_u; i++) {for (int j = v; j <= sum_v; j++) {if (dp[i][j] != 0x3f3f3f3f) {printf("%d", dp[i][j]);return 0;}}}return 0;
}

咕噜咕噜咕噜……（ 翻译：我找到 Accepted 啦！！1）

---

还要更接下来几天的，未完待续