vp1076Div3-①B-贪心②C-贪心+前缀和③D-二分④E-完全背包DP#

Dashboard - Codeforces Round 1076 (Div. 3) - Codeforces

https://www.wolai.com/o1jB8e6zHTkLvyJuC8cxPR

B-贪心#

题目#

长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，这些整数从 $1$ 到 $n$ 按任意顺序排列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 和 $[1,3,4]$ 不是排列。

给你一个长度为 $n$ 的排列组合 $p$ 。你可以执行下面的操作1次：

选择两个整数 $l,$ $r$ ( $1\le l\le r\le n$ ).
将排列 $p$ 中的线段 $[l, r]$ 倒转。

您的任务是输出通过执行此操作可以得到的字典序最大的排列。

贪心#

对于位置i的元素p[i],若p[i]==n-i，则当前元素不需要进行交换；

找到第一个不满足上述条件的位置i，该位置应对应的值为n - i，在p中找到改值对应的位置idx，翻转[i,idx]即可得到字典序最大的排列。

1
for _ in range(int(input())):
2
    n = int(input())
3
    p = list(map(int, input().split()))
4
    i = 0
5
    while i < n and p[i] == n - i:
6
        i+=1
7
    if i == n:
8
        print(*p)
9
    else:
10
        t = n - i
11
        idx = p.index(t)
12
        ans = p[:i] + p[i:idx+1][::-1] + p[idx+1:]
13
        print(*ans)

C-贪心+前缀和#

题目#

给定两个数组a和b，可以执行如下操作任意次：

1.对于位置 $i(1≤i<n)$ ，替换 $a_i$ 和 $a_{i+1}$

2.对于位置 $i(1≤i≤n)$ ，替换 $a_i$ 和 $b_i$

有 $q$ 次查询，每个查询需要返回最大的 $a[l,r]$ 的值

贪心+前缀和#

对于操作1无法让后面的值赋值到前面的，故从后往前遍历，记录过程中两个数组中各自的最大值，此位置的最大值即为这两个值中的最大值；

对于每个查询，用前缀和加速计算

1
for _ in range(int(input())):
2
    n, q = map(int, input().split())
3
    a = list(map(int, input().split()))
4
    b = list(map(int, input().split()))
5
    val = [0]*n
6
    max_a = max_b = 0
7
    for i in range(n-1,-1,-1):
8
        max_a = max(max_a,a[i])
9
        max_b = max(max_b,b[i])
10
        val[i] = max(max_a,max_b)
11
    pre = [0]*(n+1)
12
    for i in range(1,n+1):
13
        pre[i] = pre[i-1] + val[i-1]
14
    ans = []
15
    for _ in range(q):
16
        l,r = map(int,input().split())
17
        ans.append(pre[r] - pre[l-1])
18
    print(*ans)

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
signed main(){
5
    int t;
6
    cin >> t;
7
    while(t--){
8
        int n,q;
9
        cin >> n >> q;
10
        vector<int>a(n),b(n);
11
        for(int i = 0;i < n;i++) cin>>a[i];
12
        for(int i = 0;i < n;i++) cin>>b[i];
13
        vector<int> val(n);
14
        int max_a = 0,max_b = 0;
15
        for(int i = n - 1;i >= 0;i--){
16
            max_a = max(max_a,a[i]);
17
            max_b = max(max_b,b[i]);
18
            val[i] = max(max_a,max_b);
19
        }
20
        vector<long long> pre(n + 1,0);
21
        for(int i = 1;i <= n;i++){
22
            pre[i] = pre[i-1] + val[i-1];
23
        }
24
        while(q--){
25
            int l,r;
26
            cin >> l >> r;
27
            cout << pre[r] - pre[l-1] << " ";
28
        }
29
        cout << endl;
30
    }
31
    return 0;
32
}

D-二分#

题目#

有 n 把剑，每把剑有强度 a[i]
有 n 个关卡，每个关卡怪物需要 b[i] 次剑击才能打败
剑的规则：每把剑只能攻击一次就会折断
难度选择：选择 x 后，强度 < x 的剑不能使用

二分#

选择难度 x 后：

