2019安徽-省赛G题 括号序列


Problem

Portal


Meaning

求长度为n的合法括号序列集合中的的第m小序列.


Thoughts

开始我看到这道题, 首先我想到用爆搜枚举, 但2000长度的字符串显然是不行的, 排列组合2^2000分分钟破2e8. 对于这种NP问题(爆搜无法解决, 挨个枚举不行我们就想到一类一类的枚举 – dp优化), 我们考虑到dp, 那么这是我们需要考虑:

  1. 怎样定义dp数组表示状态
  2. 集合怎么样划分(答案可以由哪些子集合递推得到)
  3. 怎样递推(状态转移方程)

Solutions

  1. 对于长度为x的字符串, 它的所有组合, 我们可以这样划分, 长度为x的字符串中左括号比右括号多y (0 ~ x) 个的多个情况, 对于这多个情况每个情况都有多种全排列, 这些所有情况的集合就是长度为x的所有排列。我们用一个dp二维数组存储长度为x时左括号比右括号多y个时的左右括号相等(可以有的)合法的方案数, 比如: f[3][1] = 1, 如果加一个右括号可以凑成左右括号相等。
  2. 状态转移方程(根据最后一步的不同(加左括号还是右括号)划分长度为i的字符串类)
    对于f[i][j]相对于f[i – 1][j], 它多了一个字符, 所以相应f[i][j + 1] (加的是左括号) 和f[i][j – 1] (加的是右括号) 才是由f[i – 1][j]转移过来的, 而不是f[i][j]。 f[i][j + 1] = f[i – 1][j] (所有方案数加了个左括号) + f[i – 1][j + 2] (所有方案数加了个右括号)。
  3. 得出答案
    对于答案, 我们通过一直在前面加 ( , 如果当前的方案数比m大(那说明我们需要缩小范围), 我们就加一个 ( 符号(因为求第m小的嘛~)在答案中并将剩余点个数下降, 根据状态转移方程长度少的方案数一定小于等于长度大的方案数, 加1个 ( , 左括号比右括号就多了1, x + 1, y + 1, 加1个 ) , x + 1, y – 1, 同时m – f[x + 1][y + 1]即前x + 1个字符都为 ( 的所有方案字串大。加一个 ) 就代表第k小的k累加了一个方案数, 当m减为0时, 后面的就全部加 ( 是的它作为后面的最小, 即第m小.n - i个数 ( 比 ) 多 x 的话, 确定一个字符, 长度就 - 1, 那么n - i - 1个, 去掉前面确定的字符是 ( , 那么剩下的序列左括弧的数量就减少了一个, 那么 y – 1(左括弧的比右括弧多的数量 - 1), 去掉前面的 ) , 那就 y + 1。
  4. dp数组两维, 循环迭代两个维度, 时间复杂度 O(n^2)。2s, 4e6随便过))

Time complexity

$O(n^2)$


Accepted Code

#include <iostream>  
#include <algorithm>  

using namespace std; 

const int N = 2010;  

int n;  
long long dp[N][N], m;  
char ans[N]; 

int main() 
{      
    cin >>n >> m;  

    dp[0][0] = 1;  
    long long INF = 1e18 + 10;  
    for (int i = 1; i <= n; ++i)  
        for(int j = 0; j <= n; ++j)  
            if (dp[i - 1][j])   
            {
                dp[i][j + 1] += dp[i - 1][j];  
                dp[i][j + 1] = min(dp[i][j + 1], INF);
                if (j)  
                {

                    dp[i][j - 1] += dp[i - 1][j];  
                    dp[i][j - 1] = min(dp[i][j - 1], INF);  
                }
            }

    int now = 0;  
    for(int i = 1; i <= n; ++i) 
    {
        if (dp[n - i][now + 1] >= m) ans[i] = '(', ++now;  
        else ans[i] = ')', m -= dp[n - i][now + 1], --now;  
    }  
    puts(ans + 1);  
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
2019安徽-省赛J题 密信 2019安徽-省赛J题 密信
If you want to read this article, please go to About page, scan wechat or alipay QR code, pay 200 yuan and contact blogger through QQ, then you can get the passsword and read the article.
Next 
关于扶墙 关于扶墙
应用场景在互联网/广域网中, 有些ISP(互联网运营商 – 其实就是多个路由器集成的整体以及其自己的机房组成的)是无法互通的, 也就是我们计算机直连的ISP, 对于一些机房的ISP无法连通, 也就无法访问到该机房上的web服务, 这时我们就
2020-06-15
  TOC