11-17模拟赛

11 / 17 / 2020 | 最后修改于 11 / 17 / 2020

Contest OI

队伍统计

题目描述

现在有 nn 个人要排成一列，编号为 1→n1 \rightarrow n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有 mm 条矛盾关系 (u,v)(u, v) ，表示编号为 uu 的人想要排在编号为 vv 的人前面。要使得队伍和谐，最多不能违背 kk 条矛盾关系（即不能有超过 kk 条矛盾关系 (u,v)(u, v) ，满足最后 vv 排在了 uu 前面）。问有多少合法的排列。答案对 109+710^9+7 取模。

题解

状压DP

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
// Tags:
#include <algorithm>
#include <cctype>
#include <cstdio>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 21, mod = 1e9 + 7;
int n, m, k, f[1 << N][N], bhd[N];

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("count.in", "r", stdin);
  freopen("count.out", "w", stdout);
#endif
#endif

  read(n), read(m), read(k);
  for (int i = 0, u, v; i < m; ++i) {
    --read(u), --read(v);
    bhd[u] |= 1 << v;
  }
  f[0][0] = 1;
  for (int i = 0, lim = 1 << n; i < lim; ++i) {
    for (int j = 0; j < n; ++j) {
      if (!((i >> j) & 1)) {
        int cnt = __builtin_popcount(i & bhd[j]);
        for (int h = 0; h <= k - cnt; ++h) {
          f[i | (1 << j)][h + cnt] += f[i][h];
          if (f[i | (1 << j)][h + cnt] >= mod) f[i | (1 << j)][h + cnt] -= mod;
        }
      }
    }
  }
  ll ans = 0;
  for (int i = 0; i <= k; ++i) {
    ans += f[(1 << n) - 1][i];
    if (ans >= mod) ans -= mod;
  }
  printf("%lld", ans);
  return 0;
}

序列问题

题目描述

给定一个长度为 nn 的序列 AA。定义 f(l,r)=max(al,al+1,ar−1,qr)f(l, r)=max(a_l, a_{l+1}, a_{r-1}, q_r)，g(l,r)=min(al,al+1,⋯ ,ar)g(l,r) =min(a_l, a_{l+1}, \cdots , a_r)，希望你求出：

∑l=1n∑r=lnf(l,r)×g(l,r)(mod109+7)\sum_{l=1}^n \sum_{r=l}^n f(l,r) \times g(l,r) \pmod {10^9+7}

题解

序列问题还可以用分治考虑

在每一层中，预处理一边的前/后缀最大/小值，再枚举一边维护两个指针 i,ji, j 向另一边扫，如果使区间的max/min改变就停下来统计，分三种情况讨论

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
// Tags:
#include <algorithm>
#include <cctype>
#include <cstdio>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 5e5 + 5, mod = 1e9 + 7, inf = 0x3f3f3f3f;
int n, ans, a[N];

inline void add(int &x, int y) {
  if ((x += y) >= mod) x -= mod;
}

void solve(int l, int r) {
  if (l == r) return add(ans, (ll)a[l] * a[l] % mod);
  static int minl[N], maxl[N];
  static ll summin[N], summax[N], sumans[N];
  int mid = (l + r) >> 1;
  minl[mid + 1] = inf, maxl[mid + 1] = -inf,
  sumans[mid + 1] = summax[mid + 1] = summin[mid + 1] = 0;
  for (int i = mid; i >= l; --i) {
    minl[i] = std::min(minl[i + 1], a[i]);
    maxl[i] = std::max(maxl[i + 1], a[i]);
    summin[i] = (summin[i + 1] + minl[i]) % mod;
    summax[i] = (summax[i + 1] + maxl[i]) % mod;
    sumans[i] = (sumans[i + 1] + maxl[i] * minl[i] % mod) % mod;
  }

  for (int i = mid + 1, rmin = inf, rmax = -inf, j = mid, k = mid; i <= r; ++i) {
    rmax = std::max(a[i], rmax);
    rmin = std::min(a[i], rmin);
    while (j >= l && maxl[j] < rmax) --j;
    while (k >= l && minl[k] > rmin) --k;
    if (j > k)
      add(ans, ((ll)(mid - j) * rmax % mod * rmin % mod +
                rmin * (summax[k + 1] - summax[j + 1]) % mod + sumans[l] -
                sumans[k + 1]) %
                   mod);
    else
      add(ans, ((ll)(mid - k) * rmax % mod * rmin % mod +
                rmax * (summin[j + 1] - summin[k + 1]) % mod + sumans[l] -
                sumans[j + 1]) %
                   mod);
  }

  solve(l, mid);
  solve(mid + 1, r);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("seq.in", "r", stdin);
  freopen("seq.out", "w", stdout);
#endif
#endif

  read(n);
  for (int i = 1; i <= n; ++i) read(a[i]);
  solve(1, n);
  printf("%d", ans);
  return 0;
}

带权排序

/kk 先去改S2OJ上的题了，咕咕咕