欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019 上海网络赛 F. Rhyme scheme(dp + 线性构造)

程序员文章站 2022-04-27 11:35:50
...

2019 上海网络赛 F. Rhyme scheme(dp + 线性构造)
题目大意:用字符表示集合划分,例如 AABBA 表示 1,2,5划分一个集合,3,4划分一个集合,输入 n,k,用字母表示 n 个人的集合划分,输出字典序第 k 小的划分字符串。


集合划分的数目是一个贝尔数,观察到如果前 i 个人划分出了 k 个集合,第 i + 1 个人有 k + 1种选择,要么归属 k 个集合中的一个,要么划分到一个新的集合。一个人的可选择方案数量只和前面的集合数量有关,并且第一个人总是划分到A,因为 AB 和 BA是一样的解,那么第一个人总可以划分到A。那么可以画出一个每个人的划分选择解答树:
2019 上海网络赛 F. Rhyme scheme(dp + 线性构造)
可以沿着树dfs,用 dp 记录每个结点往下的方案数,更一般的,一个结点往下的方案数和当前这个点划分到哪个集合无关,而与这个点以及这个点之前所划分的集合数目有关。

接下来考虑沿着树链构造解,构造解的过程类似于树上二分的过程,当处于第一层的A结点时,考虑先往左儿子A结点走,若往左走方案数不够多,则往右儿子结点B走,且 询问数 - 左儿子方案数。

对于多叉树,依次从左往右遍历儿子即可,找到第一个可以往下走的儿子往下走。
(然后由于贝尔数第26项爆了 ll ,要用__int128,坑得一批)


代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
typedef __int128 int128;
__int128 dp[30][30][30];
inline __int128 read() {
 	__int128 x=0,f=1;
 	char ch=getchar();
 	while(ch<'0'||ch>'9') {
 		if(ch=='-')
 			f=-1;
 		ch=getchar();
 	}
 	while(ch>='0'&&ch<='9') {
 		x=x*10+ch-'0';
 		ch=getchar();
 	}
 	return x*f;
}
void print(__int128 x)
{
	if (!x) return ;
	if (x < 0) putchar('-'),x = -x;
	print(x / 10);
	putchar(x % 10 + '0');
}
__int128 dfs(int mx,int len,int cur) {
	if(cur == len) return dp[len][mx][cur] = 1;
	if(dp[len][mx][cur] != -1) return dp[len][mx][cur];
	__int128 & ans = dp[len][mx][cur] = 0;
	for(int i = 1; i <= min(mx + 1,26); i++) {
		if(i >= mx)
			ans += dfs(i,len,cur + 1);
		else 
			ans += dfs(mx,len,cur + 1);
	}
	return ans;
}
int t,n;
__int128 k;
int main() {
	memset(dp,-1,sizeof dp);
	for(int i = 1; i <= 26; i++)
		ll ans = dfs(1,i,1);
	scanf("%d",&t);
	int ca = 0;
	while(t--) {
		scanf("%d",&n);
		k = read();
		int lst = 1;
		printf("Case #%d: ",++ca);
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= lst + 1; j++) {
				int p = max(lst,j);
				if(dp[n][p][i] < k)
					k -= dp[n][p][i];
				else {
					putchar('A' + j - 1);
					lst = max(lst,p);
					break;
				}
			}
		}
		puts("");
	}
	return 0;
}