• 2022“杭电杯” 中国大学生算法设计超级联赛（4）1 2 题解

    1001-Link with Bracket Sequence II

    题目大意：
    有一个长度为n的括号序列，一共有m种括号，序列中有若干个位置是空的，可以填上任意的括号。
    合法的序列定义如下：

    • 空序列是合法的
    • A是合法序列，那么 (i A )i 也是合法序列（同类型的左括号和同类型的右括号匹配）
    • A、B是合法序列，那么AB也是合法序列

    问给定的序列可以构成多少种合法序列。
    输入的序列中，绝对值相等的为同一种类型的括号。正数表示左括号，复数表示右括号，0表示空。

    思路：
    对于一个长度大于2的合法括号序列，一定是(i A )i 或 AB的形式。
    考虑用区间dp，dp[i][j]表示区间[i,j]的合法序列数量，状态转移方程如下：

    1. dp[i][j] = get(i,j) * dp[i+1][j-1] get(i,j)表示 i 和 j 位置的括号能组成的合法括号对数
    2. dp[i][j] += dp[i][k] * dp[k+1][j]

    但是第二个转移方程存在重叠问题，比如1 -1 0 0 0 0 2 -2这种。

    考虑换一种枚举的方式，以右括号 j 的匹配左括号位置作为k进行枚举，就可以保证是不重叠的。

    为了方便计算，可以定义两种状态：
    g[i][j]表示区间[i,j]的合法序列数量
    f[i][j]表示区间[i,j]中i和j位置的括号匹配的合法序列数量

    状态转移方程如下：
    f[i][j] = g[i + 1][j - 1] * get(i, j)
    g[i][j] += g[i][k] * f[k+1][j]

    需要注意的是，计算i 和 j 位置的括号能组成的合法括号对数时要避免将左边是右括号，右边是左括号的情况算进去。

    AC代码：

    #include 
const int N = 5e2 + 5;
const long long mod = 1e9 + 7;
using namespace std;

long long a[N], f[N][N], g[N][N], n, m;

long long get(int l, int r)
{
    if (a[l] >= a[r]) //防止出现左边是右括号，右边是左括号的情况
    {
        if (a[l] == 0 && a[r] == 0) return m;
        if (a[l] == -a[r] || a[l] * a[r] == 0) return 1;
    }
    return 0;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    if (n & 1) //如果长度是奇数的话无论如何都构不成合法序列
    {
        cout << "0" << endl;
        return;
    }
    for (int len = 2; len <= n; len += 2) //枚举区间长度
    {
        int maxl = n - len + 1;
        for (int l = 1; l <= maxl; l++)
        {
            int r = l + len - 1;
            f[l][r] = g[l + 1][r - 1] * get(l, r) % mod;
            g[l][r] = f[l][r];
            for (int k = l + 1; k <= r - 2; k += 2)
                g[l][r] = (g[l][r] + g[l][k] * f[k + 1][r] % mod) % mod;
        }
    }
    cout << g[1][n] << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    for (int i = 1; i < N; i++)
        g[i][i - 1] = 1;
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}


    • 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

    1002-Link with Running

    题目大意：
    给定一个图，每条边有两个权值e和p，从1出发到n，在保证e的权值和最小的情况下使得p值和最大。
    输出e和p的结果。(e,p>=0)

    思路：
    图论大杂烩题。
    如果只是求最小的e，因为没有负边权，直接用dijkstra跑就行。
    现在考虑p，题目保证结果是存在的，因此在1到n的路径上不会存在e=0，p>0的环。但是会存在e=0，p=0的环。
    一开始想的是跑dijkstra的时候如果e相同的时候p更大就更新，然后类似拓扑排序，将能到达y的所有点都更新后再将y入队。
    但是这种做法在遇到e=0，p=0的环时会失效，只有在DAG上才能跑。
    那么可以将最短路先提取出来，进行缩点，使得图变成一个DAG。
    然后在缩点后的图上跑最长路即可，跑最长路的时候也是将到达y点的所有点更新后再将y入队，需要记录y的入度。
    一共要建三个图，代码量比较大，需要注意初始化的时候不要漏了某些变量。

    AC代码：

    #include 
