百度之星2022题目记录

1 介绍

本博客记录百度之星2022编程比赛相关题目。

2 训练–钻石level

题目1：小度养小猫

vip题目，未开放！

题目2：BD202203简单题

解题思路：贪心。
贪心策略：上升序列升得越慢越好，下降序列降得越慢越好。
先去除相邻相等元素的干扰。然后判断，如果当前元素b[i]既可以加入到上升序列中也可以加入到下降序列中，比较b[i]与b[i+1]的大小，如果b[i]<b[i+1]那么将b[i]放入上升序列中，上升序列会升得慢一些。

C++代码如下，

#include<bits/stdc++.h> 

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

int main( )
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    //相邻从重复元素不影响最终答案，把它去掉
    vector<int> b;
    for (int i = 1; i <= n; ++i) {
        if (b.empty() || b.back() != a[i]) {
            b.emplace_back(a[i]);
        }
    }

    int x = 0; //上升序列的末尾值
    int y = 1e9 + 10; //下降序列的末尾值
    for (int i = 0; i < b.size(); ++i) {
        if (x <= b[i] && y >= b[i]) { //b[i]可以加入上升序列中，也可以加入下降序列中
            //贪心：上升序列升得越慢越好，下降序列将得越慢越好
            if (i+1 < b.size() && b[i] < b[i+1]) {//将它加入上升序列中
                x = b[i];
            } else {
                y = b[i];
            }
        } else if (x <= b[i]) {
            x = b[i];
        } else if (y >= b[i]) {
            y = b[i];
        } else {
            cout << "no" << endl;
            return 0;
        }
    }

    cout << "yes" << endl;
    return 0;
}

题目3：大水题

vip题目，未开放！

题目4：和

vip题目，未开放。

题目5：课程安排

vip题目，未开放。

题目6：BD202211逃离这棵树

解题思路：

$f_u$表示从$u$出发到达叶结点的时间的数学期望，它可以由它的子结点$v$的$f_v$和它本身$f_u$表示。具体而言，它的计算包含两部分，一是不停留部分，二是停留部分。

不停留部分：
∑ v ∈ { f a t h e r = u } ( f v + 1 ) ⋅ q u v p u + ∑ v ∈ { f a t h e r = u } q u v (1) \frac{\sum_{v\in \{father=u\}} (f_v + 1) \cdot q_{uv}} {p_u + \sum_{v \in \{father=u\}} q_{uv}} \tag{1} pu​+∑v∈{father=u}​quv​∑v∈{father=u}​(fv​+1)⋅quv​​(1)

停留部分：
p u p u + ∑ v ∈ { f a t h e r = u } q u v ( f u + 1 ) (2) \frac{p_u}{p_u + \sum_{v \in \{father=u\}} q_{uv}}(f_u+1) \tag{2} pu​+∑v∈{father=u}​quv​pu​​(fu​+1)(2)
公式(1)和公式(2)中的记号解释如下，

$p_u$表示结点$u$的权值。

{ f a t h e r = u } \{father=u\} {father=u}表示父结点是$u$的结点的集合，也即结点$u$的子结点的集合。

v ∈ { f a t h e r = u } ,   q u v v\in \{father = u\},\ q_{uv} v∈{father=u}, quv​表示从结点$u$到结点$v$的边的权值。

$(f_v+1)$和$(f_u+1)$中的$+1$表示时间过去了1秒。

即，
f u = ∑ v ∈ { f a t h e r = u } ( f v + 1 ) ⋅ q u v p u + ∑ v ∈ { f a t h e r = u } q u v + p u p u + ∑ v ∈ { f a t h e r = u } q u v ( f u + 1 ) (3) f_u = \frac{\sum_{v\in \{father=u\}} (f_v + 1) \cdot q_{uv}} {p_u + \sum_{v \in \{father=u\}} q_{uv}} + \frac{p_u}{p_u + \sum_{v \in \{father=u\}} q_{uv}}(f_u+1) \tag{3} fu​=pu​+∑v∈{father=u}​quv​∑v∈{father=u}​(fv​+1)⋅quv​​+pu​+∑v∈{father=u}​quv​pu​​(fu​+1)(3)

将上述等式两边的$f_u$进行合并，然后化简可得，
f u = ∑ v ∈ { f a t h e r = u } ( f v + 1 ) q u v + p u ∑ v ∈ { f a t h e r = u } q u v (4) f_u = \frac{\sum_{v \in \{father=u\}} (f_v + 1)q_{uv} + p_u}{\sum_{v\in \{father=u\}} q_{uv}} \tag{4} fu​=∑v∈{father=u}​quv​∑v∈{father=u}​(fv​+1)quv​+pu​​(4)

又因为结果需要对$mod=998244353$取模，而它本身是一个质数，

C++代码如下，

#include<bits/stdc++.h> 
#define endl '\n'
#define int long long 
#define all(x) x.begin(), x.end()
using namespace std;
template<typename... Args>
void debug(Args... args) {
    ((std::cout << args << ", "), ...);
    cout << "\n";
}

const int N = 1e6 + 10;
const int mod = 998244353;
int n;
int h[N], e[N], ne[N], q[N], idx;
int p[N], f[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], q[idx] = c, h[a] = idx++;
}

int qmi(int a, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = ans * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return ans;
}

void dfs(int u) {
    int sum = p[u];
    int tot = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        sum = (sum + (f[j] + 1) * q[i] % mod) % mod;
        tot = (q[i] + tot) % mod;
    }
    f[u] = sum * qmi(tot, mod - 2) % mod; //每个结点的???
}

void solve() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i]; //每个结点的权值
    }
    for (int i = 2; i <= n; ++i) {
        int x, w; cin >> x >> w;
        add(x, i, w);
    }
    dfs(1);
    cout << f[1] << endl;
}

signed main() {
    std::ios::sync_with_stdio(false); std::cin.tie(0);
    solve();
    return 0;
}

3 参考

2005年-2023年百度之星题集
百度之星2022