首页 > 其他分享 >「笔记」可撤销背包

「笔记」可撤销背包

时间：2024-11-11 15:29:57浏览次数：3  
标签：std 背包 const int LL kN 撤销 cin 笔记

目录

写在前面

vp 24 harbin 时 E 前面的一切全都会了就是不会撤销背包，以为要上多项式科技于是跑路了，vp 快结束了跟坐牢计算几何的 dztlb 大神一说他说他会呃呃，完蛋。

引入

P4141 消失之物：

给定 \(n\) 个物品，第 \(i\) 个物品体积为 \(w_i\)。现在有一个容积为 \(m\) 的背包。
对于每一个物品 \(1\sim i\)，求删去该物品后使用剩余的物品，装满容积为 \(1\sim m\) 的背包的方案数，答案对 10 取模（即仅需输出十进制的末尾数字）。
\(1\le n, m\le 2000, 1\le w_i\le m\)。
1S，256MB。

分析

先考虑无删除，则有经典的状态 \(f_{i, j}\) 表示考虑到前 \(i\) 个物品，恰好装满容积为 \(j\) 的背包的方案数。初始化 \(f_{0, 0} = 1\)，则有显然的转移方程：

\[f_{i, j} = f_{i - 1, j} + f_{i - 1, j - w_i} \]

显然第一维可以通过滚动数组进行优化。

然后考虑如何通过上述状态得到撤销后的背包状态。发现上述背包计数的状态本质上是一个多项式，转移方程本质上就是每次对所有状态乘一个单项式。因此单次的可撤销背包本质上即每次对所有状态除一个单项式。对于物品 \(i\)，记 \(g_{j}\) 表示删除第 \(i\) 个物品后，恰好装满容积为 \(j\) 的背包的方案数，则有：

\[g_{j} = f_{j} - g_{j - w_i} \]

正确性显然，力大砖飞展开所有状态对应的多项式后，上式的结果与直接对删除物品后做背包的结果一致。从实际情况考虑，上式中 \(f_j\) 表示可能有物品 \(i\) 出现的方案的数量，而若某个包含物品 \(i\) 的方案在其中有贡献，则该方案中其他物品的容积之和一定为 \(j - w_i\)，即一定会对 \(g_{j} - w_i\) 有贡献。

总时间复杂度 \(O(nm)\) 级别。

代码

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2010;
//=============================================================
int n, m, w[kN];
LL f[kN], g[kN];
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++ i) std::cin >> w[i];
  f[0] = 1;
  for (int i = 1; i <= n; ++ i) {
    for (int j = m; j >= w[i]; -- j) {
      (f[j] += f[j - w[i]]) %= 10;
    }
  }

  for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= m; ++ j) g[j] = f[j];
    for (int j = w[i]; j <= m; ++ j) {
      g[j] = (f[j] % 10 - g[j - w[i]] + 10) % 10;
    }
    for (int j = 1; j <= m; ++ j) std::cout << g[j];
    std::cout << "\n";
  }
  return 0;
}

例题

AtCoder ABC321 F

水水板题，直接做即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5010;
const LL p = 998244353;
//=============================================================
int q, k;
LL f[kN];
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> q >> k;
  f[0] = 1;
  while (q --) {
    char opt; int x; std::cin >> opt >> x;
    if (opt == '+') {
      for (int i = k; i >= x; -- i) f[i] = (f[i] + f[i - x]) % p; 
    } else {
      for (int i = x; i <= k; ++ i) f[i] = (f[i] - f[i - x] + p) % p;
    }
    std::cout << f[k] << "\n";
  }
  return 0;
}