const long long inf = 1e18 + 7;
const int N = 3e5 + 5;
using namespace std;

long long n, m, din[N]; // din[i]记录强连通分量的入度

struct edge
{
    int to, next;
    long long e, p;
} e1[N], e2[N], e3[N];
int head1[N], head2[N], head3[N], ecnt1, ecnt2, ecnt3;

void add1(int u, int v, int e, int p) //初始图加边
{
    e1[++ecnt1] = {v, head1[u], e, p};
    head1[u] = ecnt1;
}
void add2(int u, int v, int e, int p) //最短路加边
{
    e2[++ecnt2] = {v, head2[u], e, p};
    head2[u] = ecnt2;
}
void add3(int u, int v, int e, int p) //缩点后的图加边
{
    e3[++ecnt3] = {v, head3[u], e, p};
    head3[u] = ecnt3;
    din[v]++; //入度+1
}

struct node
{
    long long dis, idx;
};
bool operator<(node a, node b) { return a.dis > b.dis; }
long long dis[N];
void dijkstra()
{
    priority_queue<node> q;
    long long d, id;
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    q.push({0, 1});
    while (q.size()) //在第一个图上跑最短路
    {
        d = q.top().dis;
        id = q.top().idx;
        q.pop();
        if (d != dis[id]) continue;
        for (int i = head1[id]; i; i = e1[i].next)
        {
            int v = e1[i].to, e = e1[i].e, p = e1[i].p;
            if (d + e < dis[v])
            {
                dis[v] = d + e;
                q.push({dis[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++) //建第二个图，只保留最短路径
    {
        if (dis[i] == inf) continue;
        for (int j = head1[i]; j; j = e1[j].next)
        {
            int v = e1[j].to, e = e1[j].e, p = e1[j].p;
            if (dis[i] + e == dis[v])
                add2(i, v, e, p);
        }
    }
}

int dfn[N], low[N], group[N], cnt, tot;
stack<int> S;
void tarjan(int x) //求出给个点所属的强连通分量
{
    dfn[x] = low[x] = ++tot;
    S.push(x);
    for (int i = head2[x]; i; i = e2[i].next)
    {
        int v = e2[i].to;
        if (!dfn[v]) //这个点还没有被访问过
        {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if (!group[v]) //这个点不属于任何一个连通集（说明还在栈中）
            low[x] = min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x]) //该顶点为连通集的第一个被访问元素
    {
        cnt++; //连通集个数加一
        while (S.top() != x)
        {
            group[S.top()] = cnt; //记录所属的连通集
            S.pop();
        }
        group[x] = cnt;
        S.pop();
    }
}

void shrink() //强连通分量缩点
{
    tarjan(1); //求出给个点所属的强连通分量

    for (int i = 1; i <= n; i++) //建第三个图，强连通分量之间连边
    {
        for (int j = head2[i]; j; j = e2[j].next)
        {
            int v = e2[j].to;
            if (group[i] != group[v]) //位于两个不同的强连通分量中
                add3(group[i], group[v], e2[j].e, e2[j].p);
        }
    }
}

long long dp[N]; //最大p
void getmaxp()   //跑最长路
{
    for (int i = 1; i <= cnt; i++)
        dp[i] = -inf;
    queue<int> q;
    dp[group[1]] = 0;
    q.push(group[1]);
    while (q.size())
    {
        int x = q.front();
        q.pop();
        for (int i = head3[x]; i; i = e3[i].next)
        {
            int v = e3[i].to;
            dp[v] = max(dp[v], dp[x] + e3[i].p);
            if (--din[v] == 0) q.push(v); //将该点的入点都更新完之后再将该点入队
        }
    }
}
void init()
{
    ecnt1 = ecnt2 = ecnt3 = 0;
    cnt = tot = 0;
    while (S.size())
        S.pop();
    for (int i = 0; i <= n; i++)
    {
        head1[i] = head2[i] = head3[i] = 0;
        group[i] = dfn[i] = low[i] = 0;
        din[i] = 0;
    }
}
void solve()
{
    int u, v, e, p;
    cin >> n >> m;
    init();
    while (m--)
    {
        cin >> u >> v >> e >> p;
        add1(u, v, e, p);
    }
    dijkstra();
    shrink();
    getmaxp();
    cout << dis[n] << " " << dp[group[n]] << endl;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 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
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176

    1003-Magic

    题目大意：
    有若干个魔法塔，编号为1…n。
    激活每个魔法塔最少需要pi点能量。
    一次充能操作为选择一个魔法塔 i ，使得区间[i-k+1, i+k-1]内的魔法塔能量值加1。
    充能操作存在限制,[li, ri]区间内最多进行b次充能。
    问是否存在解，如果存在，输出最少的充能次数。

    思路：
    要输出最少的次数，又存在大小限制，如果能想到用差分约束来做这道题的话就很简单了。
    为了便于建图，用a[i]表示区间[0, i]内的充能次数。
    一共是三种约束条件：

    • 激活魔法塔最低能量：a[i+k-1] - a[i-k] >= p[i] => a[i-k] - a[i+k-1] <= -p[i]
    • 区间内操作次数限制：a[r] - a[l-1] <= b
    • 前缀和自身的约束：a[i-1] - a[i] <=0

    然后将dis[0]置为0后跑spfa即可，跑出来的dis是负值，最后要乘-1。

    AC代码：

    #include 
const int inf = 1e9 + 7;
const int N = 1e4 + 5;
using namespace std;

struct edge
{
    int to, next, w;
} e[N * 10];
int head[N], ecnt;
void add(int u, int v, int w) { e[++ecnt].next = head[u], e[ecnt].to = v, e[ecnt].w = w, head[u] = ecnt; }
void einit(int n)
{
    ecnt = 0;
    for (int i = 0; i <= n; i++)
        head[i] = 0;
}

int n, k, dis[N], cnt[N];
bool vis[N];
bool spfa(int start = 0) //算法主体
{
    for (int i = 0; i <= n; i++) // cnt记录松弛次数，vis记录是否入队
    {
        dis[i] = inf;
        vis[i] = cnt[i] = 0;
    }
    dis[start] = 0;
    queue<int> q;
    q.push(start);

    vis[start] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            int w = e[i].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
                if (++cnt[v] >= n) return false;
            }
        }
    }
    return true; //没有负环，返回true
}

void solve()
{
    int p, q, l, r, b;
    cin >> n >> k;
    einit(n);
    for (int i = 1; i <= n; i++) //魔法塔最少能量约束
    {
        cin >> p;
        add(max(i - k, 0), min(i + k - 1, n), -p);
    }
    cin >> q;
    for (int i = 1; i <= q; i++) //区间和约束
    {
        cin >> l >> r >> b;
        add(r, l - 1, b);
    }
    for (int i = 1; i <= n; i++) //前缀和自身的约束，后面的不小于前面的
        add(i - 1, i, 0);
    if (spfa())
        cout << -dis[n] << endl;
    else
        cout << "-1" << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 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

    1005-Link with Level Editor II

    题目大意：
    有若干个图和若干个点，每个图中的点是相同的，但是边不同。在一个图中可以选择从当前结点走向相邻的结点，也可以选择留在当前结点。初始时的结点为1，终点为m。(m<=20)
    从给定的图序列中求出最长的子序列长度，使得子序列从1走到m的路径数不大于k。

    思路：
    因为每个图中最多只有20个点，要求出从一个点到另一个点的路径数，可以用矩阵乘法来快速求得。
    同时子序列具有单调性，当左边界确定后，移动右边界只会使得路径数更多，因此可以用双指针。
    矩阵是满足结合率的，可以预处理一段区间的乘积，但是在移动左边界指针时，要将最左侧的矩阵除去却是很困难的。
    因此要设法规避除法的操作，这里用了一个技巧：对顶栈。
    先介绍一个变量limit，表示当前预处理的区间乘积右端点都是到limit
    然后是双指针l和r表示当前区间的左右端点。
    cur变量表示区间[limit, r]的乘积。
    当移动r时，只要将cur乘上矩阵r即可。然后将cur与预处理的l到limit的区间乘积相乘即可得到1到m的路径数。
    移动l时，判断l是否大于limit，如果大于limit，就将limit赋值为r，重新计算从l到limit的所有区间乘积，因为l只会右移，因此原来预处理范围内的区间乘积不会再用到了。
    时间复杂度为O(nm3)

    由于矩阵不满足交换率，在计算矩阵乘积的时候一定要注意计算顺序。

    AC代码：

    #include 
const long long inf = 1e9 + 7;
const int N = 5e3 + 5;
const int M = 21;
using namespace std;
int n, m, k;
struct Matrix //行和列相同的矩阵
{
    long long num[M][M];
    Matrix(long long x = 0) //初始化为x单位矩阵
    {
        memset(num, 0, sizeof(num));
        for (int i = 1; i <= m; i++)
            num[i][i] = x;
    }
    Matrix operator*(const Matrix &that) const
    {
        Matrix res;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                for (int k = 1; k <= m; k++)
                    res.num[i][j] = min(inf, res.num[i][j] + num[i][k] * that.num[k][j]);
        return res;
    }
};

Matrix a[N], b[N];

bool check(Matrix &x, Matrix &y)
{
    long long cnt = 0;
    for (int i = 1; i <= m; i++)
        cnt = min(inf, cnt + x.num[1][i] * y.num[i][m]);
    return cnt <= k;
}

void solve()
{
    int u, v;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        int l;
        cin >> l;
        a[i] = 1; //初始化为1矩阵，因为可以留在原地
        while (l--)
        {
            cin >> u >> v;
            a[i].num[u][v] = 1;
        }
    }
    int ans = 0;
    Matrix cur = 1;
    b[0].num[1][m] = inf; //防止将b[0]算入
    int l = 0, lim = 0, r = 1;
    while (r <= n)
    {
        cur = cur * a[r];
        while (!check(b[l], cur))
        {
            l++;
            if (l > lim) // 当前栈中维护的从[l,lim]到lim的区间乘积值，l超过lim时就要重新计算
            {
            	//新的区间为[lim,r]到r
                b[r] = a[r];
                for (int i = r - 1; i > lim; i--)
                    b[i] = a[i] * b[i + 1]; //注意两者相乘的顺序，a要在b的前面，因为矩阵不满足交换律
                lim = r;
                cur = 1;
            }
        }
        ans = max(ans, r - l + 1);
        r++;
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}


    • 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

    1011-Link is as bear

    题目大意：
    给定一个序列，每次可以选择一个区间，使得区间内的数字变成区间的异或和。
    经过一定次数的操作后所有的数字可以变成相同的，求最后数字最大的值。

    思路：
    首先给出结论：答案就是从序列中取出任意数字进行异或。
    有了这个结论后直接套线性基的板子就行。
    这个结论更多还是靠猜，比赛的时候没必要推。
    下面是题解中给的证明：
    在这里插入图片描述
    AC代码：

    #include 
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 1e5 + 5;
using namespace std;

long long a[N], d[61];
void add(long long x) //插入线性基
{
    for (int i = 60; i >= 0; i--)
    {
        if (x & (1ll << i))
        {
            if (d[i])
                x ^= d[i];
            else
            {
                d[i] = x;
                break;
            }
        }
    }
}

void solve()
{
    int n;
    long long ans = 0;
    mem(d, 0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        add(a[i]);
    }
    for (int i = 60; i >= 0; i--)
        if ((ans ^ d[i]) > ans) ans ^= d[i];
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

    • 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
  • 相关阅读:
    技术分享 LINUX卸载oracle
    使用send给生成器注入数据
    【项目管理】PM vs PMO 18点区别
    Kafka架构和使用场景
    K_A02_003 基于单片机驱动8位数码管模块(MAX7219) 0-7静态显示+滚动显示
    Java经典面试题总结(附答案)-java经典面试题大全总结以及整理
    RabbitMQ原理(三)：发送者的可靠性
    java毕业设计宠物交易平台Mybatis+系统+数据库+调试部署
    【打卡】牛客网：BM37 二叉搜索树的最近公共祖先
    VS Code 远程连接 Jupyter
  • 原文地址：https://blog.csdn.net/Shanhj/article/details/126529278