牛客周赛 Round 62

A

模拟题。

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    swap(s[0],s[1]);
    cout<<s;
}

B

模拟题。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n,x;
    cin>>n>>x;
    int ans=0;
    if(x==0)
    {
        cout<<0<<'\n';
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        int q;
        cin>>q;
        if(x>0)
        x-=q,ans+=q;
        else
        x+=q,ans+=q;
    //    cout<<x<<'\n';
        if(x==0)
        {
            cout<<ans;
            return 0;
        }
    }
    cout<<ans<<'\n';
}

C

特判一下圆心即可，计算圆形距和半径，判断是否包含，最后排序一下即可。

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
#include <bits/stdc++.h>
using namespace std;
struct Circle
{
    double dis;
    double c;
};
const double pi=3.14159265358979324;
double cal(int x, int y)
{
    return sqrt(1.0 * x * x + 1.0 * y * y);
}
int main()
{
    int n, k;
    cin >> n >> k;
    vector<Circle> ci;
    for (int i = 0; i < n; i++)
    {
        double x, y, r;
        cin >> x >> y >> r;
        double dis = cal(x, y);
        double c = 0;
        if (dis < r)
        {
            c = pi * r * r * (r- dis);
        }
        else if (x == 0 && y == 0)
        {
            c = pi * r * r *r;
        }
        ci.push_back({dis, c});
    }  
    sort(ci.begin(), ci.end(), [](const Circle &a, const Circle &b)
         { return a.c < b.c; });
    double ans = 0.0;
    for (int i = 0; i < n - k; i++)
    {
        ans += ci[i].c;
    }
    printf("%.14f\n", ans);
    return 0;
}

D

解题思路：

  1. 树的基本性质：树是一种无环连通图，起点为节点 1。我们需要从节点 1 开始，逐步染红邻近的白色节点，直到所有的邻点都染红为止。

  2. 期望值的递归计算：

    • 当我们从某个节点 $ u $ 移动到一个相邻的白色节点 $ v $，期望值的计算可以递归进行。
    • 每个节点的期望值等于其所有子节点的期望值加上1（因为当前节点本身染红）。

  3. 递归公式：

    • 对于节点 $ u \(，它的期望值可以表示为其所有子节点的期望值的平均数加1：\) E(u) = 1 + _{v } E(v) $
    • 根节点的期望值是整个树的期望。

  4. 求模逆元：

    • 给出的答案需要对 \(10^9+7\) 取模。在计算有理数的取模时，我们需要使用乘法逆元来处理分数。

  5. DFS求解树的期望值：

    • 我们可以用DFS遍历整棵树，同时根据公式来累积期望值。
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
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
const int MAXN = 100005;
vector<int> G[MAXN];
int n;
int inv[MAXN];
int ksm(int a, int b, int mod)
{
    int res = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b /= 2;
    }
    return res;
}
void pre()
{
    for (int i = 1; i <= n; i++)
    {
        inv[i] = ksm(i, MOD - 2, MOD);
    }
}

int dfs(int u, int v)
{
    int count = 0;
    int total = 0;
    for (int ch : G[u])
    {
        if (ch == v)
            continue;
        int e = dfs(ch, u);
        total = (total + e) % MOD;
        count++;
    }
    if (count == 0)
    {
        return 1;
    }
    else
    {
        total = (total * inv[count]) % MOD;
        return (total + 1) % MOD;
    }
}

signed main()
{
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    pre();

    int ans = dfs(1, -1);
    cout << ans << '\n';
    return 0;
}

E

