[CF] E. Kevin and And - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)

Solutions Codeforces 贪心状态压缩dp 凸性 Hard-

Lastmod: 2025-02-02 周日 01:12:19

https://codeforces.com/contest/2061/problem/E

题目大意

给出 $n \ (1 \le n \le 10^5)$ 长的数组 $a$ 和 $m \ (1 \le m \le 10)$ 长的数组 $b$。满足 $0 \le a_i, b_i < 2^{30}$。

可以执行以下操作 $k \ (0 \le k \le nm)$ 次：

选取 $a_i$ 和 $b_j$ 将 $a_i$ 变为 $a_i \ \text{&} \ b_j$。

问执行完这些操作最小的数组和是多少。

题解

我们可以求出每个数 $a_i$ 上执行 $j$ 次操作的最小结果。显然这个结果是单调不增的。易证：我们总可以在选 $j$ 个基础上任意选一个没选过的，由于与的性质，这个结果一定不会增大。所以最优解一定小于等于这个特殊解。

特别注意：第在 $a_i$ 上进行 $j + 1$ 次操作的最好结果不一定是 $j$ 次操作最好结果的基础上再进行某一次！例如 $a_i = 1111_{2}$，如果 $b = {0101_2, 1001_2, 0110_2}$，则选取 $1$ 个的时候是选第一个最优，而 $2$ 个的时候是后两个。因此这个步骤，必须枚举 $b_i$ 的全部可能组合。

引理

我们可以求出每多用一步的差量。这里更重要的性质是，对于每个 $a_i$ 这个差量也是单调不增的。

证明

设 $f(S)$ 表示 $a_i$ 与上 $S$ 集合之中所有数的结果。

$g(j)$ 为执行 $j$ 步的后 $a_i$ 的最小结果，这里相当于要证明 $g(j)$ 是下凸的，即 $2g(i) \le g(i - 1) + g(i + 1)$。

设 $S$ 为 $i - 1$ 次操作最好的集合，$T$ 为 $i + 1$ 次操作最好的集合。$g(i - 1)$ 与 $g(i + 1)$ 最高的不同的位为第 $w$ 位（所有位都一样的情况，由于上述证明，我们知道等号成立）。则我们可以得出我们总能找到一个 $y \in T \setminus S$，使得我们可以通过 $y$ 把 $g(i - 1)$ 的 $i$ 位变为 $0$。即

$$ g(i - 1) - f(S \cup \{y\}) \ge 2^w. $$

另一边，由于 $f(S \cup {y})$ 的 $w$ 位与 $g(i + 1)$ 的 $w$ 位都为 $0$，则

$$ f(S \cup \{y\}) - g(i + 1) < 2^w. $$

综上可以得到

$$ 2g(i) \le 2f(S \cup \{y\}) \le g(i - 1) + g(i + 1). $$

得证。

有了这个性质，我们按照从大到小的顺序贪心的选就可以了。

（比赛中没有完全想清楚，写了 $n$ 路归并，但其实这里是没必要的。直接排序甚至 $std::nth_element$ 即可。）

const int INF = (1 << 30) + 1;
const int MN = 1e5 + 5;
const int MM = 10;
int diff[MN][MM];

int m;
struct Node {
  int d, id, cur;
  bool operator<(const Node& B) const {
    if (d != B.d) return d < B.d;
    for (int i = cur, j = B.cur; i < m && j < m; i++, j++) {
      if (diff[id][i] != diff[B.id][j]) return diff[id][i] < diff[B.id][j];
    }
    return cur > B.cur;
  }
};

void solve() {
  int n, k; cin >> n >> m >> k;
  vector<int> a(n);
  vector<int> b(m);
  for (int& i : a) cin >> i;
  for (int& i : b) cin >> i;

  LL ans = 0;
  for (int i : a) ans += i;

  int msk = 1 << m;

  vector<int> bb(msk, (1 << 30) - 1);
  for (int i = 1; i < msk; i++) {
    for (int j = 0; j < m; j++) {
      if (i & (1 << j)) bb[i] &= b[j];
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      diff[i][j] = INF;
    }
    for (int j = 1; j < msk; j++) {
      cmin(diff[i][__builtin_popcount(j) - 1], a[i] & bb[j]);
    }    
    for (int j = m - 1; j > 0; j--) {
      diff[i][j] = diff[i][j - 1] - diff[i][j];
    }
    diff[i][0] = a[i] - diff[i][0];
  }

  priority_queue<Node> qu;

  for (int i = 0; i < n; i++) {
    qu.push({diff[i][0], i, 0});
  }

  for (int i = 0; i < k; i++) {
    auto [d, id, cur] = qu.top(); qu.pop();
    if (!d) break;
    ans -= d;
    cur++;
    if (cur < m) {
      qu.push({diff[id][cur], id, cur});
    }
  }

  cout << ans << '\n';
}

