九月题目泛做总结。

Keywords

Special Dijkstra, Double Pointer, Doubling, Monotonic Deque, Dynamic Programming, Matrix Multiplication, Shortest Path, Smart Mind

Table of Contents

  1. Keywords
  2. BZOJ 1922 大陆争霸
    1. Description
    2. Solution
  • BZOJ 2093 Frog
    1. Description
    2. Solution
  • BZOJ 2276 Temperature
    1. Description
    2. Solution
  • BZOJ 1860 麻将
    1. Description
    2. Solution
  • BZOJ 1297 迷路
    1. Description
    2. Solution
  • BZOJ 3445 Roadblock
    1. Description
    2. Solution
  • BZOJ 1922 大陆争霸

    Description

    一些点有进入限制, 只有在其他点的限制消除之后才能进入. 求 $1$ 到 $n$ 的最短路.

    Solution

    一个点的进入时间是最短路和消除限制的时间取max.

    这样转移的时候, 首先对自己的时间取max, 然后考虑转移, 首先更新最短路, 如果限制为0, 说明可以转出, 压入堆.

    然后是消除限制, 更新被消除节点消除限制的时间, 如果恰好限制降为0, 求出节点最终时间, 压入堆.

    最后节点 $n$ 的信息就是答案.

    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
    #include <bits/stdc++.h>

    using namespace std;

    const int maxn = 3005;
    const int maxm = 70005;

    struct edge
    {
    int to, nxt, v;
    }e[maxm];
    struct node
    {
    int dis, id;
    node(int d_ = 0, int i_ = 0):
    dis(d_), id(i_){}
    bool operator < (const node &rhs) const
    {
    return dis > rhs.dis;
    }
    };
    int n, m, ptr, lnk[maxn], vis[maxn];
    int dis[maxn], rep[maxn], dgr[maxn];
    vector<int> rge[maxn];
    priority_queue<node> q;

    inline void add(int bgn, int end, int val)
    {
    e[++ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val;
    lnk[bgn] = ptr;
    }
    inline void dijkstra()
    {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0; q.push(node(0, 1));
    while(!q.empty())
    {
    node u = q.top(); q.pop();
    if(vis[u.id]) continue;
    vis[u.id] = 1;
    int mx = max(dis[u.id], rep[u.id]);
    for(int p = lnk[u.id]; p; p = e[p].nxt)
    {
    int y = e[p].to;
    if(dis[y] > mx + e[p].v)
    {
    dis[y] = mx + e[p].v;
    int tmp = max(dis[y], rep[y]);
    if(!dgr[y]) q.push(node(tmp, y));
    }
    }
    for(vector<int>::iterator p = rge[u.id].begin(); p != rge[u.id].end(); ++p)
    {
    dgr[*p]--;
    rep[*p] = max(rep[*p], mx);
    int tmp = max(dis[*p], rep[*p]);
    if(!dgr[*p])
    q.push(node(tmp, *p));
    }
    }
    }

    int main()
    {
    scanf("%d%d", &n, &m);
    int u, v, w;
    for(int i = 1; i <= m; ++i)
    {
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
    }
    for(int i = 1; i <= n; ++i)
    {
    scanf("%d", &dgr[i]);
    for(int j = 1; j <= dgr[i]; ++j)
    {
    int x; scanf("%d", &x);
    rge[x].push_back(i);
    }
    }
    dijkstra();
    printf("%d\n", max(dis[n], rep[n]));
    return 0;
    }

    BZOJ 2093 Frog

    Description

    一只青蛙每次从一个位置出发会跳到第 $k$ 远的石头上去. 求从每个位置出发, 跳 $m$ 次后的位置情况.

    Solution

    $m$ 是long long级别的, 所以肯定不能直接做, 因为每个点出发的到达都是固定的, 所以我们可以倍增或者记忆化.

    再考虑怎么求第 $k$ 远, 维护一个双指针, 每次不满足就一直右移, 然后取较大的一边就是答案.

    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
    #include <bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    const int maxn = 1e+6 + 5;

    int n, k, jm[maxn], pos;
    int q[maxn], hd, tl, f[maxn], t[maxn];
    ll m, dis[maxn];

    inline int rd()
    {
    register int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x;
    }
    inline ll rdll()
    {
    register ll x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x;
    }

    int main()
    {
    n = rd(); k = rd(); m = rdll();
    for(int i = 1; i <= n; ++i) dis[i] = rdll();
    f[1] = k + 1; int lptr = 1, rptr = k + 1;
    for(int i = 2; i <= n; ++i)
    {
    while(rptr < n && dis[rptr + 1] - dis[i] < dis[i] - dis[lptr]) lptr++, rptr++;
    if(dis[rptr] - dis[i] <= dis[i] - dis[lptr]) f[i] = lptr;
    else f[i] = rptr;
    }
    for(int i = 1; i <= n; ++i) jm[i] = i;
    while(m)
    {
    if(m & 1)
    {
    for(int i = 1; i <= n; ++i) t[i] = jm[i];
    for(int i = 1; i <= n; ++i) jm[i] = f[jm[i]];
    }
    for(int i = 1; i <= n; ++i) t[i] = f[f[i]];
    for(int i = 1; i <= n; ++i) f[i] = t[i];
    m >>= 1;
    }
    for(int i = 1; i <= n; ++i) printf("%d ", jm[i]);
    return 0;
    }

    BZOJ 2276 Temperature

    Description

    某国进行了连续 $n$ 天的温度测量,测量存在误差,测量结果是第 $i$ 天温度在$[l_i,r_i]$范围内。

    求最长的连续的一段,满足该段内可能温度不降。

    Solution

    答案转移合法的条件, 其实是满足连续一段区间内, $L$ 的最大值没有超过当前结尾的 $R$, 并且 $R - 1$ 是合法的.

    怎么维护 $L$ 的最大值? 单调队列啦.

    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
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <cctype>

    using namespace std;

    const int maxn = 1e+6 + 5;

    int n, l[maxn], r[maxn], q[maxn];
    int hd = 1, tl = 0, ans;

    inline int rd()
    {
    register int x = 0, f = 0; char c = getchar();
    while(!isdigit(c)) {if(c == '-') f = 1; c = getchar();}
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return f ? -x : x;
    }

    int main()
    {
    n = rd();
    for(register int i = 1; i <= n; ++i) l[i] = rd(), r[i] = rd();
    for(register int i = 1; i <= n; ++i)
    {
    //l[i] = rd(); r[i] = rd();
    while(l[q[hd]] > r[i] && hd <= tl) hd++;
    if(hd <= tl)
    ans = max(ans, i - q[hd] + 1);
    int pos = i;
    while(l[i] > l[q[tl]] && hd <= tl) pos = q[tl], tl--;
    l[pos] = l[i], q[++tl] = pos;
    }
    printf("%d\n", ans);
    return 0;
    }

    BZOJ 1860 麻将

    Description

    有每种号码的牌若干张, 可以打出三连, 三相同, 四相同(Bouvardia不会麻将术语啦!), 并且一定要正好打出一个对子.

    验证每组数据是否可行.

    Solution

    一眼看去又像斗地主之类的神仙题的说……其实可以DP.

    由于顺子的存在, 只记录当前牌型的状态是得不到确定状态的, 因为无法同时确定连续三张的状态, 所以我们记录这一张和之前两种的状态. 但是这样的状态是浪费的, 因为确定两张可以唯一确定上一张.

    那么最终状态就是 $f[i][j][k][0/1] = 0/1$. 第$i$种牌, 有$k$张要打出, 上一种有 $j$ 张要打出, 有没有对子, 是否可行.

    枚举各种出牌方式转移一下就好啦.

    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
    #pragma GCC optimize(3)
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cctype>

    using namespace std;

    const int maxn = 105;

    int n;
    int line[maxn];
    int f[maxn][maxn][maxn][2];

    inline int rd()
    {
    register int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x;
    }


    int main()
    {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
    for(int j = 1; j <= 100; ++j) line[j] = rd();
    memset(f, 0, sizeof f);
    f[0][0][0][0] = 1;
    for(int p = 1; p <= 100; ++p)
    for(int j = 0; j <= line[p-1]; ++j)
    for(int k = 0; k <= line[p]; ++k)
    {
    if(k > 1) f[p][j][k][1] |= f[p][j][k-2][0];
    if(k > 2) f[p][j][k][1] |= f[p][j][k-3][1], f[p][j][k][0] |= f[p][j][k-3][0];
    if(k > 3) f[p][j][k][1] |= f[p][j][k-4][1], f[p][j][k][0] |= f[p][j][k-4][0];
    if(j >= k && line[p-2] >= k) f[p][j][k][1] |= f[p-1][line[p-2]-k][j-k][1], f[p][j][k][0] |= f[p-1][line[p-2]-k][j-k][0];
    }
    if(f[100][line[99]][line[100]][1]) puts("Yes");
    else puts("No");
    }
    return 0;
    }

    BZOJ 1297 迷路

    Description

    有若干个点, 边带权$(0 \le w \le 9)$. 问经过给定距离后从一个点到达一个点的路径条数, 距离很大.

    Solution

    一看很大和路径条数就是矩阵了.

    但是有权怎么求呢?

    发现边权很小, 所以可以按距离拆点, 每个点拆成$0 \cdots 8$. 做矩阵快速幂, 最后$(i_0,j_0)$就是$(i,j)$的答案.

    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 <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cmath>

    using namespace std;

    const int maxn = 11;

    int n, t, N;
    int mtr[maxn][maxn], id[maxn][maxn];
    struct matrix
    {
    static const int MAXN = 110;
    int a[MAXN][MAXN];
    matrix() {memset(a, 0, sizeof a);}
    void e()
    {
    memset(a, 0, sizeof a);
    for(int i = 1; i <= N; ++i)
    a[i][i] = 1;
    }
    int& operator () (int x, int y)
    {
    return a[x][y];
    }
    matrix operator * (matrix rhs)
    {
    matrix ret;
    for(int k = 1; k <= N; ++k)
    for(int i = 1; i <= N; ++i)
    for(int j = 1; j <= N; ++j)
    ret(i, j) = (ret(i,j) + a[i][k] * rhs(k, j)) % 2009;
    return ret;
    }
    }res;

    inline matrix quick_power(matrix base, int index)
    {
    matrix ret; ret.e();
    while(index)
    {
    if(index & 1) ret = ret * base;
    index >>= 1;
    base = base * base;
    }
    return ret;
    }

    int main()
    {
    scanf("%d%d", &n, &t);
    char opt[20];
    int cnt = 0;
    for(int i = 1; i <= n; ++i)
    for(int p = 0; p <= 8; ++p)
    id[i][p] = ++cnt;
    for(int i = 1; i <= n; ++i)
    for(int p = 0; p < 8; ++p)
    res(id[i][p], id[i][p + 1]) += 1;
    N = cnt;
    for(int i = 1; i <= n; ++i)
    {
    scanf("%s", opt + 1);
    for(int j = 1; j <= n; ++j)
    {
    mtr[i][j] = (opt[j] ^ 48);
    if(!mtr[i][j]) continue;
    res(id[i][mtr[i][j] - 1], id[j][0]) += 1;
    }
    }
    matrix p = quick_power(res, t);
    printf("%d\n", p(id[1][0], id[n][0]));
    return 0;
    }

    BZOJ 3445 Roadblock

    Description

    给定一个无向图, 可以选择一条边, 使其边权加倍, 最大化加倍后 $1$ 到 $n$ 的最短路.

    Solution

    想一想就可以发现加倍的一定是最短路的说.

    所以枚举量是$O(n)$级别的. 这样算下来Dijkstra其实是不行的, 所以就相信一次死去的SPFA咯.

    做完了.

    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
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    #include <bitset>
    #include <cctype>

    using namespace std;

    typedef long long ll;

    const int maxn = 265;
    const int maxe = 250005;
    const int inf = 0x3f3f3f3f;

    struct edge
    {
    int to, nxt, v;
    }e[maxe];
    int n, m, ptr = 1, lnk[maxn], id[maxn], pre[maxn];
    ll dis[maxn], dis2[maxn];
    queue<int> q;
    bitset<maxn> vis;

    inline int rd()
    {
    register int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x;
    }
    inline void add(int bgn, int end, int val)
    {
    e[++ptr] = (edge){end, lnk[bgn], val};
    lnk[bgn] = ptr;
    }
    inline void spfa()
    {
    fill(dis, dis + 2 + n, inf);
    dis[1] = 0; q.push(1); vis[1] = 1;
    while(!q.empty())
    {
    int u = q.front(); q.pop(); vis[u] = 0;
    for(int p = lnk[u]; p; p = e[p].nxt)
    {
    int y = e[p].to;
    if(dis[y] > dis[u] + e[p].v)
    {
    dis[y] = dis[u] + e[p].v;
    pre[y] = u; id[y] = p;
    if(!vis[y]) vis[y] = 1, q.push(y);
    }
    }
    }
    }
    inline void spFa()
    {
    fill(dis2, dis2 + 2 + n, inf);
    dis2[1] = 0; q.push(1); vis[1] = 1;
    while(!q.empty())
    {
    int u = q.front(); q.pop(); vis[u] = 0;
    for(int p = lnk[u]; p; p = e[p].nxt)
    {
    int y = e[p].to;
    if(dis2[y] > dis2[u] + e[p].v)
    {
    dis2[y] = dis2[u] + e[p].v;
    if(!vis[y]) vis[y] = 1, q.push(y);
    }
    }
    }
    }

    int main()
    {
    n = rd(); m = rd();
    register int x, y, l;
    for(register int i = 1; i <= m; ++i)
    {
    x = rd(); y = rd(); l = rd();
    add(x, y, l); add(y, x, l);
    }
    spfa();
    int cur = n;
    ll ans = 0, X = dis[n];
    while(cur != 1)
    {
    e[id[cur]].v *= 2; e[id[cur]^1].v *= 2;
    spFa();
    ans = max(ans, dis2[n] - X);
    e[id[cur]].v /= 2; e[id[cur]^1].v /= 2;
    cur = pre[cur];
    }
    printf("%lld\n", ans);
    return 0;
    }