C++笔试强训day42

目录

1.最大差值

2.兑换零钱

3.小红的子串

1.最大差值

链接https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId=182&tqId=34396&rp=1&ru=/exam/company&qru=/exam/company&sourceUrl=%2Fexam%2Fcompany&difficulty=2&judgeStatus=undefined&tags=&title=

因为b >= a，所以可以在遍历数组的时候更新所遍历到的最小值以及返回值即可

class Solution {
  public:
    int getDis(vector<int>& A, int n) {
        int ret = -0x3f3f3f3f;
        int l = 0, r = l + 1;
        while (r < n) {
            ret = max(A[r] - A[l], ret);
            if (A[r] < A[l]) {
                l = r;
            }
            r++;
        }
        return ret < 0 ? 0 : ret;
    }
};

2.兑换零钱

链接https://www.nowcoder.com/practice/67b93e5d5b85442eb950b89c8b77bc72?tpId=230&tqId=40432&ru=/exam/oj

每个值代表一种面值的货币，每种面值的货币可以使用任意张

根据题意，可以分析出这是一道完全背包类型的题目：

直接分析状态转移方程和注意初始化的细节即可

#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010;

int w[N];
int dp[5010];
int n, aim;
int main()
{
    cin >> n >> aim;
    for(int i = 1; i <= n; ++i)
        cin >> w[i];

    memset(dp, 0x3f3f3f3f, sizeof dp);
    dp[0] = 0;

    for(int i = 1; i <= n; ++i)
    {
        for(int j = w[i]; j <= aim; ++j)
        {
            dp[j] = min(dp[j], dp[j - w[i]] + 1);
        }
    }
    cout << (dp[aim] == 0x3f3f3f3f ? -1 : dp[aim]) << endl;
    return 0;
}

3.小红的子串

链接https://ac.nowcoder.com/acm/problem/260770

若种类的范围为 【1，x】的话，则满足条件的数组区间内方案数则为 right - left + 1，因此可以将种类范围想办法变为【1，x】，最后用【1，r】 - 【1，l】即可

滑动窗口遍历数组：（数据范围过大，注意开long long）

#include <iostream>
#include <cstring>
#define int long long
using namespace std;

int n, l, r;
char s[200010];

int find(int x)
{
    if(x == 0)
        return 0;
    
    int cnt[26] = { 0 };
    int kind = 0, ret = 0;
    int L = 1, R = 1;
    while(R <= n)
    {
        if(cnt[s[R] - 'a']++ == 0)
            kind++;
            
        while(kind > x)
        {
            if(cnt[s[L++] - 'a']-- == 1)
                kind--;
        }

        ret += R - L + 1;
        R++;
    }
    return ret;
}

signed main()
{
    cin >> n >> l >> r;
    for(int i = 1; i <= n; ++i)
        cin >> s[i];
    
    cout << find(r) - find(l - 1) << endl;
    return 0;
}