Aczy156

Contest CSU 2022 预选赛 补题

[TOC]

CSU 2022 预选赛 补题

A

题目大意：计算期望。概率*次数，其中，概率会随着次数的增加，按照一定规律进行变化。

进行模拟即可。

#include <iostream>
using namespace std;

double a, b, c, d, e, na;
int n, T;
double ans, base;

int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; ++i) {
        ans = 0;base = 1.0;
        scanf("%lf%lf%lf%lf%lf%d", &a, &b, &c, &d, &e, &n);
        na = a;
        int j;
        for (j = 1; j <= n; ++j) {
            ans += base*a*j;
            base *= (1-a)*1.0;
        }
        while (na < 1) {
            na += e;
            if (na >= 1) na = 1.0;
            ans += base*na*j;
            j++;
            base *= (1-na)*1.0;

        }
        printf("%.4lf\n", ans);
    }
    return 0;
}

B

C

题目大意：最短路。会卡时间。需要堆优化。

注意权重是进行累乘。

#include <iostream>
using namespace std;
#include <vector>
typedef pair<int, double> Pair;
const int maxpoints = 2e3+9, maxedges = 1e5+9;
vector<Pair> G[maxpoints];
int n, m, ta, tb, bg, ed;
double tc;

struct nd {
    int pos;
    double dis;
    nd(int pos, double dis): pos(pos), dis(dis){}
    bool operator < (const nd n) const {
        return dis < n.dis;
    }
};
#include <queue>
priority_queue<nd> pq;

double d[maxpoints] = {0}, d1, d2;
int vis[maxpoints] = {0};
int u, v;
void dijkstra(int s, int e) {
    d[s] = 1.0;
    pq.push({s, d[s]});
    while (!pq.empty()) {
        u = pq.top().pos, d1 = pq.top().dis;pq.pop();
        if (!vis[u]) {
            vis[u] = 1;
            for (auto tm : G[u]) {
                v = tm.first, d2 = tm.second;
                if (d[v] < d1*d2) {
                    d[v] = d1*d2;
                    if (!vis[v]) pq.push({v, d[v]});
                }
            }
        }

    }
    printf("%.4lf\n", 100*1.0/d[e]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%lf", &ta, &tb, &tc);
        G[ta].push_back(make_pair(tb, 1-1.0*tc/100.0));
        G[tb].push_back(make_pair(ta, 1-1.0*tc/100.0));
    }
    scanf("%d%d", &bg, &ed);
    dijkstra(bg, ed);
    return 0;
}

D

E

题目大意：斐波那契数列

递推，然后递推的过程中要取余。

#include <iostream>
using namespace std;
int m;
const int maxm = 1e6+9;
long long f[maxm];
const long long mod = 998244353;
long long ans = 0;

int main() {
    scanf("%d", &m); //
    if (m == 1) {
        cout<<"1\n";return 0;
    }
    if (m == 2) {
        cout<<"3\n";return 0;
    }
    f[1] = 1;f[2] = 2;f[3] = f[1]+f[2];
    for (int i = 3; i <= m; ++i) {
        f[i] = f[i-1]+f[i-2];f[i] %= mod;
        ans += f[i]; ans %= mod;
    }
    printf("%lld\n", ans+3);
    return 0;
}
Posted on Feb 4, 2020