【算法题解】2022河南萌新联赛第（三）场：河南大学

比赛链接：https://ac.nowcoder.com/acm/contest/37782#question

墨染空大佬也来了，直接AK（orz）

A 玉米大炮

🍅 题目大意

链接：https://ac.nowcoder.com/acm/contest/37782/A
来源：牛客网

🌮 思路：二分答案

时间越长，击溃博士的概率越大。所以时间具有单调性，如果x是击溃博士的最小时间，那么x+1肯定也能击溃博士，x-1肯定无法击溃博士，所以大于x的都能击溃，小于x的都不能击溃，所以也具有两段性，所以可以使用二分来做。这里我们需要注意一个细节，就是二分的左右边界，左边界最小是0，因为第一发不需要时间。右边界是1e18，假设只有一个大炮每次只能攻击1生命值，装填时间是1e9,而博士生命值是1e9，所以最多需要1e18时间。

🥔 代码

#include 
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
ll n, m;
ll a[N], b[N];
bool check(ll x)
{
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if(a[i] * (x / b[i]) + a[i]>=m)
        {
            return true;
        }
        ans += a[i] * (x / b[i]) + a[i];
        if (ans >= m)
        return true;
    }
    return false;
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
    }
    ll l = 0, r = 1e18;
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r;
    return;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}
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

B 逆序对计数

🍅 题目大意

链接：https://ac.nowcoder.com/acm/contest/37782/B
来源：牛客网

🌮 思路：二分答案

一个区间改变了顺序，那么不影响区间外的逆序对个数，只影响区间内的个数，一个区间如果反转了，那么此区间的逆序对个数就变成了区间总对数减去原来区间内的总逆序对个数。每次询问相互独立，所以我们只需要记录每个区间的逆序对个数就可以解决问题了。考虑从[l,r] ==> [l, r + 1]的逆序对个数增量，可以记录[l, r]区间中必a[r + 1]大的元素个数。统计完直接记录即可。当然也可以用树状数组求逆序对或者归并排序。

🥔 代码

动态规划版

#include 
using namespace std;
const int N = 6e3 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int f[N][N]; // l到r地区间内的逆序对数量
int a[N];
int n, q;
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = n; i >= 1; i--)
    {
        int cnt = 0;
        for (int j = i + 1; j <= n; j++)
        {
            f[i][j] = f[i + 1][j]; // [l,r]内的区间逆序对个数就等于[l + 1, r] 区间内的个数在加上有了l之后的个数
            if (a[i] > a[j])
                cnt++;//统计有了l后[l,r]区间内的逆序对增量
            f[i][j] += cnt;
        }
    }
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        int len = r - l + 1;
        int ans = f[1][n] - f[l][r] + (len - 1) * len / 2 - f[l][r];
        cout << ans << endl;
    }
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}
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

C.区间操作

🍿 题目

链接：https://ac.nowcoder.com/acm/contest/37782/C
来源：牛客网

🍑 思路：线性筛 + 线段树

我们先来推导一下：

这样我们就可以知道要求什么了。我们需要记录每个b[i]的所有质因数的指数的和。

每次都是求区间的和和修改区间，所以我们可以使用线段树，由于多次修改区间，所以还需要加懒标记。

这里还有一个问题，如果我们暴力求每个数漂亮值，时间复杂度O(根号x）那么一定会超时。x最大是4e6，所以我们只需要求出2000以内的所有质数就行（大约300个），那么那么求每一个数的指数个数的话就只需要处理300次即可。求质数我们可以使用线性筛。

🍐 代码

#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int w[N];
bool st[N];
int primes[N];
int cnt1;
struct Node
{
    int l, r;
    ll sum, add;
} tr[N * 4];
void init()
{
    for (int i = 2; i <= 2e3; i++)
    {
        if (!st[i])
        {
            primes[cnt1++] = i;
        }
        for (int j = 0; primes[j] <= 2e3 / i; j++)
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                break;
            }
        }
    }
}
// 求一个数的漂亮值
int get(int d)
{
    int cnt = 0;
    for (int i = 0; i < cnt1; i++)
    {
        if (d % primes[i] == 0)
        {
            while (d % primes[i] == 0)
            {
                cnt++;
                d /= primes[i];
            }
        }
    }
    if(d > 1)
        cnt++;
    return cnt;
}
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
    if (tr[u].add)
    {
        int d = tr[u].add;
        tr[u << 1].add += d;
        tr[u << 1].sum += d * (tr[u << 1].r - tr[u << 1].l + 1);
        tr[u << 1 | 1].add += d;
        tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * d;
        tr[u].add = 0;
    }
}
void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = {l, l, get(w[l]), 0};
    }
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += d * (tr[u].r - tr[u].l + 1);
        tr[u].add += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
            modify(u << 1, l, r, d);
        if (r > mid)
            modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}