求区间第k大板子。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
template <class T>
void read(T &x)
{
    T ans = 0;
    short f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        ans = (ans << 1) + (ans << 3) + (ch ^ 48);
        ch = getchar();
    }
    x = ans * f;
}
#define maxn 200005
struct
{
    int l, r;
    vector<int> s;
} tree[maxn << 2];
int n, m;
int a[maxn], p[maxn], t;
int l, r, k;
vector<int> S[maxn];
void build(int x, int l, int r)
{
    int mid = (l + r) >> 1;
    tree[x].l = l, tree[x].r = r;
    if (l == r)
    {
        tree[x].s = S[mid];
        return;
    }
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    if (x == 1)
        return;
    vector<int>::iterator it1 = tree[x << 1].s.begin();
    vector<int>::iterator it2 = tree[x << 1 | 1].s.begin();
    while (it1 != tree[x << 1].s.end() && it2 != tree[x << 1 | 1].s.end())
        if (*it1 < *it2)
            tree[x].s.push_back(*it1), it1++;
        else
            tree[x].s.push_back(*it2), it2++;
    while (it1 != tree[x << 1].s.end())
        tree[x].s.push_back(*it1), it1++;
    while (it2 != tree[x << 1 | 1].s.end())
        tree[x].s.push_back(*it2), it2++;
}
int ask(int x, int k)
{
    if (tree[x].l == tree[x].r)
        return *tree[x].s.begin();
    int val = upper_bound(tree[x << 1].s.begin(), tree[x << 1].s.end(), r) - upper_bound(tree[x << 1].s.begin(), tree[x << 1].s.end(), l - 1);
    if (val >= k)
        return ask(x << 1, k);
    else
        return ask(x << 1 | 1, k - val);
}
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        read(a[i]), p[i] = a[i];
    sort(p + 1, p + n + 1);
    t = unique(p + 1, p + n + 1) - p - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(p + 1, p + t + 1, a[i]) - p;
        S[a[i]].push_back(i);
    }
    build(1, 1, t);
    while (m--)
    {
        read(l), read(r);
        k = (r - l) / 2 + 1;
        printf("%d\n", p[a[ask(1, k)]]);
    }
}

F

求区间第k大板子。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
template <class T>
void read(T &x)
{
    T ans = 0;
    short f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        ans = (ans << 1) + (ans << 3) + (ch ^ 48);
        ch = getchar();
    }
    x = ans * f;
}
#define maxn 200005
struct
{
    int l, r;
    vector<int> s;
} tree[maxn << 2];
int n, m;
int a[maxn], p[maxn], t;
int l, r, k;
vector<int> S[maxn];
void build(int x, int l, int r)
{
    int mid = (l + r) >> 1;
    tree[x].l = l, tree[x].r = r;
    if (l == r)
    {
        tree[x].s = S[mid];
        return;
    }
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    if (x == 1)
        return;
    vector<int>::iterator it1 = tree[x << 1].s.begin();
    vector<int>::iterator it2 = tree[x << 1 | 1].s.begin();
    while (it1 != tree[x << 1].s.end() && it2 != tree[x << 1 | 1].s.end())
        if (*it1 < *it2)
            tree[x].s.push_back(*it1), it1++;
        else
            tree[x].s.push_back(*it2), it2++;
    while (it1 != tree[x << 1].s.end())
        tree[x].s.push_back(*it1), it1++;
    while (it2 != tree[x << 1 | 1].s.end())
        tree[x].s.push_back(*it2), it2++;
}
int ask(int x, int k)
{
    if (tree[x].l == tree[x].r)
        return *tree[x].s.begin();
    int val = upper_bound(tree[x << 1].s.begin(), tree[x << 1].s.end(), r) - upper_bound(tree[x << 1].s.begin(), tree[x << 1].s.end(), l - 1);
    if (val >= k)
        return ask(x << 1, k);
    else
        return ask(x << 1 | 1, k - val);
}
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        read(a[i]), p[i] = a[i];
    sort(p + 1, p + n + 1);
    t = unique(p + 1, p + n + 1) - p - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(p + 1, p + t + 1, a[i]) - p;
        S[a[i]].push_back(i);
    }
    build(1, 1, t);
    while (m--)
    {
        read(l), read(r);
        k = (r - l) / 2 + 1;
        printf("%d\n", p[a[ask(1, k)]]);
    }
}

G

随机化做法。

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
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#ifdef WIDA_WORK_SPACE
    #include <wida/debug.h>
#endif
 
using i64 = long long;
 
mt19937_64 rgen(chrono::steady_clock::now().time_since_epoch().count());
 
signed main() {
    int n, x;
    cin >> n >> x;
 
    vector<int> id(n), ai(n);
    iota(id.begin(), id.end(), 0);
    for (int i = 0; i < n; i++) {
        cin >> ai[i];
    }
 
    int Min = 1E9;
    vector<int> ans;
    for (int t = 1; t <= 670000; t++) {
        shuffle(id.begin(), id.end(), rgen);
 
        int add = 0, x_ = x;
        for (auto &i : id) {
            if (!x_) break;
 
            int now = ai[i];
            add += now;
            if (x_ > 0) {
                x_ -= now;
            } else {
                x_ += now;
            }
             
            if (add >= Min) break;
        }
         
        if (Min > add) {
            Min = add;
            vector<int> chk;
            for (auto &i : id) {
                chk.push_back(i);
            }
            ans = chk;
        }
    }
     
    cout << Min << "\n";
    for (auto &i : ans) {
        cout << i + 1 << " ";
    }
}
 
int __OI_INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    return 0;
}();