CF1111D

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 1e9 + 7;
//=============================================================
std::string s;
int n, q, cnt[53];
LL k, fac[kN], invfac[kN], f[kN], g[kN], ans[53][53];
//=============================================================
LL qpow(LL x_, LL y_) {
  LL ret = 1;
  while (y_) {
    if (y_ & 1) ret = ret * x_ % p;
    x_ = x_ * x_ % p, y_ >>= 1ll;
  }
  return ret;
}
int trans(char ch_) {
  return (int) ('A' <= ch_ && ch_ <= 'Z' ? ch_ - 'A' : ch_ - 'a' + 26);
}
void solve(int x_, int y_) {
  for (int i = 0; i <= n / 2; ++ i) g[i] = f[i];
  for (int i = cnt[x_]; i <= n / 2; ++ i) g[i] = (g[i] - g[i - cnt[x_]] + p) % p;
  for (int i = cnt[y_]; i <= n / 2; ++ i) g[i] = (g[i] - g[i - cnt[y_]] + p) % p;

  LL v = g[n / 2];
  if (cnt[x_] + cnt[y_] <= n / 2) v += g[n / 2 - cnt[x_] - cnt[y_]];
  ans[x_][y_] = ans[y_][x_] = k * v % p;
}
void init() {
  fac[0] = 1;
  for (int i = 1; i <= n; ++ i) fac[i] = fac[i - 1] * i % p;
  invfac[n] = qpow(fac[n], p - 2);
  for (int i = n - 1; i; -- i) invfac[i] = invfac[i + 1] * (i + 1) % p;

  for (auto ch: s) ++ cnt[trans(ch)];
  k = fac[n / 2] * fac[n / 2] % p;
  for (int i = 0; i < 52; ++ i) if (cnt[i]) k = k * invfac[cnt[i]] % p;

  f[0] = 1;
  for (int i = 0; i < 52; ++ i) {
    if (!cnt[i]) continue;
    for (int j = n / 2; j >= cnt[i]; -- j) {
      f[j] += f[j - cnt[i]], f[j] %= p;
    }
  }

  // std::cout << k << "\n";
  // for (int i = 0; i < 52; ++ i) std::cout << cnt[i] << " ";
  // std::cout << "\n";
  // for (int i = 0; i <= n / 2; ++ i) std::cout << "" << i << ": " << f[i] << "\n"; 

  for (int i = 0; i < 52; ++ i) {
    for (int j = i; j < 52; ++ j) {
      if (!cnt[i] || !cnt[j]) continue;
      if (i == j) {
        ans[i][j] = k * f[n / 2] % p;
        continue;
      }
      solve(i, j);
    }
  }
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> s; n = s.length();
  init();

  std::cin >> q;
  while (q --) {
    int x, y; std::cin >> x >> y;
    std::cout << ans[trans(s[x - 1])][trans(s[y - 1])] << "\n";
  }
  return 0;
}
/*
abba
2
1 4
1 2
*/

CCPC2024 Harbin E

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 510;
const LL p = 1e9 + 7;
const double eps = 1e-9;
//=============================================================
int n, m, x[kN], v[kN];
int cur[kN], cnt0, cnt1;
LL inv[kN], ans, invv[kN], prob[kN], prob1[kN], invprob1[kN], f[kN];
struct T {
  int u, id; 
  double t;
  bool operator < (const T sec_) const {
    return t < sec_.t;
  }
} t[kN * kN];
//=============================================================
LL qpow(LL x_, LL y_) {
  LL ret = 1;
  while (y_) {
    if (y_ & 1) ret = ret * x_ % p;
    x_ = x_ * x_ % p, y_ >>= 1ll;
  }
  return ret;
}
void init() {
  for (int i = 1; i <= n; ++ i) inv[i] = qpow(i, p - 2);
  for (int i = 1; i <= m; ++ i) cur[i] = n, prob[i] = 1, prob1[i] = 0, invprob1[i] = 0;
  cnt0 = 0, cnt1 = m, f[m] = 1;
}
void dp(T t_) {
  auto [u, id, tt] = t_;
  for (int j = 0; j <= m; ++ j) {
    if (cur[id] == n) {
      f[j] = f[j + 1];
    } else {
      if (j >= 1) f[j] = (f[j] - f[j - 1] * prob[id] % p + p) % p;
      f[j] = f[j] * invprob1[id] % p;
    }
  }

  bool flag = (cur[id] == n);
  while (cur[id] && 1.0 * x[cur[id]] / v[id] <= tt + eps) -- cur[id];
  prob[id] = cur[id] * inv[n] % p;
  prob1[id] = (n - cur[id]) * inv[n] % p;
  invprob1[id] = n * inv[n - cur[id]] % p;
  if (flag && cur[id] != n) -- cnt1;
  if (cur[id] == 0) ++ cnt0;

  if (cnt1 <= m / 2) {
    ans += 1ll * u * invv[id] % p * inv[n] % p * f[m / 2] % p;
    ans %= p;
  }
  
  for (int j = m; j >= 0; -- j) {
    LL temp = 0;
    temp = f[j] * prob1[id] % p;
    if (j >= 1) temp = (temp + f[j - 1] * prob[id] % p) % p;

    f[j] = temp;
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++ i) std::cin >> x[i], x[i] = -x[i];
  std::sort(x + 1, x + n + 1, std::greater<int>());
  for (int i = 1; i <= m; ++ i) std::cin >> v[i], invv[i] = qpow(v[i], p - 2);
  
  for (int i = 1; i <= m; ++ i) {
    for (int j = 1; j <= n; ++ j) {
      t[(i - 1) * n + j] = (T) {x[j], i, 1.0 * x[j] / v[i]};
    }
  }
  std::sort(t + 1, t + n * m + 1);

  init();
  for (int i = 1; i <= n * m; ++ i) {
    dp(t[i]);
    if (cnt0 > m / 2) break;
  }
  std::cout << ans << "\n";
  return 0;
}

