牛客小白月赛47题解

A:

• 基本思路：总剩余体积等于圆柱体体积减去内部球的体积
  • 内部球的个数：

标程： 时间复杂度

double pi = acos(-1);

int r, h;

int main() {
    int ttx;  cin >> ttx;
    while(ttx --) {
        cin >> r >> h;
        double ans = pi * r * r * h - (h / 2 / r) * 4.0 / 3 * pi * r * r * r;
        printf("%.3f\n", ans);
    }
    return 0;
}

B:

• 基本思路：猜一猜，答案应该是所有数的乘积（只划分一个集合）
  • 自己写几个小案例验证后发现这个猜测是正确的
• 证明：（这里所有数都不小于 )
  • 假设我们只划分一个集合那么代价和就是
  • 假设我们将所有的数划分为了 个集合，每个集合的乘积分别记为
    • 那么一定存在一个 使得有 存在 （即存在一个最大值）
    • 所以有 成立
    • 所以有 成立
  • 所以最优划分方案必定是将所有数都划分在同一个集合中

标程： 时间复杂度

int mod = 1e9 + 7;
int n;

int main() {
    cin >> n;
    long long ans = 1;
    int x;
    for(int i = 0; i < n; i ++) {
        scanf("%d", &x);
        ans = ans * x % mod;
    }
    cout << ans;
    return 0;
}

C:

• 基本思路：模拟小猫在排队时每一刻的所处位置
  • 但是如果直接模拟时间复杂度是 的，所以我们考虑通过算法优化这个过程
  • 我们可以考虑二分小猫最后不在队列的时间
    • 假设小猫开始不在队伍中的时间（所求的答案）是
    • 那么当时间 时小猫都会在队列中，而当时间 时小猫都不会出现在队列中
    • 这意味着小猫离开队列的时间可以通过二分 来得到
  • 注意到任何时刻小猫都不会向后移动且小猫与队头的距离是不断缩减的
    • 所以我们可以考虑双指针模型
    • 设左右指针分别为 初始时有
    • 与普通的双指针不同之处在于 指针并不是每次只移动一格
      • 那么我们可以预处理出来所有可爱值大于啾啾的小猫的位置，每次尝试让啾啾往前交换（被交换的目标小猫应该仍在队伍中）
    • 最后当 相遇时我们就得到了答案

标程： 时间复杂度二分 双指针

-----二分做法：
int n, m, a[200009];

bool check(int x) {
    if(x == n + 1) return true;  /// 显然成立
    int tp = -1;
    for(int i = 0; i < x; i ++) if(a[i] > m) tp = i;  /// 记录区间 [0, x-1] 中可以被交换的最后一只小猫的位置
    int sum = 0;
    for(int i = x; i < n; i ++) if(a[i] > m) sum ++;  /// 记录区间 [x, n-1] 中有多少只小猫的可爱值大于 啾啾
    if(tp != -1 && sum < x && tp + 1 > sum) return true;  /// 如果 啾啾 可以交换到 [0, x-1] 中的位置 且 啾啾尝试交换到tp位置的时候tp位置的小猫仍处于队列中   
    return false;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%d", a + i);
    cin >> m;
    int l = 1, r = n + 1;  /// 这里注意答案可能是 n+1
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

-----双指针做法：
int n, m;
int a[200009], pre[200009];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);
    cin >> m;
    int x = 0;
    for(int i = 1; i <= n + 1; i ++) {
        pre[i] = x;
        if(a[i] > m) x = i;
    }
    int l = 1, r = n + 1;
    while(l < r) {
        if(pre[r] >= l) r = pre[r];  /// 尝试向前交换
        if(l == r) break;
        l ++;
    }
    cout << l;
    return 0;
}

D:

• 基本思路：动态规划
  • 由于元件只能从前往后进行选取，所以我们对于每个元件只需要考虑要不要选取就可以了
  • 考虑每一位能否被选取，这只取决于其前方被选取字符串的最后一个字符串的最后一个字符
  • 所以我们想到，只要存储前面 个字符串中以某个字符结尾的选取方法中最长的选法有多长，记为
  • 那么对于第 个字符串来说，假设其第一个字符与最后一个字符串以及其长度分别是 ，则其转移方程为：
  • 由于每个状态之间互不影响求值，所以我们编程时可以省去状态中枚举 的那一维

标程： 时间复杂度

int n, m;
int f[26];
char s[200009];

int main() {
    int ttx;  cin >> ttx; 
    while(ttx --) {
        cin >> n;
        for(int i = 1; i <= n; i ++) {
            scanf("%s", s);
            m = strlen(s);
            f[s[m - 1] - 'a'] = max(f[s[m - 1] - 'a'], m + f[s[0] - 'a']);
        }
        int ans = 0;
        for(int i = 0; i < 26; i ++) ans = max(ans, f[i]);
        cout << ans << endl;
        for(int i = 0; i < 26; i ++) f[i] = 0;  /// 不要忘记初始化
    }
    return 0;
}

E:

• 基本思路：画图找规律
  • 结论：对于每个颜色而言，只需要确定其所有点的横纵坐标出现的范围即可，其覆盖的范围就是其横纵坐标最大值和最小值所确定的那个矩形范围。
  • 所以只需要分别维护每个颜色横纵坐标的最大值和最小值后利用二维差分前缀和的思想打好标记后求前缀和，最后的答案就是前缀和为 的点的个数。
• 证明：
  • 让我们观察下面四个图像：
  • 不难发现每个图像都覆盖了其所在的矩形（这里把线段看作特殊的矩形），而这四种图形完全可以变化成其余的图形，所以只需要最大最小值就可以确定所有覆盖的范围了。

标程： 时间复杂度

int n, m;
int a[1000009][4];
int sum[1009][1009];

int main() {
    cin >> n >> m;
    int x;
    for(int i = 1; i <= 1e6; i ++) a[i][1] = a[i][3] = 1e4;
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) {
        scanf("%d", &x);
        a[x][0] = max(a[x][0], i);
        a[x][1] = min(a[x][1], i);
        a[x][2] = max(a[x][2], j);
        a[x][3] = min(a[x][3], j);
    }
    for(int i = 1; i <= 1e6; i ++) {  /// 枚举每一种颜色
        if(a[i][0] == 0) continue;
        if(a[i][0] != a[i][1] || a[i][2] != a[i][3]) {  /// 注意如果这个颜色只有一个点，其不能覆盖一个矩形
            sum[a[i][1]][a[i][3]] ++;
            sum[a[i][0] + 1][a[i][2] + 1] ++;
            sum[a[i][0] + 1][a[i][3]] --;
            sum[a[i][1]][a[i][2] + 1] --;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) {
        sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        if(sum[i][j] == 0) ans ++;
    }
    cout << ans;
    return 0;
}

F:

