noip模拟20

07-20-2021 约 1869 字预计阅读 4 分钟

玩具 - y - z

T1 玩具

正解是想不到的神仙做法，需要开三个数组：

dp[i][j]表示有i个点的森林，j个点在一颗（！）树上的概率
f[i][j]表示有i个点的树，深度不超过j的概率
g[i][j]表示有i个点的森林，深度不超过j的概率

dp[1][1] = 1 有1个点的森林（？）一定是1棵树

dp[i][j]的转移方程为 dp[i][j] = dp[i - 1][j - 1] * (j - 1)<原来这棵树大小> * inv[i]<除总点数> （再来1个点在一棵树上的概率） + dp[i - 1][j] * (i - j) * inv[i]（再来一个点不在一棵树上的概率）

$f[1][0 - n] = 1 \qquad g[0][0 - n] = 1$

$g[i][j] = \sum\limits^{i}_{k = 1} f[k][j] * g[i - k][j] * (i - j) * inv[i]$

Show You the Code

 


 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


#include <bits/stdc++.h>
#define For(i, l, r) for (int32_t i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int32_t i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 210;

template <typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}
template <typename ksm>
ksm qpow(int base, int power, int modd) {
  int ans = 1;
  while (power) {
    if (power & 1) {
      ans = 1ll * ans * base % modd;
    }
    base = 1ll * base * base % modd;
    power >>= 1;
  }
  return ans;
}

int n, mod;
int inv[maxn];
int64_t dp[maxn][maxn], f[maxn][maxn], g[maxn][maxn];
int main() {
  n = read<int>();
  mod = read<int>();
  inv[1] = 1;
  For(i, 2, n) { inv[i] = qpow<int>(i, mod - 2, mod); }
  dp[1][1] = 1;
  For(i, 2, n) {
    For(j, 1, i) {
      dp[i][j] = 1ll * dp[i - 1][j - 1] % mod * (j - 1) % mod * inv[i] % mod +
                 dp[i - 1][j] % mod * (i - j) % mod * inv[i] % mod;
    }
  }
  // correct
  // f[0][0] = f[1][0] = f[1][1] = f[2][1] = g[0][0] = g[1][0] = g[1][1] =
  //     g[2][1] = 1;
  For(i, 0, n) { f[1][i] = 1; }
  For(i, 0, n) { g[0][i] = 1; }
  For(i, 1, n) {
    For(j, 0, i - 1) {
      For(k, 1, i) {
        g[i][j] = (g[i][j] +
                   1ll * f[k][j] % mod * g[i - k][j] % mod * dp[i][k] % mod) %
                  mod;
      }
      f[i + 1][j + 1] = g[i][j];
      For(k, j + 1, n) { f[i + 1][k] = f[i + 1][j + 1]; }
      if (j == i - 1) {
        For(k, i, n) { g[i][k] = g[i][j]; }
      }
    }
  }
  long long ans = 0;
  For(i, 1, n - 1) {
    ans = (ans + i * (f[n][i] - f[n][i - 1])) % mod;
    // cout << f[n][i] << ' ' << f[n][i - 1] << endl;
    ans %= mod;
  }
  cout << (ans + mod) % mod << endl;
}

T2 y

考试时先想到状压，一看数据范围。压**啊，然后就不会了，实际上正解和状压是有点联系的

Official Solution:

$f[i][j][mask]$ 表示从 i 出发，j 结束，是否存在一条表示为 mask 的路径。发现 t 掉了，meet in the middle，对于每种可能的路径，枚举中间的那个位置判断。 bitset 一发可以整体除以 64，可以把 n 开得更大

em？MITM（此非彼）？这怎么想的到？实现起来挺简单但记得不要直接写等号，要写或，因为不止有一种方法可以转移到这个点（见代码）

cOdE




  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
 99
100
101
102
103
104
105


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 23333;
template <typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

struct EDGE {
  int to, next;
  bool w;
} edge[maxn];
int tote, head[maxn];
void addEdge(int from, int to, bool w) {
  edge[++tote].to = to;
  edge[tote].next = head[from];
  edge[tote].w = w;
  head[from] = tote;
}

int maxs;

unordered_map<int, bool> mp[91][91], mp1[91][91];  //[step][to][state]
int up[91];
int n, m, d;
bool vis[1 << 21];
int main() {
  n = read<int>();
  m = read<int>();
  d = read<int>();
  int hd = (d + 1) / 2;
  For(i, 1, m) {
    int from, to, w;
    from = read<int>();
    to = read<int>();
    w = read<int>();
    addEdge(from, to, w);
    addEdge(to, from, w);
  }
  mp[0][1][0] = true;
  maxs = (1 << hd) - 1;

  For(step, 0, hd - 1) {
    For(pnt, 1, n) {
      for (int i = head[pnt]; i; i = edge[i].next) {
        int to = edge[i].to, w = edge[i].w;
        For(state, 0, (1 << step) - 1) {
          mp[step + 1][to][(state << 1) | w] |= mp[step][pnt][state];//here
        }
      }
    }
  }
  For(i, 1, n) { mp1[0][i][0] = true; }
  For(step, 0, d - hd - 1) {
    For(pnt, 1, n) {
      for (int i = head[pnt]; i; i = edge[i].next) {
        int to = edge[i].to, w = edge[i].w;
        For(state, 0, (1 << step) - 1) {
          mp1[step + 1][to][(state << 1) | w] |= mp1[step][pnt][state];
        }
      }
    }
  }
  vector<int> hb[91], qb[91];
  For(i, 1, n) {
    For(state, 0, maxs) {
      if (mp[hd][i][state]) {
        hb[i].push_back(state);
      }
    }
  }
  For(i, 1, n) {
    For(state, 0, maxs) {
      if (mp1[d - hd][i][state]) {
        qb[i].push_back(state);
      }
    }
  }
  int ans = 0;
  For(i, 1, n) {
    for (auto j : qb[i]) {
      for (auto k : hb[i]) {
        if (!vis[(k << hd) | j]) {
          vis[(k << hd) | j] = true;
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

T3 z

xswl给的std只有31分，稍微删一下点的纯暴力都有45分




 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


#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; i++)
using namespace std;
const long long maxn = 100010;

template <typename type>
type read() {
  type s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

vector<long long> x;
long long n, q;
int main() {
  n = read<long long>();
  q = read<long long>();
  x.reserve(maxn);
  long long b1, b2;
  // x.push_back(0);
  For(i, 1, n) {
    long long in = read<long long>();
    if (in == x.back()) continue;
    x.push_back(in);
    if (i == 1) {
      b2 = in;
      continue;
    }
    if (i == 2) {
      b1 = in;
      continue;
    }
    if ((b1 < in && b2 < b1) || (b2 > b1 && b1 > in)) {
      x.erase(x.end() - 2);
      b1 = in;
      continue;
    }
    b2 = b1;
    b1 = in;
  }
  // for (auto i : x) {
  //   cout << i << endl;
  // }
  For(i, 1, q) {
    long long l;
    l = read<long long>();
    long long L = 0, R = l;
    long long ans = 0;
    for (auto pos : x) {
      if (pos >= L && pos <= R) continue;
      if (pos < L) {
        ans += L - pos;
        L = pos;
        R = L + l;
      }
      if (pos > R) {
        ans += pos - R;
        R = pos;
        L = R - l;
      }
    }
    cout << ans << endl;
  }
  return 0;
}
/*
9 6
2 -3 -1 1 2 3 5 3 7
 */

目录

noip模拟20

T1 玩具

T2 y

T3 z