写在最后

参考：

想休学了。

标签：std,背包,const,int,LL,kN,撤销,cin,笔记
From： https://www.cnblogs.com/luckyblock/p/18539827

相关文章

  • [豪の学习笔记] CI/CD相关 - Docker
    一、docker常见命令单独下载镜像文件dockerpull查看本地镜像文件dockerimages删除本地镜像文件dockerrmi基于dockerfile构建自定义镜像dockerbuild将打包好的镜像保存在本地dockersave加载外部镜像文件dockerload将本地镜像推送到镜像仓库dockerpush创建并......
  • Spring学习笔记_30——事务接口PlatformTransactionManager
    PlatformTransactionManager是Spring框架中事务管理的核心接口，它负责管理事务的创建、提交和回滚等操作。源码/**Copyright2002-2020theoriginalauthororauthors.**LicensedundertheApacheLicense,Version2.0(the"License");*youmaynotusethis......
  • [豪の学习笔记] Git的使用
    一、本地仓库1.1-工作流程1.2-本地仓库操作①全局配置：gitconfig--globaluser.name"用户名"gitconfig--globaluser.email"邮箱地址"②创建仓库：当需要让Git去管理某个项目时，就需要创建仓库。PS：创建仓库时使用的目录不一定要求是空目录，选择一个非空目录也可以......
  • MapStruct笔记
    依赖包<dependency><groupId>org.mapstruct</groupId><!--jdk8以下就使用mapstruct--><artifactId>mapstruct-jdk8</artifactId><version>1.2.0.Final</version></dependency><dependency>......
  • 【论文笔记】基于不完整数据的鲁棒多模态情感分析
    背景在现实世界的多模态情感检测中，由于存在大量的不完整的数据，影响了模型在判断情感时的准确性和鲁棒性，为了解决这一问题，本文提出了一个出了一种新颖的网络结构——Language-dominatedNoise-resistantLearningNetwork(LNLN)，旨在解决数据不完整性问题，在MSA中语言模态通常包......
  • 点云学习笔记14——PCL点云文件投影到平面
    #include<iostream>#include<pcl/io/pcd_io.h>#include<pcl/point_types.h>#include<pcl/ModelCoefficients.h>#include<pcl/filters/project_inliers.h>#include<pcl/visualization/pcl_visualizer.h>#include<boost/th......
  • Mit6.S081笔记：知识点记录
    课程地址翻译程序到汇编的转换​ 任何一个处理器都有一个关联的ISA（InstructionSetsArchitecture，指令集架构），ISA就是处理器能够理解的指令集。每一条指令都有一个对应的二进制编码或者一个Opcode。当处理器在运行时，如果看见了这些编码，那么处理器就知道该做什么样的操作。​ 写......
  • 《Django 5 By Example》阅读笔记：p1-p16
    《Django5ByExample》学习第1天，p1-p16总结，总计16页。一、技术总结1.Django基本操作(1)创建project&创建appdjango-adminstartprojectmysitedjango-adminstartappblog(2)定义model(3)启动项目pythonmanage.pyrunserver二、英语总结(生词：8)1.fintechabbr......
  • 《程序员修炼之道：从小工到专家》阅读笔记5---交流的重要性
    在阅读《程序员修炼之道：从小工到专家》的过程中，我深刻体会到了交流在软件开发中的重要性。交流是软件开发过程中不可或缺的环节。无论是与团队成员之间的沟通，还是与用户的交流，都直接影响着项目的成功与否。良好的交流可以帮助我们更好地理解用户的需求，避免不必要的误解和返工。同......
  • 背包九讲——背包问题求方案数
    目录背包问题求方案数1.01背包问题题目链接：11.背包问题求方案数-AcWing题库算法实现：代码实现：问题变形： 解决方法：2.多重背包问题3.完全背包问题背包问题第八讲——背包问题求方案数背包问题是一类经典的组合优化问题，通常涉及在限定容量的背包中选择物品，以最......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99