9.12集训

Posted on Edited on In

考试 bzoj2500幸福的道路

考虑分为两个子任务

  • 求出每个点在树上距离最远的距离
  • 求出一段最大值与最小值之差不超过m的最长的一段区间

第一个任务跑一边换根dp就好

第二个任务是Pilots，维护两个单调队列，发现差值大于m的时候，就弹弹弹

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>
using namespace std;

const int N = 1e6 + 66;
int n, m, res, pre;
int l1, r1, l2, r2, q1[N], q2[N];
int f[N], g[N][6];

inline void dfs1(int x)
{
    int i, y, z, fuck;
    for (i = head[x]; i; i = nex[i])
    {
        y = to[i], z = len[i];
        dfs1(y);
        fuck = g[y][1] + z;
        if (fuck > g[x][1])
        {
            g[x][2] = g[x][1];//ci max
            g[x][1] = fuck;//max
        }
        if (fuck > g[x][2] && fuck < g[x][1]) g[x][2] = fuck;
    }
    return;
}

inline void dfs2(int x)
{
    int i, y, z, fuck;
    for (i = head[x]; i; i = nex[i])
    {
        y = to[i], z = len[i];
        fuck = g[x][1] == g[y][1] + z ? g[x][2] : g[x][1];
        fuck = max(fuck, f[x]);
        fuck += z;
        f[y] = fuck;
        dfs2(y);
    }
    return;
}

signed main()
{
    int i, y, z;
    n = read(), m = read();
    for (i = 2; i <= n; ++ i)
    {
        y = read(), z = read();
        add(y, i, z);
    }
    f[1] = 0, dfs1(1), dfs2(1);
    for (i = 1; i <= n; ++ i) f[i] = max(f[i], g[i][1]); // step 1

    l1 = l2 = 1;
    for (i = 1; i <= n; ++ i)
    {
        while (l1 <= r1 && f[i] < f[q1[r1]]) -- r1;
        q1[++ r1] = i;
        while (l2 <= r2 && f[i] > f[q2[r2]]) -- r2;
        q2[++ r2] = i;
        while (f[q2[l2]] - f[q1[l1]] > m)
        {
            if (q2[l2] < q1[l1]) pre = q2[l2], ++ l2;
            else pre = q1[l1], ++ l1;
        }
        res = max(res, i - pre);
    }
    put(res);
    return 0;
}

PTA-Little Bird

简单dp

但是需要用单调队列来优化

Moovie Mooving G

这题壮压，并且用到bfs的搜索

bfs找到的第一个\(f[S]\)超过l就是正解了——因为宽搜保证看的电影数量递增

bzoj2121字符串游戏

区间dp

状态：

\(f[l][r]\)表示\(l,r\)这段区间能否被删除

\(g[l][r][i][j]\)表示\(l,r\)这段区间能否删成第\(i\)个字符串的前\(j\)个字符

考虑匹配到中间一块，或者是把这段区间劈开，分成两段

如果进行匹配的话转移为 \(g[l][r][i][j]=g[l][r-1][i][j-1]\)，前提条件，\(str[r] == w[i][j]\)即区间右端点和第 i 个串的第 j 个字符相同

如果考虑劈开的话，转移为：\(g[l][r][i][j]= g[l][k-1][i][j]\)&&\(f[k][r]\)

考虑答案， \(h[i] = h[i - 1] + 1\)或者\(h[i] = h[j-1]\)