noip模拟49

09-09-2021 约 2640 字预计阅读 6 分钟

真·开幕雷击

T1 Reverse

众所周知，反转有两个意思，在这里取反转。随便列列表可以发现在字串合法的情况下，位移前和位移后的位置差为1,3,5,7或2,4,6,8。~~于是我开始dfs,然后TLE~~题解为 $O(nlogn)$ 做法，用前向星的思路可以砍掉一个log

设每个位置下一个可选（没被访问，若该位置为禁止位，则也把这个位置认为是访问过的）的位置为 $nxt[x]$ ，然后钦定每个位置的初始nxt为它的位置+2（因为位移变化量为2）进行BFS

BFS过程：

求出能包含这个点的字串的左端点的最小值和最大值
求助第一个可选的位置
把可选位置所对应的nxt设为最右端点
如果可选位置没被访问过就更新这个位置的答案，标记并加入队列
用nxt数组向后跳可选位置（位置满足小于最右端点）

 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


#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 = 100010;

template <typename LDXIN>
LDXIN read() {
  LDXIN 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;
}



int n, k, m, s;
int  nxt[maxn], ans[maxn];
bool vis[maxn];

queue<int> q;
int main() {
  n = read<int>();
  k = read<int>();
  m = read<int>();
  s = read<int>();
  Set(ans, -1);
  For(i, 1, m) {
    int pos = read<int>();
    vis[pos] = 1;
  }
  ans[s] = 0;
  For(i, 1, n) {
    nxt[i] = i + 2;
  }
  vis[s] = 1;
  q.push(s);
  while(!q.empty()) {
    int fnt = q.front();
    q.pop();
    int l = max(1, fnt - k + 1), r = min(fnt, n - k + 1);
    int pos = 2 * l + k - fnt - 1;
    while (pos <= 2 * r + k - fnt - 1) {
      int nxtt = nxt[pos];
      nxt[pos] = nxt[2 * r + k - fnt - 1];
      if (!vis[pos]) {
        ans[pos] = ans[fnt] + 1;
        vis[pos] = 1;
        q.push(pos);
      }
      pos = nxtt;
    }
  }
  For(i, 1, n) {
    cout << ans[i] << ' ';
  }
  cout << endl;
  return 0;
}

T2 Silhouette

显然对A和B数组排序不会影响最终答案，那就排个序

土块的图片：

 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


#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 = 10000010;
const int mod = 1e9 + 7;

template <typename LDXIN>
LDXIN read() {
  LDXIN 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;
}

#define   int long long

int qpow(int base, int pwr) {
  int ans = 1;
  while (pwr) {
    if (pwr & 1) {
      ans = 1ll * ans * base % mod;
    }
    base = 1ll * base * base % mod;
    pwr >>= 1;
  }
  return ans;
}


bool cmp(int a, int b) { return a > b; }

int a[maxn], b[maxn], fac[maxn], inv[maxn], invv[maxn];
int getC(int n, int m) {
  if (n < m) swap(n, m);
  return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}
