杂题（二）

soj914 dp/组合

http://120.27.222.204:12243/problem/914

令 $f_i$ 表示长度为 $i$ 最后一个没被填的概率。

枚举第一次填哪里，那么和位置 $i$ 远的那一段就不用管了，只用管离 $i$ 近的一段。

$f_i=\sum\limits_{j=1}^{n-2}f_j * \frac{1}{n-1}$

然后长度为 $n$ 的数列， $p$ 位置被被填的概率，就是前 $p$ 项最后一个没被填乘上后 $n-p+1$ 项第一个（也就是最后一个）没被填的概率。

这样简单的题我想了一会没想出来。。

soj896 二分/dp

http://120.27.222.204:12243/problem/896

先二分答案，注意答案在 $[m,3m]$ 之间。

然后我们发现，假设令第一项填的是 $1$ 到 $m$ ，那么第 $i$ 项填 $1$ 多少个小于等于 $m$ 的数是一段区间，第 $i$ 项区间左端点和第 $i-1$ 项右端点有关，第 $i$ 项区间右端点和第 $i-1$ 项左端点有关。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e5 + 5;
int n;
ll m, l[N], r[N], a[N];
//
bool check(ll mid) {
  l[0] = r[0] = m;
  for (int i = 1; i < n; i++) {
    if (mid < a[i]) return false;
    l[i] = max(0ll, m - mid - r[i - 1] + max(r[i - 1], a[i]));
    r[i] = m - l[i - 1] + min(m - a[i], l[i - 1]);
    if (l[i] > r[i]) return false;
  }
  return m - l[n - 1] >= a[0];
}
int main() {
  ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> n >> m;
  rep(i, n) {
    cin >> a[i];
    if (a[i] > m) {
      cout << -1 << endl;
      return 0;
    }
  }
  ll lb = -1, rb = 2 * m;
  while (rb - lb > 1) {
    ll mid = (lb + rb) >> 1;
    if (check(mid)) rb = mid; else lb = mid;
  }
  cout << m + rb << endl;
  return 0;
}

其实thuwc上我做出过更难的，其实joiscd1t1的正解也是这个，但我又想不出来。

uoj180 树状数组

http://uoj.ac/problem/180

想要测试一下自己做题速度，大概 $20$ min内一遍 $AC$ 。

考虑排列 $A$ 前 $i$ 个已经交换好了，第 $i+1$ 个数字要交换进去，需要的条件是前 $i$ 个中比 $a_{i+1}$ 小的数字不能最终位置在 $a_{i+1}$ 右边。

我把排列倒过来做的。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e5 + 5;
int n, a[N], pos[N], dat[N];
//
void upd(int x, int y) {
  ++x;
  while (x < N) {
    dat[x] = max(dat[x], y);
    x += x & -x; 
  }
}
int qry(int x) {
  ++x; int ans = -1;
  while (x) {
    ans = max(ans, dat[x]);
    x -= x & -x;
  }
  return ans;
}
int main() {
  n = getint();
  rep(i, n) a[i] = getint() - 1;
  rep(i, n) pos[getint() - 1] = i;
  memset(dat, -1, sizeof(dat));
  for (int i = n - 1; i >= 0; i--) {
    if (qry(pos[a[i]] - 1) > a[i]) return !printf("NO\n");
    upd(pos[a[i]], a[i]);
  } 
  printf("YES\n");
  return 0;
}

soj923 dp

http://120.27.222.204:12243/problem/923

直接dp没问题，受伤，得病，伤病。

注意这四个和 $\leq 200$ ，状态数很少， $O(n^4)$ 。

还要注意中间可以一起取模，会快很多。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 998244353;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline void add(int &x, int y) {
  x += y - mod; x += x >> 31 & mod;
}
//ruogu_alter
const int M = 200 * 200 + 5;
const int N = 205;
int inv[M];
int n, m, f[3][N][N][N];
//
void init() {
  inv[0] = inv[1] = 1;
  for (int i = 2; i < M; i++) {
    inv[i] = mul(mod - mod / i, inv[mod % i]);
  }
}
int main() {
  init();
  n = getint(); m = getint();
  rep(A, n - m + 1) {
    int i = A % 3, j = (A - 1 + 3) % 3, k = (A - 2 + 3) % 3;
    rep(B, n - m - A + 1) {
      rep(C, n - A - B + 1) {
        rep(D, n - A - B - C + 1) {
          f[i][B][C][D] = 0;
          if (A + B + C + D > 1) {
            ll ans = 0;
            if (A >= 2) ans += 1ll * A * (A - 1) / 2 * f[k][B + 2][C][D];
            if (B >= 2) ans += 1ll * B * (B - 1) / 2 * f[i][B - 2][C][D];
            if (C >= 2) ans += 1ll * C * (C - 1) / 2 * f[i][B][C - 2][D + 2];
            if (D >= 2) ans += 1ll * D * (D - 1) / 2 * f[i][B][C][D - 2];
            if (A >= 1 && B >= 1) ans += 1ll * A * B * f[j][B][C][D];
            if (A >= 1 && C >= 1) ans += 1ll * A * C * f[j][B][C][D];
            if (A >= 1 && D >= 1) ans += 1ll * A * D * f[j][B][C + 1][D - 1];
            if (B >= 1 && C >= 1) ans += 1ll * B * C * f[i][B - 1][C - 1][D + 1];
            if (B >= 1 && D >= 1) ans += 1ll * B * D * f[i][B - 1][C][D];
            if (C >= 1 && D >= 1) ans += 1ll * C * D * f[i][B][C - 1][D];
            ans %= mod;
            f[i][B][C][D] = mul(ans, inv[(A + B + C + D) * (A + B + C + D - 1) / 2]);
            add(f[i][B][C][D], 1);
          }
        }
      }
    }
  }
  cout << f[(n - m) % 3][0][m][0] << endl;
  return 0;
}