CF525E. Anya and Cubes

发表于 分类于 阅读次数： Waline： 本文字数： 721 阅读时长 ≈ 2 分钟

考点

  • 双向DFS

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;
ll N, K, S, ans, a[maxn], v[maxn], p[maxn];

// 打表判断每个位置上的数字阶乘对于S是否有效
ll pd(ll x) {
  ll fact = 1;
  while (x) {
    if (fact * x > S) return -1;
    fact *= x--;
  }
  return fact;
}

map<pair<int, ll>, int> f;
void check1() {
  ll cnt = 0, sum = 0;
  for (int i = 1; i <= N / 2; ++i) {
    if (v[i] == 1)
      sum += a[i];
    else if (v[i] == 2) {
      ll s = p[i];
      if ((s == -1) || ((s + sum) > S)) return;
      ++cnt;
      sum += s;
    }
  }
  ++f[{cnt, sum}];
  // 由于同一个sum会有很多种cnt，单独开一个(-1,sum)确认sum是否存在
  ++f[{-1, sum}];
}

// 左半边递归
void dfs1(int x, ll k) {
  if (x > N / 2)
    check1();
  else {
    for (int i = 0; i <= 2; ++i) {
      if (i == 0 || i == 1) {
        v[x] = i;
        dfs1(x + 1, k);
      } else if (i == 2 && k) {
        // 可行性剪枝：只有k大于0的时候才能选阶乘
        v[x] = i;
        dfs1(x + 1, k - 1);
      }
    }
  }
}

// 记忆化搜索优化
map<pair<int, ll>, ll> g;
ll query(int x, ll s) {
  if (g.count({x, s})) return g[{x, s}];
  return g[{x, s}] = f[{x, s}] + (x ? query(x - 1, s) : 0);
}

void check2() {
  ll cnt = 0, sum = 0;
  for (int i = N / 2 + 1; i <= N; ++i) {
    if (v[i] == 1)
      sum += a[i];
    else if (v[i] == 2) {
      ll s = p[i];
      if ((s == -1) || ((sum + s) > S)) return;
      ++cnt;
      sum += s;
    }
  }
  if (f.count({-1, S - sum})) ans += query(K - cnt, S - sum);
}

// 右半边递归
void dfs2(int x, ll k) {
  if (x > N)
    check2();
  else {
    for (int i = 0; i <= 2; ++i) {
      if (i == 0 || i == 1) {
        v[x] = i;
        dfs2(x + 1, k);
      } else if (i == 2 && k) {
        v[x] = i;
        dfs2(x + 1, k - 1);
      }
    }
  }
}

int main() {
  cin >> N >> K >> S;
  for (int i = 1; i <= N; ++i) cin >> a[i], p[i] = pd(a[i]);
  dfs1(1, K), dfs2(N / 2 + 1, K);
  cout << ans << endl;
  return 0;
}

思路

每个位置上的元素有三种状态，不选、选但不加阶乘，选且阶乘，总复杂度高达\(O\left( 3^{25} \right)\)，考虑双向DFS，可降到$ O( 3^{12} )$

每个状态是一个二元组，(阶乘个数，总和)

所以用一个红黑树来记录左半部分每个状态的出现次数map<pair<int, ll>, int> f

左右部分各自求出总和在S以内，阶乘个数在K以内的所有状态后，

假设当前右部分状态为(阶乘个数cnt, 总和sum, 出现次数a)，去寻找左半部分的所有状态f中，满足阶乘个数小于等于K - cnt, 总和等于S - sum的方案总数，累计起来就是答案。

有两个重要优化点：

  • 由于K并没要求一定要用完，那么需要找K - 1，K - 2一直到0为止的所有可能性

    所以采用记忆化搜索来优化：

    1
    2
    3
    4
    5
    6
    // 记忆化搜索优化
    map<pair<int, ll>, ll> g;
    ll query(int x, ll s) {
      if (g.count({x, s})) return g[{x, s}];
      return g[{x, s}] = f[{x, s}] + (x ? query(x - 1, s) : 0);
    }

  • 因为S最大只有1e7，可以提前打表每个位置上的数字的阶乘，如果大于1e7就没必要使用