ll query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        ll sum = 0;
        if (l <= mid)
            sum += query(u << 1, l, r);
        if (r > mid)
            sum += query(u << 1 | 1, l, r);
        return sum;
    }
}
void solve()
{
    init();
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d",&w[i]);
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--)
    {
        ll k, l, r, s;
        cin>>k>>l>>r;
        if (k == 1)
        {
            cout << query(1, l, r) << endl;
        }
        else
        {
            cin>>s;
            s= get(s);
            modify(1, l, r, s);
        }
    }
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

H 树上问题

🌾 题目

链接：https://ac.nowcoder.com/acm/contest/37782/H
来源：牛客网

🍨 思路：树形DP

一个点的代价最大代价就等于从这个点到其他点的最长路径。我们需要求三个相连的点的最长路径和，那么首先我们就需要先求出每个点的最大代价。

那如何求一个点到其他点的最长路径呢？

一个点到其他点的最长路径无非是从它的几个子节点和它的父节点中寻找最长路径在加上自己的值。也就是向上走或者向下走的问题。

向下走是很容易的，我们只需要使用dfs寻找每一个点向下走的最长路径，然后在用子节点更新父节点。这里利用了回溯的特点。寻找向下走的最长距离还需要记录次长距离和分别是从哪个点下去的。具体为什么要求次长距离我们等一下在求向上走的时候需要用到。

假设我们当前正在求2号点向下走的情况，可以遍历它的所有子节点5和6,在记录它的所有子节点的路径，保留最长路径和次长路径即可，通过一次dfs遍历我们就可以球的所有点向下走的最长路径。

我们再来看看向上走的情况，假设我们当前正在求5号点向上走的最长路径，那么它需要在2号点的其他子节点的最长路径以及2号点向上走的最长路径中找。如果我们一个一个找的话就回超时。这时我们在向下走时得到的最长距离和次长距离就排上了用场。

• 5号点位于最长路径上，那么它向上走的距离就取2号点的子节点次长距离和2号点向上最长距离的最大值即可。这样我们的复杂度是O(1)的。

• 假设5号节点不在2号点的最长路径上，那么一定2好点的最长距离一定在它的其他子节点上。那5号点向上走的最长路径就等于2号点向上走的最长路径和2号点向下走的最长路径取最大值即可。

求得每个点向上走和向下走的最长路径之后，它俩取最大值就是这个点到其他点的最长路径。

接下来就是求三个相连的点的最长路径的和的最大值了。如果求呢？

有两种情况：

• 一个点和它的两个子节点组成的三个点的路径和最大
• 一个点和它的儿子以及它的儿子的儿子组成的三个点的路径和最大

我们只需要遍历每个点，记录它的儿子中最大和次大的两个儿子，以及它儿子和它孙子的路径和，最后取最大值即可，如下图所示

🎃 代码