int f(int A, int B, int a, int b, int s) {
  long long ans = 0;
  For(i, 0, a) {
    ans = (ans + qpow(mod - 1, i) * getC(a, i) % mod * qpow(s, B * i) % mod *
                     qpow(qpow(s + 1, A - i) - qpow(s, A - i) + mod, b) % mod *
                     qpow(qpow(s + 1, a - i), B - b)) %
          mod;
  }
  // cout << "F: " << (ans + mod) % mod << endl;
  return (ans + mod) % mod;
}
int n;
int32_t main() {
  n = read<int>();
  For(i, 1, n) { a[i] = read<int>(); }
  sort(a + 1, a + 1 + n, cmp);
  For(i, 1, n) { b[i] = read<int>(); }
  sort(b + 1, b + 1 + n, cmp);
  fac[1] = fac[0] = 1;
  inv[0] = inv[1] = 1;
  invv[0] = invv[1] = 1;
  For(i, 2, n * 100) {
    fac[i] = 1ll * fac[i - 1] * i % mod;
    invv[i] = mod - mod / i * invv[mod % i] % mod,
    inv[i] = inv[i - 1] * invv[i] % mod;
    // cout << fac[i] << ' ' << inv[i] << ' ' << invv[i] << endl;
  }
  long long ans = 1;
  int i = 1, j = 1;
  while (i <= n || j <= n) {
    int maxx = max(a[i], b[j]);
    int la = 0, lb = 0;
    // little a little b
    while (a[i] == maxx && i <= n) {
      i++;
      la++;
    }
    while (b[j] == maxx && j <= n) {
      j++;
      lb++;
    }
    ans *= f(i - 1, j - 1, la, lb, maxx);
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}

T3 Seat

还没改出来，先放std

  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>
using namespace std;
const int N = 1030;
int n, mod;
int qpow(int x, int k, int ans = 1) {
  while (k) {
    if (k & 1) ans = ans * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return ans;
}
// dp为答案
// f为题解中dp数组
// f[i][j]代表这一层已经坐了i个人，还有j个长度为偶数区间的概率
int dp[N][N], f[N][N], g[N][N], vis[N], inv[N], cnt[N], even[N], pos[N];
int main() {
  scanf("%d%d", &n, &mod);
  for (int i = 1; i <= n; ++i) inv[i] = qpow(i, mod - 2);
  vis[0] = vis[n + 1] = true;
  for (int i = 1; i <= n; ++i) {  // 找距离最大的可行区间
    int pl = 0, pr = 0, mx;
    for (int j = 0; j <= n; ++j) {
      int r = j + 1;
      while (!vis[r]) ++r;
      if (r - j > pr - pl) pl = j, pr = r;
      j = r - 1;
    }
    // mx = 最小距离最大值
    ++cnt[mx = pr - pl >> 1];  // 长度为mx的区间的个数++
    even[mx] += pr - pl & 1;  //长度为mx的层中包含长度为偶的区间个数++
    pos[i] = pl + mx;         // 第i层的人坐下的位置
    /*  *我错在没先坐在奇区间再坐在偶区间*  */
    vis[pl + mx] = true;
  }
  int sum = n;  // 还未坐下的人数
  for (int i = 1; i <= n; ++i) {
    if (!cnt[i]) continue;  //莫得坐
    int l = sum - cnt[i] + 1, r = sum;
    // 因为cnt[i]代表这一层有几个区间，所以这一层要坐cnt[i]个人（废话？）
    // l代表这一层坐下的最后一个人
    if (i == 1) {  // 特判最后一层， 这一层的人无论坐在哪里有一样，所以xjb坐就行
      for (int j = l; j <= r; ++j)
        for (int k = l; k <= r; ++k)
          dp[j][pos[k]] = inv[cnt[i]];  //直接赋值为距离为1个数的逆元？
                                        //或许这里也被平均掉了(wmz)
      // 其实是因为概率均等，所以直接乘上人数分之一就行
    } else {
      for (int j = 0; j <= cnt[i]; ++j)
        for (int k = 0; k <= even[i]; ++k) f[j][k] = 0;  //清空数组
      f[0][even[i]] = 1;  //还没有坐人，那么该层剩下even[i]个偶数区间的概率为1
      int p = l + even[i] - 1;  //偶数区间长度的最后一个人
      for (int j = 1; j <= cnt[i]; ++j) {
        int evenw = 0, oddw = 0;  // even为偶数 odd为奇数
        for (int k = 0; k <= even[i]; ++k) {
          if (!f[j - 1][k])
            continue;  // dp转移 所以f值为0的时候可以剪枝
                       // k表示剩余多少个偶数区间
          int frac = (cnt[i] - (j - 1)) + k,
              w = 0;  //括号内表示剩余的区间个数 +k表示剩余多少个转移点
          if (k) {  //还有偶区间剩余
            w = f[j - 1][k] * k * 2 % mod * inv[frac] %
                mod;  //占一个偶区间位置 那么概率为k*2/转移点
            evenw = (evenw + w * inv[even[i] * 2]) %
                    mod;  //方便累加答案 对于这一次的转移 可能作用在不同的转移点
            (f[j][k - 1] += w) %= mod;
          }
          if (cnt[i] - even[i]) {  //可以向奇区间转移
            w = f[j - 1][k] * (frac - 2 * k) % mod * inv[frac] %
                mod;  //向奇数区间转移的概率
            oddw = (oddw + w * inv[(cnt[i] + even[i]) - even[i] * 2]) %
                   mod;  //向不同奇数区间转移
            (f[j][k] += w) %= mod;
          }
        }
        for (int u = l; u <= p; ++u)
          (dp[l + j - 1][pos[u]] += evenw) %= mod,
              (dp[l + j - 1][pos[u] + 1] += evenw) %= mod;  //累加答案
        for (int u = p + 1; u <= r; ++u)
          (dp[l + j - 1][pos[u]] += oddw) %=
              mod;  //这里存在疑问 似乎将偶数区间默认加给了前面的pos
      }
      for (int j = l; j <= p; ++j) {             //偶区间
        int L = pos[j] - i + 1, R = pos[j] + i;  //当前的偶区间左右端点i是长度
        //因为逆推，所以当前以下的概率都算过了
        for (int v = L; v <= R; ++v) {
          if (v == pos[j]) continue;          //不能是选择的点
          for (int u = r + 1; u <= n; ++u) {  //后面每一个人
            int s = (v < pos[j]) ? (v + i + 1) : (v - i),  // 对称点
                w = dp[u][v] * inv[2] % mod;  //后一个人在位置v的概率除2
            (g[u][v] += w) %= mod;
            (g[u][s] += w) %= mod;  //平均一下 虽然不知道为啥 但是感觉很对(wmz)
            //每个人等概率坐在左边和右边，刚刚只算了左边，平均一下
          }
        }
        for (int v = L; v <= R; ++v)
          for (int u = r + 1; u <= n; ++u) dp[u][v] = g[u][v], g[u][v] = 0;
      }
    }
    sum -= cnt[i];  //考虑下一层 剩余人数减少
  }
  for (int i = 1; i <= n; i++, puts(""))
    for (int j = 1; j <= n; j++) printf("%d ", dp[i][j]);
  return 0;
}

目录

noip模拟49

真·开幕雷击

T1 Reverse

T2 Silhouette

T3 Seat