复杂度

$T$：$O(n 2^m + nm)$

$S$：$O(n + m)$

代码实现

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

const int INF = (1 << 30) + 1;

void solve() {
  int n, m, k; cin >> n >> m >> k;
  vector<int> a(n);
  vector<int> b(m);
  for (int& i : a) cin >> i;
  for (int& i : b) cin >> i;

  LL ans = 0;
  for (int i : a) ans += i;

  int msk = 1 << m;

  vector<int> bb(msk, (1 << 30) - 1);
  for (int i = 1; i < msk; i++) {
    for (int j = 0; j < m; j++) {
      if (i & (1 << j)) bb[i] &= b[j];
    }
  }

  vector<int> f(m);

  vector<int> diff;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      f[j] = INF;
    }
    for (int j = 1; j < msk; j++) {
      cmin(f[__builtin_popcount(j) - 1], a[i] & bb[j]);
    }    
    for (int j = m - 1; j > 0; j--) {
      diff.push_back(f[j - 1] - f[j]);
    }
    diff.push_back(a[i] - f[0]);
  }

  nth_element(diff.begin(), diff.begin() + (n * m - k), diff.end());

  for (int i = 0; i < k; i++) {
    ans -= diff[n * m - i - 1];
  }

  cout << ans << '\n';
}

int main() {
  int t = 1; 
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

对拍

一组小数据

1
4 6 4
20 27 23 4
7 22 31 14 22 13

对拍程序

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename Func> struct YCombinatorResult {
  Func func;
  template<typename T>
  explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
  template<class ...Args> decltype(auto) operator()(Args &&...args) {
    return func(std::ref(*this), std::forward<Args>(args)...);
  }
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
  return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

const int INF = 0x3f3f3f3f;

void solve() {
  int n, m, k; cin >> n >> m >> k;
  vector<int> a(n);
  vector<int> b(m);
  for (int& i : a) cin >> i;
  for (int& i : b) cin >> i;

  vector<int> curi(k), curj(k);
  vector<int> ansi, ansj;
  int mn = INF;

  LL ans = y_comb([&](auto dfs, int cur) -> LL {
    if (cur == k) {
      LL ans = 0;
      // for (int i : a) cerr << i << ' ';
      // cerr << endl;
      for (int i : a) ans += i;
      if (ans < mn) {
        mn = ans;
        ansi = curi;
        ansj = curj;
      }
      return ans;
    }
    LL ans = INF;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) { 
        curi[cur] = i;
        curj[cur] = j;
        int t = a[i];
        a[i] &= b[j];
        cmin(ans, dfs(cur + 1));
        a[i] = t;
      }
    }
    return ans;
  })(0);

  for (int i : ansi) cerr << i << ' ';
  cerr << '\n';
  for (int i : ansj) cerr << i << ' ';
  cerr << '\n';

  cout << ans << '\n';
}

int main() {
  int t = 1; 
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

数据生成

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

inline int rndi() { return rnd(); }
inline int rndi(int n) { return rnd()%n; }
inline int rndi(int l, int r) { return rnd() % (r - l + 1) + l; }
inline LL rndll() { return rnd_64(); }
inline LL rndll(LL n) { return rnd_64() % n; }
inline LL rndll(LL l, LL r) { return rnd_64() % (r - l + 1) + l; }
inline char rndc() { return rnd() % 26 + 'a'; }
inline char rndC() { return rnd() % 26 + 'A'; }
inline char rnddig() { return rnd() % 10 + '0'; }
inline char rndcha() { 
  int v = rnd() % 52;
  return v < 26 ? v + 'a' : (v - 26 + 'A');
}

template<typename T>
void shuffle(vector<T>& vec) { shuffle(vec.begin(), vec.end(), rnd); }

vector<int> rnd_permu(int n, int from = 0) {
  vector<int> vec(n);
  iota(vec.begin(), vec.end(), from);
  shuffle(vec);
  return vec;
}

void solve() {
  int n = rndi(1, 5), m = rndi(1, 6), k = rndi(0, min(n * m, 5));
  cout << n << ' ' << m << ' ' << k << '\n';
  for (int i = 0; i < n; i++) {
    cout << rndi(0, (1 << 5)) << ' ';
  }
  cout << '\n';

  for (int i = 0; i < m; i++) {
    cout << rndi(0, (1 << 5)) << ' ';
  }
  cout << '\n';
}

int main() {
  int t = 10; cout << t << '\n';
  while (t--) {
    solve();
  }
  return 0;
}

Prev: [CF] D. Kevin and Numbers - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
Next: [CF] D. Game With Triangles - Codeforces Round 1000 (Div. 2)