2. 勇闯币圈

题目描述

最近以比特币为代表的数字货币市场非常动荡，聪明的小明打算用马尔科夫链来建模股市。如图所示，该模型有三种状态：“行情稳定”，“行情大跌”以及“行情大涨”。每一个状态都以一定的概率转化到下一个状态。比如，“行情稳定”以0.4的概率转化到“行情大跌”的状态。

不妨设“行情稳定”，“行情大跌”以及“行情大涨”分别为状态0，状态1和状态2。我们可以定义概率转移矩阵P，其中P(i,j)的数值表示的是状态j转移到状态i的概率。如图所示的概率转移矩阵为：

有了概率转移矩阵P，我们只要知道一个初始状态 ，我们就容易可以知道第 t 步三种状态的概率了。由此可以知道行情什么时候大涨大跌，从而发家致富，赢取白富美，走向人生巅峰。比如我们想知道第1步之后“行情大跌”的概率，那么由全概率公式和马尔科夫链的性质(第t步的概率只和第t-1步有关)：

可以通过该模型，计算出第t步的“行情大涨”的概率吗？如果这个概率大于0.5那么输出1，否则输出0。

输入描述

输出描述

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int t;
    vector<double> a(3);
    vector<vector<double>> p(3, vector<double>(3));
    cin >> t;
    for (int i = 0; i < 3; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> p[i][j];
        }
    }
    while (t--) {
        auto tmp = a;
        for (int i = 0; i < 3; ++i) {
            a[i] = 0;
            for (int j = 0; j < 3; ++j) {
                a[i] += tmp[j] * p[i][j];
            }
        }
    }
    cout << (a[2] > 0.5 ? 1 : 0) << '\n';
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

3. 迎宾车队

题目描述

输入描述

输出描述

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0, j = 0; j < n; ++j) {
        while (i < n && a[j] - a[i] > 10) {
            i += 1;
        }
        ans = max(ans, j - i + 1);
    }
    cout << ans << '\n';
    return 0;
}

4. 水站的水流量

题目描述

有一个水站网络共有n层，第i层有i个水站节点，如图所示连接，水流单向流动。

每个水站在达到MAX个水流量时，称该水站满负荷工作，后续流进该水站的水流量，将会分为两等份流向它后面所连接的两个水站。若每秒都有流入第一个水站MAX个水流量，请问第T秒有多少个水站是满负荷工作的？

输入描述

输出描述

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, t;
    cin >> n >> t;
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    int N = n * (n + 1) / 2;
    vector<int> a(N + 1);
    int b = 1 << 10;
    while (t--) {
        a[1] += b;
        int s = 1, d = 1;
        while (s <= N - n - n + 2) {
            for (int i = s; i < s + d; ++i) {
                if (a[i] > b) {
                    int r = (a[i] - b) / 2;
                    a[i + d] += r;
                    a[i + d + 1] += r;
                    a[i] = b;
                }
            }
            s += d;
            d += 1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        if (a[i] >= b) {
            ans += 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

5. 定点轰炸

题目描述

输入描述

输出描述