Burnling's Blog
0%

CF1988

发表于 更新于 分类于 ，

这场打得太难受了 熬夜打场 CF 结果 Rating $-85$，，，我图啥呢

A. Split the Multiset

题意简述

你有一个多重集 $S$，初始时包含一个正整数 $n$。此外，给定一个正整数 $k$。

在一次操作中，你可以选择多重集中的任意一个正整数 $u$ 并将其移除，然后插入不超过 $k$ 个正整数，使得这些正整数的和等于 $u$。

求使 $S$ 中包含 $n$ 个数字 1 所需的最少操作次数。

思路分析

到最后也没 A 掉 A🤣

看了 Editorial 下的一条 comment，醍醐灌顶啊

将 ${n}$ 看成 ${\overbrace{1,\cdots,1}^{n}}$，其中每两个相邻的 $1$ 之间有一条连接线。

现在每次可以断掉 $k-1$ 根连接线。

问需要多少次操作。

将问题转化为这样，答案就很显然是 $\left\lceil \dfrac{n-1}{k-1} \right\rceil$ 了。

反思

顺着想不容易想不妨试试逆着想。

像初学 dp 的那道数字三角形一样。

他妈的这么小的数据范围就别惦记你那个 B 优化了。

暴力递归都能草过去😋 

1
2
3
4
5
6
int f(int n, int k)
{
    if (n == 1) return 0;
    else if (n <= k) return 1;
    return 1 + f(n - (k - 1), k);
}

B. Make Majority

题意简述

给定一个序列 $[a_1, \ldots, a_n]$，其中每个元素 $a_i$ 不是 0 就是 1。你可以对该序列进行若干次（可能为零次）操作。在每次操作中，你选择两个整数 $1 \le l \le r \le |a|$（其中 $|a|$ 为当前序列的长度），并将子序列 $[a_l, \ldots, a_r]$ 替换为一个元素 $x$，其中 $x$ 为 $[a_l, \ldots, a_r]$ 的多数元素。

多数元素定义如下：假设序列中有 $c_0$ 个 0 和 $c_1$ 个 1。

  • 如果 $c_0 \ge c_1$，多数元素为 0；
  • 如果 $c_0 < c_1$，多数元素为 1。

判断是否可以通过有限次操作将 $a$ 变为 $[1]$。

思路分析

首先，由于我们的目标是 $[1]$，所以我们需要让 $0$ 尽可能地少。

那么显然，我们可以将连续的若干个 $0$ 合并为一个。

这么一次操作过后，原序列一定变为了在若干个 $1$ 里面夹杂了若干个单个的 $0$ 的序列。

由于此时不含连续的 $0$，那么我们消除一个 $0$ 就需要其左右是 $1$。对这个 $[1,0,1]$ 的序列的操作结果为 $[1]$，$0$ 和 $1$ 各少了一个。

那么此次操作对 $c_0$ 和 $c_1$ 的大小关系没有影响。

所以我们直接扫一遍合并后的序列记录 $c_0$ 和 $c_1$ 的数量比较即可。

C. Increasing Sequence with Fixed OR

题意简述

给定一个正整数 $n$，找到满足以下条件的最长正整数序列 $a = [a_1, a_2, \ldots, a_k]$ 并输出该序列：

  • 对于所有的 $1 \le i \le k$，有 $a_i \le n$。
  • 序列 $a$ 严格递增，即对于所有的 $2 \le i \le k$，有 $ai > a{i-1}$。
  • 对于所有的 $2 \le i \le k$，有 $ai \,|\, a{i-1} = n$，其中 $|$ 表示按位或运算。

思路分析

为了保证 $ai \,|\, a{i-1} = n$，我们需要对于 $n$ 的二进制下某位为 $0$ 时，$ai$ 与 $a{i-1}$ 在该位不同时为 $0$。

又要这个上升序列最长，

所以可以每次抠掉 $n$ 的二进制表示中某一位上的 $1$ 。

从高位开始抠即可。

D. The Omnipotent Monster Killer

题意简述

你是一名怪物杀手，想要消灭一群怪物。这些怪物在一棵有 $n$ 个顶点的树上。顶点 $i$ ($1 \le i \le n$) 有一个攻击力为 $a_i$ 的怪物。你将与怪物战斗 $10^{100}$ 回合。

每回合依次发生以下事件：

  1. 所有活着的怪物攻击你。你的健康值会减少所有活着怪物攻击力的总和。
  2. 你选择一些（可能是全部或没有）怪物杀死。被杀死的怪物不会再攻击。

有一个限制：在一个回合中，你不能杀死两个直接相连的怪物。

如果你最优地选择要攻击的怪物，求在所有回合结束后，你的最小健康损失是多少？

思路分析

这里的 “直接相连的” 指的是在最初直接相连的，即二者之间仅靠一条边相连。

那么就是一个经典的树上 dp 问题了。

设 $\text{dp}_{i,j}$ 表示 $i$ 为根的子树中，节点 $i$ 上的怪物在第 $j$ 回合被杀死所造成的最少伤害。

$\text{dp}_{i,j}$ 应由两部分组成：节点 $i$ 上的怪物造成的伤害 + 以 $i$ 为根的子树内的怪物造成的总伤害。

而节点 $i$ 上的怪物在前 $j$ 回合造成了 $a_i\times j$ 的伤害。

故转移方程为 $\text{dp}{i,j}=j \times a_i + \sum\limits{v\in s(u)} \min\limits{t\neq j}\text{dp}{v,t} $

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 10;
const long long inf = 1e18;

long long A[maxN];

vector<int> G[maxN];

long long dp[maxN][30];
 
void dfs(int p,int fa){
    for(int i = 1;i<30;i++) dp[p][i] = i * A[p];
    for(auto v : G[p]){
        if(v == fa) continue;
        dfs(v,p);

        for(int j = 1;j<=25;j++){
            long long mi = inf;
            for(int k = 1;k<=25;k++){
                if(j == k) continue;
                mi = min(mi,dp[v][k]);
            }
            dp[p][j] += mi;
        }
    }
}
inline void solve(){
    int N;
    scanf("%d",&N);
    for(int i = 1;i<=N;i++){
        scanf("%lld",&A[i]);
        G[i].clear();
    } 

    for(int i = 2;i<=N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    long long ans = inf;

    for(int i = 1;i<=25;i++) ans = min(ans,dp[1][i]);

    printf("%lld\n",ans);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}