$“葡萄城杯”牛客周赛Round53$

比赛地址： “葡萄城杯”牛客周赛 Round 53

D. 小红组比赛

题意

给出两个数字$n,m$，然后给出$n$组数，每组有$m$个数，最后给出一个数字$target$。题目要求从每组中选出一个数，要求最后选出的数字之和$target$相差最小，求最小相差多少？

数据范围

• $1\le n\le 100,1\le m\le 20$
• $1\le a_{i,j}\le 50$
• $1\le target\le 5000$

思路

读完题意可以很容易发现是一道分组背包问题的板子题，也是一道基础题，数据范围也符合。

但是这类问题可以使用位运算快速求解。

我们可以通过移位操作模拟加法操作，首先对于第一组数，我们都先将其通过或操作保存，我们可以使用$bitset$实现位运算操作。那么此时里面每个为‘1’的位的下标即为当前组里的数。

然后之后遍历每一组数的时候，只需重复上述操作。最后$bitset$中为**‘1’**的位的下标即为所有选择的可能结果。

然后我们根据$target$来遍历$bitset$中对应的位置，通过不断向两边查找，当查找到第一个‘1’时，那么当前位的下标与$target$的差值即为相差的最小值。

这样边实现了$O(nm)$时间复杂度的求解。

标程

#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10; int main() {int n, m; cin >> n >> m;bitset<N> b, t;b.set(0);for(int i = 1; i <= n; i ++ ) {t.reset();for(int j = 1; j <= m; j ++ ) {int x; cin >> x;t |= (b << x);}b = t;}int target; cin >> target;int res = target;for(int i = target, j = target; i >= 0 || j <= 100 * 50; i --, j ++ ) {if(i >= 0 && b[i] == 1) {res = target - i; break;}if(j < n * 50 && b[j] == 1) {res = j - target; break;}}cout << res << endl;return 0;
}

E. 折半丢弃

题意

给出一个长度为$n$的数组$a$，定义一次操作过程：选择其中任意一个元素$a_i$，然后将其改为$\left \lfloor \frac{a_i}{2} \right \rfloor $。

可以进行任意次操作，要求使得数组的$MEX$最大。

• 多实例$1\le T\le 10^4$
• $1\le n\le 10^5$
• $0\le a_i\le 10^6$

思路

我们可以从0开始枚举，判断数组中现存的数字是否可以构造出，当不能构造出时，那么就找出了最大的MEX。

在步骤”判断数组中现存的数字是否可以构造出”时，可以先对数组排序，然后从小开始判断。

因此先对数组进行排序，然后遍历整个原数组，并对原数组进行处理：我们对该数进行循环/2操作，直到其在数组中没有出现过。

然后我们从0开始枚举MEX，直到数组中的数字全部小于当前的MEX时结束，此时就得到了答案。

判断数字在数组中是否出现，可以用set容器。

标程

#include<bits/stdc++.h>using namespace std;#define ALL(x) x.begin(), x.end()void Solved() {int n; cin >> n;vector<int> v(n);set<int> st;for(auto &i : v) cin >> i;sort(ALL(v));int res = 0;for(auto i : v) {while(i && st.count(i)) i /= 2;st.insert(i);}while(st.count(res)) res ++;while(st.size() && *st.rbegin() > res) {int x = *st.rbegin();st.erase(x);x /= 2;while(x && st.count(x)) x /= 2;st.insert(x);while(st.count(res)) res ++;}cout << res << endl;
}signed main(void) {int ALL = 1; cin >> ALL;while(ALL -- ) Solved();return 0;
}

F.小红走矩阵

题意

给出一个$n\times m$的矩阵，起点和终点分别为$(1,1),(n,m)$，小红每次可以向上下左右移动。

由于矩阵中有障碍，因此小红可以在起点进行一次操作：选择一个障碍并替换为空地，然后选择失去向上下左右四个方向中的一个移动的能力。

求小红从起点到达终点的最小步数，如果无法到达则输出$-1$ 。

数据范围：

• $1\le n,m\le 1000$

思路

根据数据范围，我们可以使用bfs来搜，由于我们小红可以选择删去的方向只有五种情况：上、下、左、右、不删。

因此可以先枚举这五种情况，然后在搜索的过程中记录每个障碍物的删除情况。

实现过程中，我们可以使用$b[x][y][z]$来表示$(x,y)$位置，$z\in (0,1)$，若当前为障碍时，$z$有两种情况：删/不删。然后进行搜索即可。

标程

#include<bits/stdc++.h>using namespace std;const int INF = 0x7fffffff;
const int N = 1000 + 10; int n, m, res = INF;
bool a[N][N];
int nxt[5] = {-1, 0, 1, 0, -1};void bfs(int x, int y) {for(int i = -1; i < 4; i ++ ) {queue<tuple<int, int, bool>> q;q.push({x, y, false});vector b(n + 1, vector(m + 1, vector(2, -1)));b[x][y][0] = 0;while(!q.empty()) {auto [x1, y1, z] = q.front(); q.pop();for(int j = 0; j < 4; j ++ ) {if(j == i) continue;int x2 = x1 + nxt[j], y2 = y1 + nxt[j + 1];if(x2 < 1 || x2 > n || y2 < 1 || y2 > m) continue;bool z1 = z;if(a[x2][y2]) {if(z) continue;else z1 = true;}if(b[x2][y2][z1] != -1) continue;b[x2][y2][z1] = b[x1][y1][z] + 1;q.push({x2, y2, z1});}}if(b[n][m][0] != -1) res = min(res, b[n][m][0]);if(i != -1 && b[n][m][1] != -1) res = min(res, b[n][m][1]);}
}int main() {cin >> n >> m;for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= m; j ++ ) {char ch; cin >> ch;a[i][j] = (ch == '.' ? 0 : 1);}}bfs(1, 1);cout << (res == INF ? -1 : res) << endl;return 0;
}

G. 游游的删点直径

题意

给出一棵n个节点，n-1条边的树，然后用$f(i)$表示不经过i号节点的所有路径中，最长的路径长度。

题目要求输出$f(1)...f(n)$的全部值。

数据范围：

• $1\le n\le 10^5$
• 保证树联通，没有重边

思路

其实通过题目要求我们就能够发现，相邻两个节点的$f(i)$必然存在联系，如果之前做过类似题或者了解过的应该能很快想到。

然后我们来观察相邻两个节点之间的关系：

标程