首页 > 其他分享 >2024初秋集训——提高组 #24

2024初秋集训——提高组 #24

时间:2024-09-29 11:37:14浏览次数:9  
标签:24 数列 int ll 2024 MAXN 初秋 using dp

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

相关文章

  • 史上最详细论文word排版格式指导规范保姆级教学(2024.9.28)!
    前言首先,每个学校的论文排版格式都是不太相同的,但大体上都是相似的。正常来说,论文的排版操作是十分枯燥并且重复的,但是word中的样式工具使得论文排版会变得容易。接下来我将以某个学校论文格式要求为例,进行论文格式排版的操作。全文一共有5500多字,你只需要辛苦一次将这......
  • Python量化分析2024年最新整理的免费获取股票数据接口集合以及API数据接口说明文档
    ​近一两年来,股票量化分析逐渐受到广泛关注。而作为这一领域的初学者,首先需要面对的挑战就是如何获取全面且准确的股票数据。因为无论是实时交易数据、历史交易记录、财务数据还是基本面信息,这些数据都是我们进行量化分析时不可或缺的宝贵资源。我们的核心任务是从这些数据......
  • 2024/9/29
    又是乌云明媚的一天。[ARC042A]掲示板本来想用两个容器分别维护修改元素和未修改元素,但是遇到有重复操作的元素时会假。看样例发现是把操作倒着输出,遇到重复元素就输出第一次出现的,其余先不管,用一个桶标记一下,最后一并输出。因为元素和下标书写错误WA了一发。点击查看代......
  • 2024.9.29 计划
    项目学习ROS第三章背包问题求具体方案能量石金明的预算方案(有依赖的背包问题)总结......
  • 使用 Anchor 和 QuickNode 在 Solana 上创建NFT: 2024 版指南
    gg欢迎来到本教程。今天,我们将使用 SolanaPlayground、QuickNode RPC和一个IPFS服务,在Anchor/Rust中创建一个Solana程序,以直接在链上铸造NFT。作为预备步骤,我们将在去中心化存储服务中准备我们的NFT图像和元数据。我们将使用QuickNode IPFS,这是一个IPFS存储......
  • 【2024计算机毕业设计】基于jsp+mysql的JSP酒店预定管理系统
    运行环境:最好是javajdk1.8,我在这个平台上运行的。其他版本理论上也可以。IDE环境:Eclipse,Myeclipse,IDEA或者SpringToolSuite都可以,如果编译器的版本太低,需要升级下编译器,不要弄太低的版本tomcat服务器环境:Tomcat7.x,8.x,9.x版本均可操作系统环境:WindowsXP/7......
  • 【2024计算机毕业设计】基于JSP酒店预定管理系统
    运行环境:最好是javajdk1.8,我在这个平台上运行的。其他版本理论上也可以。IDE环境:Eclipse,Myeclipse,IDEA或者SpringToolSuite都可以,如果编译器的版本太低,需要升级下编译器,不要弄太低的版本tomcat服务器环境:Tomcat7.x,8.x,9.x版本均可操作系统环境:WindowsXP/7......
  • 【2024-09-28】连岳摘抄
    23:59吾日三省吾身:为人谋而不忠乎?与朋友交而不信乎?传不习乎?                                              ——《论语》人生,并不是追求天天做选择,事事做选择。选择伴随着混......
  • 迅雷加速器兑换口令2024最新免费会员
    对于热爱游戏的玩家来说,网络延迟和卡顿无疑是游戏体验的致命伤。迅雷加速器以其专业和高效的服务,为全球游戏爱好者提供了解决方案。现在,新用户有机会免费领取迅雷加速器的VIP会员,享受长达7+30天的加速服务。以下是详细的领取攻略:领取7天免费会员领取7天免费会员的步骤非常简......
  • 【2024-09-27】时常陪伴
    20:00我们要用自己的腿去走路,我们要用自己的双手去劳动,我们要说出自己的思想。                                              ——拉尔夫沃尔多·爱默生现在没能陪何太上下......