牛客算法周周练13

A.最小生成树
可以用最小生成树写，不过稍微想一下就可以想到，从小到大排序后a[1]和其他个点连接就是最小生成树。
C.Shopping
可以半价的物品的个数为 $max(m,板凳数)$ ，排序之后max个物品半价，其余原价即是答案。
B.病毒感染
 B.病毒感染

题意：给出一颗所有路径都为1的树，让你找出到其余点距离和最小的点，若存在多个，都输出。

暴力法：跑n边迪杰斯特拉，n>=5e5，显然不行。

试着画图模拟找思路：

在这里插入图片描述

上图中，1到其余各点的距离和为7（1+1+1+1+1+2），2到其余各点的距离和为10（1+1+2+2+2+2），因为题目保证了各路径长度都为1，显然，从1到2的过程中，增加的路径是1、3、4、5、6五个点贡献的，减少的路径则是2、7两个点贡献的。也就是ans[2]=ans[1]+5-2。其中的5和2，就是结点2“左边”的结点数量和“右边”的节点数量。

这样一来，这个问题就分成了下面几个步骤：

计算出每个结点“左边”的结点数量和“右边”的节点数量。

我们用dfs递归到根结点，然后回溯累加即可。

计算出某个结点x的答案。

使用bfs计算x到其余结点的距离，累加。

通过结点x来递推其余结点。

使用bfs转移。

AC代码：

/*
 * @Author: hesorchen
 * @Date: 2020-04-14 10:33:26
 * @LastEditTime: 2020-07-01 15:49:29
 * @Link: https://hesorchen.github.io/
 */
#include <bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f
#define pll pair<long long, long long>
#define ll long long
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);

ll head[500010], ct = 1;
struct node
{
    ll v, w, next;
} G[500010];
void add(ll u, ll v)
{
    G[ct].v = v;
    G[ct].w = 1;
    G[ct].next = head[u];
    head[u] = ct++;
}

ll cnt[500010];
ll dis[500010];
bool vis[500010];

void dfs1(ll s) //计算出每个结点“左边”的结点数量和“右边”的节点数量
{
    cnt[s] = 1;
    for (int i = head[s]; i; i = G[i].next)
    {
        if (vis[G[i].v])
            continue;
        vis[G[i].v] = 1;
        dfs1(G[i].v);
        cnt[s] += cnt[G[i].v];
        vis[G[i].v] = 0;
    }
}

pll a;
queue<pll> q;
void bfs(ll s, ll sum) //bfs求出结点1到其余各点的距离
{
    vis[s] = 1;
    q.push(make_pair(s, sum));
    while (!q.empty())
    {
        ll pos = q.front().first;
        ll sum = q.front().second;
        q.pop();
        for (int i = head[pos]; i; i = G[i].next)
        {
            if (!vis[G[i].v])
            {
                vis[G[i].v] = 1;
                dis[G[i].v] = sum + 1;
                q.push(make_pair(G[i].v, sum + 1));
            }
        }
    }
}
ll n, m;
void bfs2(ll pos, ll sum) //递推
{
    vis[pos] = 1;
    dis[pos] = sum;
    q.push(make_pair(pos, 5201314)); //...只需一个pos参数（不想新建queue了
    while (!q.empty())
    {

        ll pos = q.front().first;
        ll sum = q.front().second;
        q.pop();
        for (int i = head[pos]; i; i = G[i].next)
        {
            if (vis[G[i].v])
                continue;
            vis[G[i].v] = 1;
            dis[G[i].v] = dis[pos] - cnt[G[i].v] + (n - cnt[G[i].v]); //状态转移
            q.push(make_pair(G[i].v, 5201314));
        }
    }
}
int main()
{

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        ll u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    vis[1] = 1;
    dfs1(1);
    fill(vis, vis + 500010, 0);
    bfs(1, 0); //bfs求出结点1到其余各点的距离和，使用结点1递推其他点
    ll sum_1 = 0;
    for (int i = 1; i <= n; i++)
        sum_1 += dis[i];
    fill(vis, vis + 500010, 0);
    fill(dis, dis + 500010, 0);
    bfs2(1, sum_1); //递推

    ll minn = INF;
    for (int i = 1; i <= n; i++)
        minn = min(minn, dis[i]);
    for (int i = 1; i <= n; i++)
        if (minn == dis[i])
            cout << i << ' ';
    cout << endl;
    return 0;
}

D.铺地毯
遍历每个地毯，看是否包含要查询的点，包含就更新答案。
E.金币馅饼
简单的DP，不过有些细节问题：
1.开始时在起点，也就是第一次转移只能从a[1][1]开始
2.不能到达的点，比如地图大小 $4\times 4$ ，那么a[3][2]，a[4][2]，a[4][3]都不能到达，自然不能获得对应位置的金币了。
AC代码：

ll dp[110][110];
ll mp[110][110];
int main()
{
    ll n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];
    dp[1][1] = mp[1][1];
    for (int j = 2; j <= m; j++)
        for (int i = 1; i <= n; i++)
            if (max(dp[i + 1][j - 1], max(dp[i][j - 1], dp[i - 1][j - 1])))
                dp[i][j] = mp[i][j] + max(dp[i + 1][j - 1], max(dp[i][j - 1], dp[i - 1][j - 1]));
    cout << dp[n][m] << endl;
    return 0;
}