A. 平滑数列
题目描述
我们定义一个正整数数列是平滑的当且仅当任意两个相邻元素的差 \(\le 1\)。
求长度为 \(N\) 的字典序第 \(K\) 小的平滑数列。
思路
首先我们做一个 \(dp\):求出长度为 \(i\) 的首项为 \(j\) 的平滑数列数量,这里 \(j\) 只用枚举到 \(i\) 就足够了,因为 \(j>i\) 的部分等于 \(dp_{i,i}\)。
接着我们从前往后一位一位地确定。我们枚举这一位上是什么数字,如果当前是最后一个数字 \(x\) 使得第一位数字 \(\le x\) 的方案数之和 \(\ge k\),则当前这一位显然为 \(x\)。如果枚举到了 \(N\) 还不满足,就用除法求解。并令 \(K\leftarrow K-(<x的方案数)\)。
时空复杂度均为 \(O(N^3)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 45;
int n;
ll k;
__int128 dp[MAXN][MAXN][2 * MAXN], sum[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
dp[i][1][i] = sum[i][1] = 1;
}
for(int x = 1; x <= n; ++x) {
for(int i = 2; i <= n; ++i) {
for(int j = 1; j <= 2 * n - 1; ++j) {
dp[x][i][j] = dp[x][i - 1][j];
if(j > 1) {
dp[x][i][j] += dp[x][i - 1][j - 1];
}
if(j < 2 * n - 1) {
dp[x][i][j] += dp[x][i - 1][j + 1];
}
sum[x][i] += dp[x][i][j];
}
}
}
k--;
ll last = 0;
for(int i = 1; i <= n; ++i) {
ll p = 0;
if(i == 1) {
for(int j = 1; j < n; ++j) {
if(sum[j][n - i + 1] <= k) {
k -= sum[j][n - i + 1];
}else {
p = j;
break;
}
}
}else {
for(ll j = last - 1; j <= last + 1; ++j) {
if(sum[min(0ll + n, j)][n - i + 1] <= k) {
k -= sum[min(0ll + n, j)][n - i + 1];
}else {
p = j;
break;
}
}
}
if(!p) {
cout << n + (ll)(k / sum[n][n - i + 1]) << " ";
last = n + (ll)(k / sum[n][n - i + 1]);
k %= sum[n][n - i + 1];
}else {
cout << p << " ";
last = p;
}
}
return 0;
}
C. 连接传送门
题目描述
给定一个字符串 \(S\),你要构造一个排列 \(p\),使得如果 \(p_i>i\) 那么必须满足 \(S_{p_i}=1\)。求方案数。
思路
令 \(dp_{i,j}\) 表示考虑前 \(i\) 个,其中有 \(j\) 个数的 \(p_k>i\) 且未确定的方案数。
每次转移到 \(i+1\) 时,位置 \(i+1\) 可以选择 \(p_{i+1}\le i+1或>i+1\),并且若 \(S_{i+1}=1\),之前还未确定的可以连向 \(i+1\)。
时空复杂度均为 \(O(N^2)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5005, MOD = 998244353;
int t, n, dp[MAXN][MAXN];
string s;
void Solve() {
cin >> s;
n = s.size(), s = ' ' + s;
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= i; ++j) {
dp[i][j] = 0;
}
}
dp[0][0] = 1;
for(int i = 0; i < n; ++i) {
for(int j = 0; j <= i; ++j) {
dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD;
dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * j % MOD) % MOD;
if(s[i + 1] == '1') {
dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * j % MOD) % MOD;
}
if(s[i + 1] == '1' && j) {
dp[i + 1][j - 1] = (dp[i + 1][j - 1] + 1ll * dp[i][j] * j % MOD * j % MOD) % MOD;
}
}
}
cout << dp[n][0] << "\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}
标签:24,数列,int,ll,2024,MAXN,初秋,using,dp
From: https://www.cnblogs.com/yaosicheng124/p/18439302