九月题目泛做总结。

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;
    }