#include 
using namespace std;
#define int long long
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx;
int n, a[N];
int w[N];  //当前这个点到叶子节点的最长路径
int d1[N]; //当前这个点向下走的最长路径
int d2[N]; //当前这个点向下走的次长路径
int up[N]; //当前这个点向上早的最长路径
int p1[N]; //当前这个点的最长路径是从哪一个子节点下去的
int p2[N]; //当前这个点的次长路径是从哪一个子节点下去的
int ans;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs_d(int u, int fa)
{
    d1[u] = d2[u] = a[u];
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
        int d = dfs_d(j, u) + a[u];
        if (d >= d1[u]) //这里一定要大于等于
        {
            p2[u] = p1[u];
            d2[u] = d1[u];
            p1[u] = j;
            d1[u] = d;
        }
        else if (d > d2[u])
        {
            p2[u] = j;
            d2[u] = d;
        }
    }
    return d1[u];
}
void dfs_u(int u, int fa)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
        if (p1[u] == j)
            up[j] = max(up[u], d2[u]) + a[j];
        else
            up[j] = max(d1[u], up[u]) + a[j];
        dfs_u(j, u);
    }
}
int dfs(int u, int fa)
{
    int max1, max2, max3;
    max1 = max2 = max3 = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == fa)
            continue;
        if (w[j] >= max1)
        {
            max2 = max1;
            max1 = w[j];
        }
        else if (w[j] > max2)
        {
            max2 = w[j];
        }
        max3 = max(max3, dfs(j, u));
        ans = max(ans, w[u] + w[j] + max3);
    }
    ans = max(ans, (w[u] + max1 + max2));
    return max1;
}
signed main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    // 求d1、d2、p1、p2数组
    dfs_d(1, -1);
    // 这里一定要初始化1的up数组
    up[1] = a[1];
    // 求 up数组
    dfs_u(1, -1);
    // 求w数组
    for (int i = 1; i <= n; i++)
        w[i] = max(d1[i], up[i]);
    // 计算总价值
    dfs(1, -1);
    cout << ans;
    return 0;
}
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

I 旅行

⭐️ 题目

链接：https://ac.nowcoder.com/acm/contest/37782/I
来源：牛客网

🌃 思路：分层图求最短路

每一个城市都有两种状态，一种是要做核酸，一种是不做。如果上一个城市做了核酸，那么当前这个城市就不用做，如果上个城市没做，则我当前一定要做。所以每个城市都有可能做核酸或者没做核酸，而后直接跑最短路即可

😋 代码

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define int long long
#define x first
#define y second
typedef priority_queue<int, vector<int>, less<int>> Q;
typedef pair<ll, pair<int, int>> PII;
const int N = 1e6 + 10, M = 1e6 + 10;
ll h[N], e[M], w[M], ne[M], idx;
ll dist[N][2];
bool st[N][2];
int n, m, x;
int ans;
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, {1, 0}});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.y.x;
        int state = t.y.y;
        ll d = t.x;
        if (st[ver][state])
            continue;
        st[ver][state] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (state == 0)
            {
                if (dist[j][1] > dist[ver][0] + w[i] + x)
                {
                    dist[j][1] = dist[ver][0] + w[i] + x;
                    heap.push({dist[j][1], {j, 1}});
                }
            }
            else
            {
                if (dist[j][0] > dist[ver][1] + w[i])
                {
                    dist[j][0] = dist[ver][1] + w[i];
                    heap.push({dist[j][0], {j, 0}});
                }
            }
        }
    }
}

signed main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> x;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra();
    cout << min(dist[n][0],dist[n][1]);
    return 0;
}

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

J 神奇数字

⭐️ 题目

链接：https://ac.nowcoder.com/acm/contest/37782/J
来源：牛客网

🌃 思路：试除法求约数

要想让两个数同余，那么它俩的差一定是x的倍数，三个数同余，那就是两两之间的差的倍数。一个数是几个数的约数，那么它一定是这几个数最大公约数的约数。

所以我们只需要求出最大公约数，然后在求最大公约数的约数即可。

😋 代码

#include 
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, inf = 0x3f3f3f3f, mod = 998244353;
void solve()
{
    int a[3] = {0};
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if (a[0] == a[2])
    {
        puts("-1");
        return;
    }
    int x = __gcd((a[1] - a[0]), (a[2] - a[1]));
    vector<int> v;
    for (int i = 1; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            v.push_back(i);
            if (i != x / i)
            {
                v.push_back(x / i);
            }
        }
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        cout << v[i]<<" ";
    cout << endl;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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

💌 剩下的题慢慢补了，有任何疑问欢迎留言评论