黑魔法

创建多维 vector

需要 C++14 及以上

不可初始化值的版本：

template <typename T>
std::vector<T> create_nd_vector(size_t size) {
  return std::vector<T>(size);
}

template <typename T, typename... Sizes>
auto create_nd_vector(size_t first, Sizes... sizes) {
  return std::vector<decltype(create_nd_vector<T>(sizes...))>(
    first, create_nd_vector<T>(sizes...));
}

void solve() {
  int n;
  cin >> n;
  vector<string> a(n + 1);
  auto b = create_nd_vector<int>(n + 1, n + 1, n + 1, n + 1);
  cout << typeid(b).name() << endl;
}

带初始化值的版本，初始化值必须为第一个参数：

template <typename T>
std::vector<T> create_nd_vector(T value, size_t size) {
  return std::vector<T>(size);
}

template <typename T, typename... Sizes>
auto create_nd_vector(T value, size_t first, Sizes... sizes) {
  return std::vector<decltype(create_nd_vector<T>(value, sizes...))>(
    first, create_nd_vector<T>(value, sizes...));
}

void solve() {
  int n;
  cin >> n;
  vector<string> a(n + 1);
  auto b = create_nd_vector<int>(n + 1, n + 1, n + 1, n + 1);
  cout << typeid(b).name() << endl;
}

“动态”的 std::bitset

需要 C++14 及以上

来自 CF1856E2， 利用模板展开预定义大小为 $2^k$ 的函数。

// bitset 优化可行性 01 背包（重量和价值相等的 01 背包）
template <int len = 1>
int knapsack01(const vector<int> &a, int target) {
  if (target >= len) {
    return knapsack01<min(len * 2, MAX_BITSET_SIZE)>(a, target);
  }
  bitset<len> dp;
  dp[0] = 1;
  for (auto x : a) {
    dp |= dp << x;
  }
  for (int i = target; i >= 0; --i) {
    if (dp[i]) {
      return i;
    }
  }
  return 0;
}