稠州常规赛18题解

· · 个人记录

T1括号画家

本题有暴力做法，就是枚举i,j，然后直接字符串是不是符合条件，但是这样子做显然时间复杂度比较高！

优化思路

容易想到利用栈进行匹配判断。
考虑其实这个字符串如果优美，其实只要看栈是否为空即可，那么我们可以用栈进行字符串匹配，那么我们只需要枚举i即可，因为在栈的处理中，完全可以不用考虑j的情况，那么时间复杂度就降低到了O(n^2)

优化思路2

本题可以考虑进行DP优化，我们记录上次匹配的点，然后下次遇到可以匹配的时候，只需要查询一下前置是否合法即可，这样子就可以进行合法的转移！时间复杂度O(n)

代码略

T2数阵K小值

思路1暴力

考虑直接生成数列，然后sort即可，期望40分

思路2二分

容易发现，每行通过i*j产生的序列都是单调的，那么我们可考虑二分答案。

左界为1 \times 1，右界为n \times m，那么我们二分一个mid,在n行单调的区间进行搜寻符合的值即可，其实查找个数非常简单，我们只需要数学计算一下即可！

因为当前的乘数m是知道的，乘积又是mid，那么被乘数x就可以计算得知，这里留给大家自行思考！

代码略

T3或表达式

思路

本题还是考察分治思想，我们考虑|,对于|，其实就是分段了，相当于每个|就是max分段结果即可！

对于括号，就像是多了一次计算即可！

代码

int dfs() {
    int ans = 0;
    while (cin >> c) {
        if (c == 'a')
            ans++;
        else if (c == '(')
            ans += change();
        else if (c == '|')
            return max(ans, change());
        else if (c == ')')
            return ans;
    }
    return ans;
}

T4集合等分

思路

容易看出，本题考察背包，因为在数字组成方案的时候，我们可以用01dfs，也可以用01背包来推方案数量。

划分集合的时候，我们发现1,2,5,6和3,4,7会重复计算到，如果我们暴力用二维背包，会MLE.

那么考虑优化，我们可以滚动进行压缩维度！

今天我们讲解第二种思路！

对于组合我们容易观察到，枚举出来的组合并不是任意两个进行配对的，也就是1,2,5,6是不能和1,6,7组合的，因为1不能用两次，那么也就是这个东西是互斥的，这个就是性质好玩的地方，我们考虑让dp[1]=1，让天平的左半边永远都有一个1，那么另外的一半就是剩下来的另外一半，也就是我们枚举的带有1的半数集合即可，至于另外的，我们根本不用枚举！

那么令dp[1]=1，for循环从2开始，我们就可以用一维的01背包来解决本次的题目了。

所以，我们去考虑问题的时候，请同学们务必想明白它的含义和由来，例如整数划分、数字组成类型的背包，其实包含了集合的含义在里面，希望大家能明白其背后的意义！

T5流浪猫

思路

本题是一个环形，容易想到破环成链，一般来说有两种方法，一种是复制一份，然后直接求解1到2 \times n即可。

另外如果1,n是互斥的，我们可以考虑分别处理1\to n-1和2\to n即可，本题用这种方法来做。

那么我们考虑在dp，因为可以喂两次，所以我们考虑1喂食的dp一次，然后1不喂食的dp一次即可！

代码

  dp[1][0] = INF;
    dp[1][1] = a[1];
    for (ll i = 2; i <= n; ++i) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    ans = min(dp[n][0], dp[n][1]);
    dp[1][0] = 0;
    dp[1][1] = INF;
    for (ll i = 2; i <= n; ++i) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i];
    }
    ans = min(ans, dp[n][1]);

T6 树上K路径

思路

考虑暴力，就是dfs出来一个点，然后深下去k，有多少条即可，如果是链条的数据，就可以卡住。

那么考虑如何优化，考虑dp[i][j]记录下i节点下，深度为j的路径数量，那么只需要考虑dp[i][j]的转移即可，对于最终对ans的贡献，只需要求解dp[rt][j]* dp[to][k - j - 1]即可，意思是父节点到这里长度为j的数量是多少，然后儿子节点下去的长度为k - j - 1数量，那么长度为k的路径数量自然是两者乘积

            for (int j = 0; j < k; j++)
                ans += dp[rt][j] * dp[to][k - j - 1];

接下来是第二个转移，这个转移还是比较清晰的，就是表示对于父节点rt来说，深度j+1的节点数量可以由儿子节点to深度+1转移而来。

            for (int j = 0; j < k; j++)
                dp[rt][j + 1] += dp[to][j];

当然本题可以有书上点分治的做法，这里不展开讲！

代码

void dfs(int rt, int fa) {
    dp[rt][0] = 1;
    for (auto to : G[rt]) {
        if (to != fa) {
            dfs(to, rt);
            for (int j = 0; j < k; j++)
                ans += dp[rt][j] * dp[to][k - j - 1];
            for (int j = 0; j < k; j++)
                dp[rt][j + 1] += dp[to][j];
        }
    }
}