摘要
Title: Acwing 第 45 场周赛
Tag: 贪心、双指针

Acwing 第 45 场周赛

A AcWing 4393. 字符串价值

思路

哈希表记录即可

代码

from collections import Counter

a = list(map(int, input().split()))
a = [0, *a]
s = input()
d = Counter(s)
ans = 0

for key in sorted(d.keys()):
    ans += a[int(key)] * d[key]

print(ans)

B AcWing 4394. 最长连续子序列

题意

给定一个长度为 n 的整数序列 a1,a2,…,an。
请你找出它的一个最长连续子序列，要求该子序列包含不超过 k 个不同的值。
思路

看到连续子序列，一般可以用双指针
i为右指针，j为左指针，每次找最远的且符合条件的j

代码

'''
Author: NEFU AB-IN
Date: 2022-04-02 18:57:37
FilePath: \ACM\Acwing\45\b.py
LastEditTime: 2022-04-02 19:21:55
'''
N = int(1e6 + 10)
st = [0] * N

n, k = map(int, input().split())
a = list(map(int, input().split()))

j = 0
cnt, ans = 0, 0
l, r = 0, 0
for i in range(n):
    if st[a[i]] == 0:
        cnt += 1
    st[a[i]] += 1
    while j < i and cnt > k:
        st[a[j]] -= 1
        if st[a[j]] == 0: cnt -= 1
        j += 1
    if i - j + 1 > ans:
        ans = i - j + 1
        l, r = j + 1, i + 1

print(l, r)

C AcWing 4395. 最大子矩阵

题意

给定数组a和b，计算由a×b数组组成的矩阵中，子矩阵的元素和在不超过x的情况下面积最大
思路

首先我们可以将题目所求的子矩阵元素和转换为求a b数组的一段子区间和的乘积
如：
a1 * b1 + a2 * b1 + a3 * b1
a1 * b2 + a2 * b2 + a3 * b2 =>=> (a1 + a2 + a3) * (b1 + b2 + b3)
a1 * b3 + a2 * b3 + a3 * b3

我们要使区间长度的乘积最大，那么相同长度的区间其区间和肯定是越小越好，然后枚举所有可能的区间长度的选法
区间和可以用前缀和实现
记录a b数组长度为1~(n or m)的最小区间和
然后暴力枚举a的区间长度和b的区间长度进行判断比较即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-04-02 19:59:19
* @FilePath: \ACM\Acwing\45\c.cpp
* @LastEditTime: 2022-04-02 20:15:12
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int N = 2020;
int a[N], b[N], lena[N], lenb[N];

signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    memset(lena, 0x3f, sizeof lena);
    memset(lenb, 0x3f, sizeof lenb);
    //计算a b数组的前缀和
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1];
    for (int i = 1; i <= m; i++)
        cin >> b[i], b[i] += b[i - 1];
    //记录a b数组长度为len时的最小区间和
    for (int len = 1; len <= n; len++)
    {
        for (int l = 1; l <= n - len + 1; l++)
        {
            int r = l + len - 1;
            lena[len] = min(lena[len], a[r] - a[l - 1]);
        }
    }
    for (int len = 1; len <= m; len++)
    {
        for (int l = 1; l <= m - len + 1; l++)
        {
            int r = l + len - 1;
            lenb[len] = min(lenb[len], b[r] - b[l - 1]);
        }
    }
    int x;
    cin >> x;
    int ans = 0;
    //暴力枚举元素和小于x时的最大数量
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (lena[i] * lenb[j] <= x)
                ans = max(ans, i * j);
        }
    cout << ans << '\n';
}

Acwing 第 45 场周赛

A AcWing 4393. 字符串价值

思路

代码

B AcWing 4394. 最长连续子序列

题意

思路

代码

C AcWing 4395. 最大子矩阵

题意

思路

代码