![[牛客小白月赛70]A-F题解[小d和超级泡泡堂][小d和孤独的区间][小d的博弈][小d和送外卖]](/static/background/58.jpg "[牛客小白月赛70]A-F题解[小d和超级泡泡堂][小d和孤独的区间][小d的博弈][小d和送外卖]")
难度适中。
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 阅读原文获得更好阅读体验：https://www.eriktse.com/algorithm/1109.html
A - 小d和答案修改
略。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
char s[N];
signed main(
{
cin >> s + 1;
for(int i = 1; s[i]; ++ i
{
if('a' <= s[i] && s[i] <= 'z'printf("%c", s[i] - 'a' + 'A';
else printf("%c", s[i] - 'A' + 'a';
}
return 0;
}
B - 小d和图片压缩
Tag：签到
Code：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 9;
int a[N][N];
signed main(
{
ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
int n, m;cin >> n >> m;
for(int i = 1;i <= n; ++ i
for(int j = 1;j <= m; ++ j
cin >> a[i][j];
for(int i = 1;i <= n; i += 2
{
for(int j = 1;j <= m;j += 2
{
int sum = a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1];
cout << sum / 4 << ' ';
}
cout << '\n';
}
return 0;
}
C - 小d和超级泡泡堂
Tag：dfs，联通块
n x m的地图，求起点@所在的联通块的大小。
dfs扫一遍即可，复杂度O(nm，当然你想用bfs也行。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 9;
char mp[N][N];
bitset<N> vis[N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m;
int dfs(int x, int y
{
int res = mp[x][y] == '!';
for(int i = 0;i < 4; ++ i
{
int nx = x + dx[i], ny = y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] || mp[nx][ny] == '#'continue;
vis[nx][ny] = true;
res += dfs(nx, ny;
}
return res;
}
signed main(
{
ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
cin >> n >> m;
for(int i = 1;i <= n; ++ icin >> mp[i] + 1;
int sx, sy;
for(int i = 1;i <= n; ++ i
for(int j = 1;j <= m; ++ jif(mp[i][j] == '@'sx = i, sy = j;
int ans = dfs(sx, sy;
cout << ans << '\n';
return 0;
}
D - 小d和孤独的区间
Tag：思维，dp，组合计数
1的。
l[i]表示从i点开始，往左有多少个连续的0，r[i]表示从i点开始，往右有多少连续的0。
a[i] == 1，说明这个点i可以被一些区间包含到且仅有这一个1，那么是哪些区间呢？我们假设这个区间为[s, e]，那么一定有s <= i && i <= e，且[s, i - 1]中只包含0，[i + 1, e]中只包含0。
s的取值有l[i - 1] + 1种，右端点e的取值有r[i + 1] + 1种。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9;
int a[N], l[N], r[N];
signed main(
{
ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
int n;cin >> n;
for(int i = 1;i <= n; ++ icin >> a[i];
for(int i = 1;i <= n; ++ i
{
if(a[i] == 1continue;
if(i > 1 && a[i - 1] == 0l[i] = l[i - 1] + 1;
else l[i] = 1;
}
for(int i = n;i >= 1; -- i
{
if(a[i] == 1continue;
if(i < n && a[i + 1] == 0r[i] = r[i + 1] + 1;
else r[i] = 1;
}
int ans = 0;
for(int i = 1;i <= n; ++ i
{
if(a[i] == 1ans += (l[i - 1] + 1 * (r[i + 1] + 1;
}
cout << ans << '\n';
return 0;
}
E - 小d的博弈
Tag：博弈，思维
n x m的矩形，Alice和Bob轮流对其进行操作，每次操作可以横着或竖着在把矩形切一刀分成两个长宽都为整数的矩形，然后留下面积较小的那个，两个矩形面积相等是不被允许的，也就是说不能从中间切。
我们分析一下容易发现几种必败的局面，(1, 1, (1, 2, (2, 1, (2, 2无法操作，直接败。
n=m的情况，我们可以发现n=m的时候也是必败的，因为下一个人一定可以模仿当前操作者的操作，从而每次都使得回到自己手上的都是一个正方形，那么最终必然会到(1, 1或(2, 2的必败局面。
n=m的局面，此时我们就是必胜的。
W必胜态: 当n > 2m || m > 2n时，我们可以通过切分使得对手得到一个正方形，所以此时是必胜的。
不能把小的再切小，因为每次切割必然使得n或m比原来的一半还小，就会使得对手进入W的必胜态。所以我一定是切割n, m中较大的那个，并且要尽可能大的切割。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9;
void solve(
{
int n, m;cin >> n >> m;
int ans = 1;
while(1
{
if(n > 2 * m || m > 2 * nbreak;
if(n > mn = (n - 1 / 2;
else m = (m - 1 / 2;
ans ^= 1;
}
cout << (ans ? "Alice" : "Bob" << '\n';
}
signed main(
{
ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
int _;cin >> _;
while(_ --solve(;
return 0;
}
F - 小d和送外卖
Tag：树形dp，背包，图论
need。
dp[x][i]表示在以节点x为根的子树上删除i个点后可以减少的最大路程。s[x]表示在以节点
x为根的子树中的需求量（标记为need的点的个数）。在转移刚开始的时候，
dp[x]是不完整的，它仅包含x这一个点的信息，设x的儿子分别为y1,y2,y3，在将y1转移给x之后，dp[x]表示的范围就是x点和y1子树，以此类推，将y2, y3一个个合并，最后dp[x]表示的信息就是以x为根的子树的信息。dp[x][k]，我们可以将
k分解成i + (k - i，然后有dp[x][k] = max(dp[x][i], dp[y][k - i]。dp[x]需要用到
dp[x]本身的信息，所以我们需要开一个临时的数组f[]来表示dp[x]更新完再将f[]复制给dp[x]。s[y] == 0，说明y子树对答案完全没有影响，可以直接跳过。
k - i == s[y]，说明我们把
y子树的所有需求点都删了，那么x -> y这条边可以删除，所以对答案贡献为2（表示最终路程可以减少2），其余情况贡献都为0。dp[x]后还要更新一下
s[x]，直接加上s[y]即可。tot，当
s[y]不为0，就必须往下走了。#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 9; int dp[N][60], s[N];//dp[i][j]表示在i为根的子树中删除j个点的最大贡献 //s[i]表示以i为根的子树中的需求量 vector<int> g[N]; bitset<N> need; int tot, n, m;; void dfs(int x, int p { s[x] = need[x]; for(auto &y : g[x] { if(y == pcontinue; dfs(y, x; if(s[y] == 0continue; static int f[60]; memset(f, 0, sizeof f; for(int k = 0;k <= min(m, s[x] + s[y]; ++ k { //x树中取i个，注意此时x树并不完整 //在y中取k - i个，此时y树为完整的 for(int i = 0;i <= min(m, s[x]; ++ i { if(k - i <= s[y] && k - i >= 0 f[k] = max(f[k], dp[x][i] + dp[y][k - i] + (k - i == s[y] ? 2 : 0; } } s[x] += s[y]; tot += 2;//此时已经保证s[y] != 0，注意看上面的continue for(int i = 0;i <= min(m, s[x] + s[y]; ++ idp[x][i] = f[i]; } } signed main( { ios::sync_with_stdio(0, cin.tie(0, cout.tie(0; cin >> n >> m; for(int i = 1;i < n; ++ i { int x, y;cin >> x >> y; g[x].push_back(y, g[y].push_back(x; } int k;cin >> k; for(int i = 1;i <= k; ++ i { int x;cin >> x; need[x] = true; } dfs(1, -1; cout << tot - dp[1][m] << '\n'; return 0; }🎈 本文由eriktse原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