• 基本思路：（没思路？那就！）模拟
  • 首先，让我们把问题进行分类：
    • 如果存在 集合内的点通过中转点 无法到达，那么我们所连接的边必须要能够让 能够到达所有的点
    • 如果所有 集合内的点通过中转点 都能够到达，那么我们连接的这条边应该尽可能的缩短 到所有点的距离和
    • 仔细分析后发现这两个问题的解决方法是不一样的，所以我们分开解决它们
  • 对于第一类问题：
    • 我们建立一个新集合为 代表所有 无法到达的点
    • 我们知道如果将 指向根节点 其必能到达 中的所有结点
      • 我们思考为什么会这样
      • ……（思考中）
      • 哦！这是因为 是所有结点的公共祖先，如果一个结点 能够到达所另一个结点 的某个祖先，那么这个结点 必定能到达 （这是显然的）
      • 那么对于一个集合 呢？我们自然而然的想到了它中间所有点的公共祖先，将 连向它们的公共祖先这样 必定能够到达所有的结点
    • 现在我们考虑怎么使得答案最优（这是因为集合 的公共祖先可能会有多个）
    • 感性的画图分析，我们最后得到的结论应该是：我们将选择深度最深的那个公共祖先作为连接点最优
    • 至此第一类问题解决了（其实根据视频题解，第一类问题其实也可以类似第二类一样，通过枚举解决）
  • 对于第二类问题：
    • 这里我们只需要考虑以 为根的子树就可以了（因为所有集合 中的点都在这颗子树中）
    • 我们考虑暴力枚举每个结点作为连接点时 到所有结点的距离和的变化
    • 如果要维护出上面这个信息，我们显然需要先预处理一些额外的信息来进行计算，所以我们定义：
      • 为以 为根的子树中有多少个集合 中的点
      • 为 这个结点到 的距离（也是其在这个子树中的深度）
      • 为从 到以这个点为根的子树中所有属于 集合的点的距离和（这个值可以通过 求出来，具体看标程）
    • 那么如果我们选取某个结点 作为 的连接点的话，会使 到所有 集合中点的距离和变为：
    • 至此第二类问题解决
• 坑点
  • 的值可能会超过 能够表示的范围所以要用 来存储
  • 也可能属于 这个集合（这意味着答案可能为 ）
• 小技巧
  • 当我们分析结束后，可以发现，这颗树其实是可以分为两部分来看的：
    • 以 为根
    • 以 为根
  • 所以我们可以干脆将以 为根的子树分离出来（不对 建立入边）
  • 这样在后续的编程中会省去许多麻烦，代码也会更加的直观（比如第一类问题和第二类问题中都需要用到 “深度” 这个信息，不过这里分别是对根为 和根为 来说的，如果将树分开就没有这个问题了，标程也是这样实现的

标程：

#define ll long long 

int n, m, k;
int head[200009], nex[200009], to[200009], tot;
void add(int x, int y) {
    nex[++ tot] = head[x], head[x] = tot, to[tot] = y;
}
int cnt[200009];
pair<int, int> a[200009];

int dis[200009], sum[200009];
ll val[200009];
void dfs(int x) {
    if(cnt[x]) sum[x] ++;
    for(int i = head[x], p; i; i = nex[i]) {
        p = to[i];  dis[p] = dis[x] + 1;
        dfs(p);
        sum[x] += sum[p], val[x] += val[p] + sum[p];
    }
}
ll dfs2(int x) {
    if(sum[x] != sum[1]) return 1e18;
    ll ans = val[x];
    for(int i = head[x], p; i; i = nex[i]) {
        p = to[i];  
        ans = min(ans, dfs2(p));
    }
    return ans;
}
ll dfs3(int x) {
    ll ans = (dis[x] - dis[k] - 1) * 1ll * sum[x];  /// 若 x==k 这里会计算出负值，所以统计答案时需要对 0 取 max
    for(int i = head[x], p; i; i = nex[i]) {
        p = to[i];
        ans = max(ans, dfs3(p));
    }
    return ans;
}
int main() {
    cin >> n;
    int x, y;
    for(int i = 1; i < n; i ++) {
        scanf("%d%d", &a[i].first, &a[i].second);  /// 存下所有的边
    }
    cin >> m >> k;
    for(int i = 1; i < n; i ++) {
        if(a[i].second != k) add(a[i].first, a[i].second);  /// 跳过 k 的入边
    }
    for(int i = 1; i <= m; i ++) {
        scanf("%d", &x);
        cnt[x] ++;  /// 记录某个结点是否是 m 集合内的点
    }
    ll ans;
    dfs(1);  if(k != 1) dfs(k);  /// 这里需要注意特判 k 为树根的情况，不能重复dfs
    if(sum[1] == 0 || k == 1) {  /// 所有标记点都在 K 子树内部 
        ans = val[k] - max(0ll, dfs3(k));
    } else {
        ans = val[k] + sum[1] + dfs2(1);
    }
    cout << ans;
    return 0;
}