P4799. 世界冰球锦标赛

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

考点

  • 双向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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5e7 + 50;
ll n, m, alen, blen, a[maxn], b[maxn], in[100];

void dfs1(ll idx, ll sum) {
  if (idx > n / 2) {
    a[++alen] = sum;
    return;
  }
  for (ll i = 0; i < 2; ++i) {
    if (sum + i * in[idx] > m) break;
    dfs1(idx + 1, sum + i * in[idx]);
  }
}

void dfs2(ll idx, ll sum) {
  if (idx > n) {
    b[++blen] = sum;
    return;
  }
  for (ll i = 0; i < 2; ++i) {
    if (sum + i * in[idx] > m) break;
    dfs2(idx + 1, sum + i * in[idx]);
  }
}

int main() {
  cin >> n >> m;
  for (ll i = 1; i <= n; ++i) cin >> in[i];
  dfs1(1, 0), dfs2(n / 2 + 1, 0);
  sort(a + 1, a + 1 + alen), sort(b + 1, b + 1 + blen);
  ll cnt = 0;
  for (ll i = 1, j = blen; i <= alen; ++i) {
    while (j >= 1 && a[i] > m - b[j]) --j;
    cnt += j;
  }
  cout << cnt << endl;
  return 0;
}

思路

采用双向DFS，左半部分票价情况保存至a，右半部分票价情况保存至b。

对a和b排序之后，令a的游标i从1开始，令b的游标j从blen开始，使用双指针：

只要a[i] + b[j] > m，就--j；

遇到第一次两部分和小于等于m时，j就等于有a[i]存在的所有情况中满足题意的个数。