本文共 3164 字，大约阅读时间需要 10 分钟。

0x01

解题思路

题目非常简单，我们知道只有奇数和偶数相加才会得到奇数，那么我们可以分别统计A和B中的奇偶个数，最后的结果就是min(A奇,B偶)+min(A偶,B奇)

n, m = list(map(int, input().split()))A = list(map(int, input().split()))B = list(map(int, input().split()))a1, a2, b1, b2 = 0, 0, 0, 0for i in A:    if i & 1:        a1 += 1    else:        a2 += 1for i in B:    if i & 1:        b1 += 1    else:        b2 += 1print(min(a1, b2) + min(a2, b1))

0x02

解题思路

我们可以将$a_i\ast (j-1)+b_i\ast (n-j)$进行因式分解，得到$(a_i-b_i)\ast j+(b_i\ast n-a_i)$，此时我们不难发现最后的得分结果由$(a_i-b_i)\ast j$决定，也就是我们需要其越小越好，而我们知道$j$是从小到大的数，那么我们只需要将$(a_i-b_i)$按照从大到小的顺序排序，那么最后二者乘积的和一定是最小的。

n = int(input())dif = []for _ in range(n):    data = list(map(int, input().split()))    dif.append([data[0] - data[1], data[0], data[1]])dif.sort(key=lambda x:-x[0])res = 0for k, v in enumerate(dif):    res += (k+1)*v[0] + v[2]*n - v[1]print(res)

0x03

解题思路

首先我们不难想到通过二分法解决这个问题。二分法的关键就是处理合法性问题，我们可以通过贪心的策略处理这个问题的合法性（给定时间x，最少多少人可以完成任务）。

我们知道，如果我们只有一个人的话，那么需要sum(A)+n的时间完成任务。所以我们可以遍历数组A计算前缀和cnt，如果cnt+i>=x（i表示遍历到的A中元素位置），说明此时人手不够了，我们需要增加人手。当我们增加一个人手后，我们相应的消耗时间就要减少x-i（其中x表示我们的目标时间，在位置i，每个人有x-i时间搬物品）。当最后所需人手个数小于m或者人手恰好是m且前缀合cnt小于等于0的时候，说明在x时间内可行，否则不可行。

接着就是二分法的常规套路，当我们发现当前的mid可行的时候，我们的r=mid，否则l=mid+1。

n, m = list(map(int,input().split()))A = list(map(int, input().split()))acc = sum(A)def check(x):    cnt, p = 0, 0    for i in range(1, n + 1):        cnt += A[i-1]        if i >= x:            return False        while i + cnt >= x:            cnt -= x - i            p += 1            if p > m:                return False    if p == m:        return cnt <= 0    return Trueif m > acc:    print(n + 1)else:    l, r = 2, n + acc    while l < r:        mid = l + r >> 1        if check(mid):            r = mid        else:            l = mid + 1    print(r)

0x04

解题思路

区间和的问题不难想到前缀和，最小值的问题不难想到单调栈，思路就非常清晰了。这个问题和非常类似。

我们需要维护一个严格的单调递增栈（通过这个栈我们可以得到区间的最小值，也就是栈顶元素），区间长度由栈顶和当前位置决定。具体步骤还是看Leetcode 84吧！

n = int(input())data = list(map(int, input().split()))data.append(0)res = 0s = []pre = [0]*len(data)for i in range(1, len(data)):    pre[i] += pre[i-1] + data[i-1]    for i, v in enumerate(data):    while s and v <= data[s[-1]]:        t = s.pop()        res = max(res, data[t]*(pre[i] - pre[s[-1] + 1 if s else 0]))    s.append(i)print(res)

0x05

解题思路

典型的动态规划问题，我们定义函数$f(i)$表示长度为$i$的时候合法方案数。那么

• $f(i)=f(i-1)+f(i-k)$

解释一下上面这个式子，$f(i)$的方案数只能来源于两种情况：一种是前面的白花不连续，一种是白花连续。

最后区间查询问题，显然就是通过前缀和来处理了。

#include 
   
    using namespace std;typedef long long LL;const int MAX = 1e5 + 5;const int MOD = 1e9 + 7;int a[MAX];LL dp[MAX], sum[MAX];int main(){
       int t, k;    scanf("%d %d", &t, &k);    for(int i = 0; i < k; i++) dp[i] = 1;    for(int i = k; i < MAX; i++) dp[i] = (dp[i - 1] % MOD + dp[i - k] % MOD) % MOD;        sum[1] = dp[1];    for(int i = 2; i < MAX; i++) sum[i] = (sum[i - 1] % MOD + dp[i] % MOD) % MOD;    while (t--)    {
           int a, b;        scanf("%d %d", &a, &b);        printf("%lld\n", (MOD + sum[b] - sum[a - 1]) % MOD);    }}
   

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/100355642 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！