比赛传送门： 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原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬 。

最后此篇关于【牛客小白月赛70】A-F题解【小d和超级泡泡堂】【小d和孤独的区间】【小d的博弈】【小d和送外卖】的文章就讲到这里了,如果你想了解更多关于【牛客小白月赛70】A-F题解【小d和超级泡泡堂】【小d和孤独的区间】【小d的博弈】【小d和送外卖】的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。