19年安徽省赛G. 括号序列
本帖最后由 MFwxy 于 2020-6-14 16:18 编辑G. 括号序列
描述
括号序列是指由‘(’和‘)’组成的序列，假如一个括号序列中，包含相同数量的左括 号和右括号，并且对于每一个右括号，在他的左侧都有左括号和他匹配，则这个 括号序列就是一个合法括号序列。比如(())()就是一个合法括号序列，但 (())(()不是合法括号序列。
给出两个长度相同的合法括号序列A 和B，那么A < B当且仅当：
A 和B至少有一位不相同。
在A 和B从左往右数第一个不相同的位置i，A=(，B=)
比如A = (())()，B = ()()()，则A < B，因为从左边数第一个不相同的 是第二个字符，A = (,B = )。对于长度 N，由于定义了小于关系， 则可以通过这个关系推出所有长度为 N 的合法括号序列的大小关系，对于长度 为6的合法括号序列，从小到大排列顺序如下：
1.((()))
2.(()())
3.(())()
4.()(())
5.()()()
给出N和M，求长度为N的合法括号序列中，第M 小的合法括号序列是？
输入
输入的第一行是N 和M
2 <= N <= 2000
1 <= M <= 10^18
输出格式
输出一个字符串，表示长度为N的平衡括号序列从小到大排列，序号为M的字符串
样例输入
6 2
样例输出
(()())
解：。。。
一开始的思路是投机倒把（确实方便理解，但是效果不明显，不呈现了）
想把右括号根据它所在位置数字化，的确能做到给定括号序列判断他们的正确性以及大小，但是反向输出好像有点难。。。就放弃了
然后想通过左右括号交错的位置来整活，好像结果也不是很理想。
然后正常的去考虑动态规划。
大佬指点：
a：
dp算下吧
算出每个长度的括号序列有多少个
然后一个一个就推出来了
超过1e18就扔了
当做正无穷
因为只问前1e18项
反正后面也不算简单
大概就是看看最前面能放几个左括号
反正就是要算每一步怎么走
走完之后还要找多少个比这个小的路径
可能记忆化搜索更好写
也可以算我说的那个加组合数
差不多吧
记忆化搜索慢点儿
不过这个无所谓
b：
n^2dp
看看當前選（幾種路,）幾種路
你可以想成是對角線下的路徑
要在爆long long前變成inf
c：
括号这个好像是Catalan数
dp数组是什么？
动态规划是通过找当前项和前一或几项或后一或几项的关系,从而对一个数组多次利用达到减少复杂度。
1.当一串数可以不限次利用时，采用顺序的方式循环：for(j=0;j<=max_n;j++)（一维数组）或者加一个for(k=0;k*A<=j;k++)(二维数组)
2.当一串数的使用次数有限时用for(k=0;k*A<=j&&k<=B;k++)(二维数组)
3.当一串数的使用次数为一时，用倒序的方式循环：for(j=max_n;j>=0;j–)(一维数组),或者for(j=0;j<=max_n;j++)(二维数组)；或者另外开一个一维数组，用来每i一次就记录一次这个数组，格式一次前一个数组。
其实应该可以说明之前的树形图递归生成的想法是有可行性的
继续扒一扒dp算法和卡特兰数。。
大致结果：
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 2010;
int n;
ll f, k;
char ans;
int main() {
cin>>n>>k;
f = 1;
ll INF = 1e18 + 10;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= n; ++j) if (f) {
f += f;
f = min(f, INF);
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
cout << f << " ";
}
cout << endl;
}
if (j) f += f;
if (j) f = min(f, INF);
cout << endl;
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
cout << f << " ";
}
cout << endl;
}
cout << endl;
}
int n2 = 0;
cout << endl;
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
cout << f<<" ";
}
cout << endl;
}
for (int i = 1; i <= n; ++i) {
if (f >= k)
ans = '(', ++n2;
else
ans = ')', k -= f, --n2;
}
puts(ans + 1);
}
VS2017
括号变换原理还是不太懂 TL;DR
页:
[1]