可用的剑：强度 ≥ x 的剑，数量为 cnt
这些剑总共只能攻击 cnt 次（每把剑一次）
要完成前 k 个关卡，需要 sum(b[0:k]) 次攻击
所以须满足：sum(b[0:k]) ≤ cnt

得分 = x × k，其中 k 是能完成的最大关卡数。

通过前缀和+二分快速查找每个x对应的最大k

1
import bisect
2
for _ in range(int(input())):
3
    n = int(input())
4
    a = list(map(int,input().split()))
5
    b = list(map(int,input().split()))
6
    ans = 0
7
    a.sort()
8
    pre = [0]*(n+1)
9
    for i in range(1,n+1):
10
        pre[i] = pre[i-1] + b[i-1]
11
    p = 0
12
    for i,x in enumerate(a):
13
        if x != p:
14
            p = x
15
            cnt = n - i
16
            k = bisect.bisect_right(pre,cnt) - 1
17
            if x * k > ans:
18
                ans = x * k
19
    print(ans)

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    int t;
5
    cin >> t;
6
    while(t--){
7
        int n;
8
        cin >> n;
9
        vector<int> a(n);
10
        vector<int> b(n);
11
        for(int i = 0;i < n;i++) cin >> a[i];
12
        for(int i = 0;i < n;i++) cin >> b[i];
13
        vector<long long> pre(n+1,0);
14
        for(int i = 1;i <= n;i++){
15
            pre[i] = pre[i-1] + b[i-1];
16
        }
17
        sort(a.begin(),a.end());
18
        long long ans = 0;
19
        for(int i = 0;i < n;i++){
20
            if(i > 0 && a[i] == a[i-1]) continue;
21
            int x = a[i];
22
            int cnt = n - i;
23
            int k = upper_bound(pre.begin(),pre.end(),(long long)cnt) - pre.begin() - 1;
24
            long long s = (long long)x*k;
25
            if(s > ans) ans = s;
26
        }
27
        cout << ans << endl;
28
    }
29
    return 0;
30
}

E-完全背包DP#

题目#

给定一个长度为 n 的数组 a
对于每个 i (1 ≤ i ≤ n)，问能否从数组 a 中选择若干个元素（可以重复选择同一个元素），使得它们的乘积恰好等于 i
要求选择的元素数量最少，如果不可能则输出 -1
注意：必须至少选择一个元素

完全DP#

初始化：dp[1..n] = INF 表示得到乘积 i 所需的最少元素个数

设置基础值：对于数组 a 中的每个元素 x（x ≤ n），dp[x] = 1（选择这一个元素即可）

DP 转移：对于每个 i 从 1 到 n，遍历 j = i, 2i, 3i, … ≤ n

dp[j] = min(dp[j], dp[i] + dp[j/i])

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = list(map(int,input().split()))
4
    INF = 10**9
5
    dp = [INF]*(n + 1)
6
    for x in a:
7
        if x <= n:
8
            dp[x] = 1
9
    for i in range(1,n+1):
10
        if dp[i] == INF:
11
            continue
12
        for j in range(i,n+1,i):
13
            if dp[j//i] != INF:
14
                dp[j] = min(dp[j],dp[i] + dp[j//i])
15
    ans = []
16
    for i in range(1,n+1):
17
        if dp[i] == INF:
18
            ans.append(-1)
19
        else:
20
            ans.append(dp[i])
21
    print(*ans)

音乐

音乐

vp1076Div3-①B-贪心②C-贪心+前缀和③D-二分④E-完全背包DP#

B-贪心#

题目#

贪心#

C-贪心+前缀和#

题目#

贪心+前缀和#

D-二分#

题目#

二分#

E-完全背包DP#

题目#

完全DP#

文章分享

音乐

目录

音乐

音乐

[算法训练] vp1076Div3-①B-贪心②C-贪心+前缀和③D-二分④E-完全背包DP

vp1076Div3-①B-贪心②C-贪心+前缀和③D-二分④E-完全背包DP#

B-贪心#

题目#

贪心#

C-贪心+前缀和#

题目#

贪心+前缀和#

D-二分#

题目#

二分#

E-完全背包DP#

题目#

完全DP#

文章分享

音乐

目录