8.27集训

Posted on Edited on In

今天有考试，有做题 第一个是单调队列的板子，

切了

注意细节与拓展：

  • 保证\(l \leq r\)的情况下
  • 求区间最小值，维护递减队列，如果\(a[i]>a[q[r]]\)，不断缩小r
  • 求区间最大值，维护递增队列，如果\(a[i]<a[q[r]]\)，不断缩小r

第二个是bzoj2151 火车

昨天没写完今天接着写的

细节多：

  • dep[0] = -1，不然就GG
  • 开LL
  • 数组得开到\(1e6\)以上

然后考试了

考试第一题，大致就是需要在树上寻找三条链并且有相同的公共部分求得最大的累加和

cjh给出状态....

然后就是转移了....

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66, inf = 0x3f3f3f3f;

int TO[N << 1], nex[N << 1], head[N << 1], cnt;

inline void add(int x, int y)
{
    TO[++ cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt;
}

int n, res = -inf;
int val[N], f[N][66];

inline void dfs(int x, int fa)
{
    f[x][0] = val[x]; int tmp[8], i, j, y;
    for (i = head[x]; i; i = nex[i])
    {
        y = TO[i];
        if (y == fa) continue;
        dfs(y, x);
        int *fx = f[x], *to = f[y];
        for (j = 0; j < 8; ++ j) tmp[j] = fx[j];

        tmp[1] = max(tmp[1], fx[0] + max(to[0], to[1]));
        tmp[4] = max(tmp[4], fx[0] + max(to[3], to[4]));
        tmp[7] = max(tmp[7], fx[0] + max(to[6], to[7]));
        tmp[2] = max(tmp[2], fx[1] + max(to[0], to[1]));
        tmp[5] = max(tmp[5], fx[1] + max(to[3], to[4]));

        res = max(res, max(fx[0], fx[1]) + max(to[6], to[7]));

        tmp[3] = max(tmp[3], fx[2] + max(to[0], to[1]));
        tmp[6] = max(tmp[6], fx[2] + max(to[3], to[4]));
        tmp[5] = max(tmp[5], fx[4] + max(to[0], to[1]));
        tmp[6] = max(tmp[6], fx[5] + max(to[0], to[1]));

        res = max(res, max(fx[3], fx[4]) + max(to[3], to[4]));
        res = max(res, max(fx[6], fx[7]) + max(to[0], to[1]));
        res = max(res, tmp[7]);

        for (j = 0; j < 8; ++ j) fx[j] = tmp[j];
    }
}

inline int thestars()
{
    int i, x, y;
    cin >> n;
    for (i = 1; i <= n; ++ i) cin >> val[i];
    for (i = 1; i < n; ++ i)
    {
        cin >> x >> y;
        add (x, y), add(y, x);
    }
    memset (f, 0xf3, sizeof f);
    dfs(1, 0);
    cout << res;
    return 0;
}

int youngore = thestars();

signed main() {;}

第二题

矩阵 + BSGS

第三题

求前缀最大值有a个，后缀最大值有b个的长度为n的排列个数。

显然每一个前缀最大值和一段连续的区间构成了一个环排列，显然每个前缀最大值就是这个环中的最大值。

而全局最大值一定把前后缀最大值分开。 所以答案考虑除最大值外，左侧需要a−1个前缀最大值，右侧需要b−1个前缀最大值。也就是一共要a+b−2个环，

那么这一部分的贡献是\(\begin{bmatrix}n-1\\a+b-2\end{bmatrix}\), 而环在左右随意分配，所以再乘上一个\(a+b-2\choose a-1\)

解释一个小问题，为什么不需要考虑环的最大值的大小关系，因为我们强制在排列过程中按照最大值从小往大放，而每个环因为放置的时候是一个线段，那么我们保证最大值一定在靠外侧，这样子后面的比它小的值必定不是前缀或者后缀最大值。

那么问题转化成了怎么预处理第一类斯特林数

第一类斯特林数：

\(\begin{bmatrix}n\\m\end{bmatrix}\)表示n个元素分成m个环的方案数。

那么递推式很显然：\(\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)*\begin{bmatrix}n-1\\m\end{bmatrix}\)

即考虑先前已经放好的n−1个数，当前新加入的这个元素有两种选择，第一种是自己成一个环，贡献是\(\begin{bmatrix}n-1\\m-1\end{bmatrix}\)

第二种是放到环内，那么它可以放在任意一个数的前面，所以就是\((n-1)*\begin{bmatrix}n-1\\m\end{bmatrix}\)

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
#include <bits/stdc++.h>
#define int long long
// #define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e3+66, mod = 998244353;

inline int ksm(int a, int b)
{
    if (! b) return 1;
    if (b & 1) return a * ksm(a, b-1) % mod;
    int tmp = ksm(a, b/2)%mod;
    return tmp * tmp % mod;
}

int f[N][N], js[N];

inline int thestars()
{
    int i, j, res, n, m, a, b;
    cin >> n >> a >> b; -- n;
    js[0] = 1, m = a + b - 2;
    for (i = 1; i <= (a + b)<<1; ++ i) js[i] = js[i - 1] * i % mod;
    res = js[m] * ksm(js[a - 1], mod - 2) % mod * ksm(js[b - 1], mod - 2) % mod;
    f[1][1] = 1;
    for (i = 2; i <= n; ++ i)
        for (j = 1; j <= i; ++ j)
            f[i][j] = (f[i - 1][j - 1] + (i - 1) * f[i - 1][j] % mod) % mod;
#ifdef debug
cout << f[n][m];
puts("");
#endif
    cout << f[n][m]*res%mod;
    return 0;
}

int youngore = thestars();

signed main() {;}