2025-11-27 数据结构整理-(散装)

vector使用注意事项

1.向未初始化vector里添加元素需要用push_back,而不能用下标访问,想要用下标访问就要先初始化或resize
2.upper_bound(a,a+n,num)访问的是第一个比num大的位置,lower_bound访问的则是第一个大于等于num的位置
3.用下标访问时和数组一样前闭后开,注意begin() 和 end() 返回的是迭代器(iterator),这里end()访问的也是下一个位置
4.可以用a=b直接覆盖数组

快速转置稀疏矩阵

ppt上的原文(显然不想让我们看懂)

template <class Type>
SparseMatrix<Type> SparseMatrix<Type>::FastTranspos() {
    int *rowSize = new int[Cols];
    int *rowStart = new int[Cols];

    SparseMatrix<Type> b(Cols, Rows);
    b.Rows = Cols;
    b.Cols = Rows;
    b.Terms = Terms;

    if (Terms > 0) {
        // 初始化每列元素个数
        for (int i = 0; i < Cols; i++)
            rowSize[i] = 0;

        // 统计每列的非零元素数量
        for (int i = 0; i < Terms; i++)
            rowSize[smArray[i].col]++;

        // 计算每行的起始位置
        rowStart[0] = 0;
        for (int i = 1; i < Cols; i++)
            rowStart[i] = rowStart[i - 1] + rowSize[i - 1];

        // 将元素放到转置后的正确位置
        for (int i = 0; i < Terms; i++) {
            int j = rowStart[smArray[i].col];
            b.smArray[j].row = smArray[i].col;
            b.smArray[j].col = smArray[i].row;
            b.smArray[j].value = smArray[i].value;
            rowStart[smArray[i].col]++;
        }
    }

    delete[] rowSize;
    delete[] rowStart;

    return b;
}

说真的,他只要提一嘴用一个数组来存储矩阵中的所有非零元素就可以了,而ppt的原话是:

核心思想：事先统计好转置后各行非零元素在转置矩阵的三元组表中应存放的位置

hash表

模板:

int main(){
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        string k;
        cin>>k;
        int flag=1;
        for(int j=0;j<k.size();j++){
            a[i]=a[i]*mod1+k[j];
            b[i]=b[i]*mod2+k[j];
            //这里的mod1和mod2可以是某个大质数
        }
        for(int j=1;j<i;j++){
            if(a[i]==a[j]&&b[i]==b[j]) flag=0;
        }
        if(flag) sum++;
    }
    cout<<sum;
    return 0;
}

背包问题

参考链接

0-1背包

每个物品只取一次.

for(int i=1;i<=n;i++){
    for (int l = W; l >= w[i]; l--) 
        f[l] = max(f[l], f[l - w[i]] + v[i]);
    //每一次只考虑一个物品,逆向确保一个物品只考虑一次
}

完全背包

每个物品都能选无数次

for (int i = 1; i <= n; i++)
    for (int l = w[i]; l <= W; l++)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l -  w[i]] + v[i];
      //正向确保可以反复选同一个物品

多重背包

每个物品能选的次数有限
模板

for (int i = 1; i <= n; i++) {
  for (int weight = W; weight >= w[i]; weight--) {
    // 多遍历一层物品数量
    for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
      dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
      //看成01背包
    }
  }
}

进一步优化
二进制拆分

for (int i=1; i<=n; i++) {
        int k = 1;
        while (num[i] > 0) {
            int cnt = min(k, num[i]);
            int weight = cnt * w[i];
            int value  = cnt * v[i];

            // 0-1 背包更新
            for (int j=W; j>=weight; j--) {
                f[j] = max(f[j], f[j-weight] + value);
            }
            num[i] -= cnt;
            k *= 2;
        }
    }

单调队列

for (int i=1; i<=n; i++) {
       // 对每个余数 r = 0..wi-1
       for (int r=0; r<wi; r++) {
           deque<pair<int,int>> q; // pair<value, index m>
           for (int k=0, j=r; j<=W; k++, j+=wi) {
               int val = f[j] - k*vi;  // f[j - k*wi] - k*vi
               // 弹出不在窗口的队头
               while (!q.empty() && k - q.front().second > mi) q.pop_front();
               // 单调递减
               while (!q.empty() && q.back().first <= val) q.pop_back();
               q.push_back({val, k});
               f[j] = q.front().first + k*vi;
           }
       }
   }