Alexander's questions

最近我了解到，为了加快解决背包问题的速度，可以使用C++中的bitset结构来进行位压缩。有一个问题：有N 个物体，其权重为w。我们需要检查是否可以选择总重量等于Weight的一定数量的对象。看起来没什么困难，但问题在于限制：N <= 2500和Weight <= 6250000。不幸的是，我不太了解bitset在 C++ 中的工作原理，因此我无法实现具有此类限制的解决方案。我在网上找到了解决同样问题的方法，但我不明白为什么它不起作用：

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
 
int main() {
    int N, W;
    cin >> N >> W;
    vector<int> w(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i];
    }
    //vector<bool> A(W + 1);
    bitset<6250001> A;
    A[0] = true;
    for (int i = 1; i <= N; i++) {
        for (int j = W; j >= 0; j--) {
            if (j >= w[i - 1]) {
                A[j] = A[j] | (A[j] << w[i - 1]);
            }
        }
    }
    if (A[W]) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

如果有人已经做过类似的实现，请告诉我最适合我做什么。

我有个问题。给定一个数字数组 a，其中 (-10^9 <= ai <= 10^9)。对于这个数字数组，你需要找到数组中和最大的子段，取出这个和以及这样的子段的数量。我设法找到了最大金额（我附上了代码），但我不太明白如何快速找到金额。如果您有任何想法，我将非常感激。

 int n;
 cin >> n;
 vector<int> a(n);
 for (int i = 0; i < n; ++i) cin >> a[i];

 int ans = a[0], sum = 0;
 for (int r = 0; r < n; ++r) {
      sum += a[r];
      ans = max(ans, sum);
      sum = max(sum, 0);
 }
 cout << ans;

unordered_map<int, int> check;
int s[n + 1];
for (int i = 0; i < n; i++) {
      s[i + 1] = s[i] + a[i];
       if (check.find(s[i + 1]) != check.end()) {
           ++check[s[i + 1]];
       } else {
          check[s[i + 1]] = 1;
       }
}

有一个问题：有 n 个产品，以及 m 个优惠券，如果原始价格至少为 l 卢布，则第 i 个优惠券可以让您将一件商品的成本减少 d。我编写了一个解决方案，其中我对 的对数组进行排序di，之后我使用搜索箱来查找成本最低的产品，其价格至少为li卢布，然后我删除数组的这个元素并添加一个新的价格至 ans。显然问题出在删除上，但我不知道如何做到这一点，以便多个优惠券对同一产品无效。

第一行包含整数 n 和 m (1 ≤ n, m ≤ 2⋅10^5) — 商品和优惠券的数量。

第二行列出数字 c (1 ≤ ci ≤ 10^9) — 物品的成本。

第三行列出了数字 l (1 ≤ li ≤ 10^9) - 使用优惠券的商品的最低价格。

第四行列出数字d（1≤di≤li）——使用优惠券后的折扣。

#include <iostream>
#include <vector>
#include <algorithm>

#define len(a) ((int)((a).size()))

using namespace std;

bool cmp(const pair<int, int>& f, const pair<int, int>& s) {
     if (f.first != s.first)
          return f.first < s.first;
     return f.second > s.second;
}

int32_t main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);

     int n, m;
     cin >> n >> m;
     vector<int> c(n);
     vector<pair<int, int>> ld(m);
     for (int i = 0; i < n; ++i) cin >> c[i];
     for (int i = 0; i < m; ++i) cin >> ld[i].first;
     for (int i = 0; i < m; ++i) cin >> ld[i].second;

     stable_sort(ld.begin(), ld.end(), cmp);
     stable_sort(c.begin(), c.end());

     int i = 0, j = 0;
     while (i < n && j < m) {
          if (c[i] >= ld[j].first) {
               c[i] -= ld[j].second;
               ++j;
          }
          ++i;
     }

     long long ans = 0;
     for (auto& num : c) ans += num;
     cout << ans;

     return 0;
}

Входные данные:
10 5
9 7 1 5 2 2 5 5 7 6
7 2 7 8 2
3 2 4 1 2

Ответ:
37

有一个排列，还有q查询：求这个排列向左循环移位A个元素的反转次数。只有一个问题，排列大小是 3⋅10^5。我只能找到 n⋅log(n) 中的反转次数，但我不知道在移位时如何回答查询。如果您有任何想法，请写信，我将不胜感激！

我在大学里被布置了一个任务，我不知道如何解决它：给定一个长度为 n的数组，我们需要使用两个动作（将数组的最小元素加 1 或从最大元素减 1 )以便k 个不同的数字在所有操作后保留在数组中。即从数组-1；-5; 7; 8; 2; 1; 10，你需要得到-1；-1；7; 7; 7; 2; 1. 可能有人遇到过类似的东西，不然只能从思路上整理一下，不知道接下来怎么办...