ABC 448 A - D 题解

ABC 448 A - D 题解

A：chmin

题意

给你一个长度为 \(N\) 的数组 \(A\)，与一个整数 \(X\)。对于 \(i = 1, 2, \cdots , N\)，执行以下操作：

• 若 \(A_i < X\)，则将 \(X\) 赋值为 \(A_i\)，并输出 1。
• 否则输出 0。

思路

遍历整个数组，按照思路进行操作即可。

代码部分

#include <bits/stdc++.h>
using namespace std;
int n, x;
int main()
{cin >> n >> x;for(int i = 1, a;i <= n;i ++){cin >> a;if(a < x)cout << 1 << endl, x = a;elsecout << 0 << endl;}return 0;
}

B：Pepper Addiction

题意

这个题意太乱了，我尽量按照它的原意说明白。

有 \(M\) 种胡椒粉末，第 \(i\) 种有 \(C_i\) 克。
又有 \(N\) 盘菜，第 \(i\) 盘菜只能加第 \(A_i\) 种胡椒粉末，并且最多加入 \(C_i\) 克。
求问我们总共最多能加入几克的胡椒粉末。

思路

这题很容易想到一点：就是不同的菜加胡椒粉末的效果是一样的，就是你不用管加了多少胡椒粉末，尽可能加满就可以了。
然后再看最后能用掉总共多少胡椒粉末就可以了。

代码部分

#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[1010], a[1010], b[1010];
long long ans = 0;
int main()
{cin >> n >> m;for(int i = 1;i <= m;i ++)cin >> c[i];for(int i = 1;i <= n;i ++){cin >> a[i] >> b[i];if(c[a[i]] >= b[i]){c[a[i]] -= b[i];ans += b[i];}elseans += c[a[i]], c[a[i]] = 0;}cout << ans << endl;return 0;
}

C：Except and Min

题意

一个袋子里有 \(N\) 个球，编号为 \(1\) 至 \(N\)。第 \(i\) 个球上写着数字 \(A_i\)。
我们需要处理 \(Q\) 项查询，每次查询给出一个长度为 \(K\) 的序列 \(B\)。然后，执行以下操作：

• 拿走编号为 \(B_1, B_2, \cdots , B_K\) 的球。
• 输出当前袋中最小的球的编号。
• 把拿走的球放回袋子里。

对于每次查询，输出结果。

思路

首先，我们可以发现：\(N\) 范围很大，无法暴力解决；但是 \(K\) 范围很小。
于是，我想到了一个思路：就是可以记录每个小球的编号与上面的数，并依据数的大小升序排列。
我们使 \(minn_i\) 为第 \(i\) 小的球的编号。
然后对于每次的查询，都遍历 \(minn\) 数组。一旦找到一个可使用的位置，就输出它代表的值，并退出循环。
由于 \(K\) 的范围非常小，所以并不会超时。

代码部分

#include <bits/stdc++.h>
using namespace std;
struct node
{int num, s;
}a[300010], minn[300010];
bool cmp(node a, node b)
{return a.num < b.num;
}
int n, Q, k;
int A[300010], b[10];
int main()
{cin >> n >> Q;for(int i = 1;i <= n;i ++){cin >> a[i].num;a[i].s = i;A[i] = a[i].num;}sort(a + 1, a + 1 + n, cmp);for(int i = 1;i <= n;i ++)minn[i] = a[i];while(Q --){cin >> k;for(int i = 1;i <= k;i ++)cin >> b[i];int ans = 0;for(int i = 1;i <= n;i ++){bool fg = 0;for(int j = 1;j <= k;j ++)if(minn[i].s == b[j]){fg = 1;break;}if(fg)continue;else{ans = minn[i].num;break;}		}cout << ans <<endl;}return 0;
}

D：Integer-duplicated Path

题意

一棵树有 \(N\) 个节点，\(N - 1\) 条边。第 \(i\) 个节点上写着数字 \(A_i\)。
我们希望知道，对于 \(k = 1, 2, \cdots , N\)，能否在一条从节点 \(1\) 到节点 \(k\) 的简单路径中出现两个相同的整数。

思路

这题是树论，我的解决思想有点像树形 DP 的思路。
首先，我们用 \(vis\) 数组记录节点是否到过。然后，用 \(sum\) 数组记录在路径中出现的整数的数量，如 \(sum_i\) 代表在这条路径中数字 \(i\) 的出现次数。
由于数字大小范围比较大，所以需要用 map 来实现。
然后，以节点 \(1\) 作为起点，一路向下遍历。遍历的过程中不断记录整数的出现次数。如果有一个整数的出现次数大于等于了两次，我们就需要记录这个节点是有答案的。但是直接查询时间复杂度太大了，我这里用了一个转化思想来实现。
对于节点 \(u\)，设其父节点为 \(fa\)。如果设 \(maxn_i\) 为从节点 \(1\) 到节点 \(i\) 的路径上出现的重复整数的最多数量，就可以发现，对于节点 \(u\)，有转移公式：

\[maxn_u = max(maxn_{fa}, sum_{A_u}) \]

然后，我们就可以通过这个来找寻答案了。
还有要注意的是，要在走到一条路径的末尾时，在回溯过程中把用过的数字删掉。
然后，这题就算完成了。

代码部分

#include <bits/stdc++.h>
using namespace std;
int n;
int a[200010], ans[200010], maxn[200010];
bool vis[200010];
vector<int> g[200010];
map<int, int> sum;
void dfs(int u, int fa)
{if(vis[u])return;vis[u] = 1;//标注已到达sum[a[u]] ++;//增加数字出现次数maxn[u] = max(maxn[fa], sum[a[u]]);//转移公式if(maxn[u] >= 2)//这个节点可以ans[u] = 1;for(int i = 0;i < g[u].size();i ++){int v = g[u][i];dfs(v, u);}sum[a[u]] --;//回溯
}
int main()
{cin >> n;for(int i = 1;i <= n;i ++)cin >> a[i];for(int i = 1, u, v;i < n;i ++){cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);for(int k = 1;k <= n;k ++){if(ans[k])cout << "Yes" << endl;elsecout << "No" <<endl;}return 0;
}