共计 4449 个字符，预计需要花费 12 分钟才能阅读完成。
较量传送门：https://ac.nowcoder.com/acm/contest/53366
难度适中。
🎈 作者：Eriktse
🎈 简介：19 岁，211 计算机在读，现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换 C ++/Python 算法。（优质好文继续更新中……）🚀
🎈 浏览原文取得更好浏览体验：https://www.eriktse.com/algorithm/1109.html
A – 小 d 和答案批改
Tag：签到
略。
Code：
#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; ++ i)cin >> mp[i] + 1;
int sx, sy;
for(int i = 1;i <= n; ++ i)
for(int j = 1;j <= m; ++ j)if(mp[i][j] == '@')sx = i, sy = j;
int ans = dfs(sx, sy);
cout << ans << '\n';
return 0;
}D – 小 d 和孤单的区间
Tag：思维，dp，组合计数
给定一个长度为 0 的 01 串，问有多少个子串是仅蕴含一个 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 种。
Code:
#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; ++ i)cin >> a[i];
for(int i = 1;i <= n; ++ i)
{if(a[i] == 1)continue;
if(i > 1 && a[i - 1] == 0)l[i] = l[i - 1] + 1;
else l[i] = 1;
}
for(int i = n;i >= 1; -- i)
{if(a[i] == 1)continue;
if(i < n && a[i + 1] == 0)r[i] = r[i + 1] + 1;
else r[i] = 1;
}
int ans = 0;
for(int i = 1;i <= n; ++ i)
{if(a[i] == 1)ans += (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 中较大的那个，并且要尽可能大的切割。
Code:
#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 * n)break;
if(n > m)n = (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 状态：
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，就必须往下走了。
Code：
#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 == p)continue;
dfs(y, x);
if(s[y] == 0)continue;
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]); ++ i)dp[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 原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬
