拼多多 2020校招 多多的电子字典(字典树前缀搜索,DP)

news/2024/10/31 5:28:08/

多多鸡打算造一本自己的电子字典,里面的所有单词都只由a和b组成。
每个单词的组成里a的数量不能超过N个且b的数量不能超过M个。
多多鸡的幸运数字是K,它打算把所有满足条件的单词里的字典序第K小的单词找出来,作为字典的封面。

解题思路:

首先,答案最终的输出为上面这棵字典树的先序输出第k次。当然这棵树的a.b数量不能超过题目给的a,b数量。我们在先序输出的时候可以判断它的左子树的节点数是否小于k,是的话,我们左子树就可以不访问了。为此我们需要计算一个量dp[n][m][sta];当sta == 0时,表示当前我们在'a'节点上,而且总共有n个a节点,m个b节点,注意包含自己。那么有如下转移公式:

dp[n][m][sta]=1;if(!sta){dp[n][m][sta]+=((n>1)?dfs1(n-1,m,0):0) +((m>0)?dfs1(n-1,m,1):0);}else dp[n][m][sta]+=((n>0)?dfs1(n,m-1,0):0)+((m-1>0)?dfs1(n,m-1,1):0);

比较有疑惑的地方可能是为什么用了问号进行判断,因为我们的状态中要转移到下一个节点,必须保证那个节点还剩下。比如:我们不能转移到dp[n][m][sta];其中假设 n==0,sta == 0; sta==0 代表这是一个1节点,所以n>=1。这是一个无效的状态

完整代码:

#include <bits/stdc++.h>
#define int unsigned long long 
using namespace std;
vector<vector<vector<int>>> dp;
const int FLAG=1E18;
int  dfs1(int n,int m,int sta){if(n==0 && m==0)return dp[n][m][sta] = 0;if(dp[n][m][sta]!=FLAG)return dp[n][m][sta];if(sta == 2){ dp[n][m][sta] = 0;dp[n][m][sta] = ((m>0)?dfs1(n,m,1):0);dp[n][m][sta]=  ((n>0)?dfs1(n,m,0):0);return dp[n][m][sta];}dp[n][m][sta]=1;if(!sta){dp[n][m][sta]+=((n>1)?dfs1(n-1,m,0):0) +((m>0)?dfs1(n-1,m,1):0);}else dp[n][m][sta]+=((n>0)?dfs1(n,m-1,0):0)+((m-1>0)?dfs1(n,m-1,1):0);return dp[n][m][sta];
}
string ans="";
void dfs2(int n,int m,int sta,int k,char t){ans+=t;k--;if(k==0)return;if(!sta){if(n>1 && dp[n-1][m][0]>=k)dfs2(n-1,m,sta,k,'a');else dfs2(n-1,m,!sta,k- ((n>1)?dp[n-1][m][sta]:0),'b');}else {if(n>=1 && dp[n][m-1][0]>=k)dfs2(n,m-1,!sta,k,'a');else dfs2(n,m-1,sta,k- ((n>=1)?dp[n][m-1][!sta]:0 ),'b');}
}
int32_t main(){int n,m,k;cin>>n>>m>>k;dp.assign(n+1,vector<vector<int>> (m+1,vector<int>(3,FLAG)));dfs1(n,m,2);cerr<<dp[n][m][1]<<" "<<dp[n][m][0]<<endl;if(dp[n][m][0]>=k)dfs2(n,m,0,k,'a');else dfs2(n,m,1,k-dp[n][m][0],'b');cout<<ans<<endl;return 0;
}

 


http://www.ppmy.cn/news/276666.html

相关文章

使用TS装饰器从0封装一个socket.io服务器

背景 最近沉迷WebRTC技术&#xff0c;想用WebRTC试做一个快启动的文件传输PWA应用。涉及到使用websocket服务器传输WebRTC的信令&#xff0c;全栈的话自然是选择Nodejs做服务器了。 选型 因为项目体量肯定不是很大&#xff0c;所以所有选型都以高性能轻量为主要目标。前端选择…

Mybatis面试题

Mybatis常见面试题 #{}和${}的区别是什么&#xff1f; {}和${}的区别是什么&#xff1f; 在Mybatis中&#xff0c;有两种占位符 #{}解析传递进来的参数数据${}对传递进来的参数原样拼接在SQL中#{}是预编译处理&#xff0c;${}是字符串替换。使用#{}可以有效的防止SQL注入&…

新版本踩坑记录:SpringBoot2.3.x整合ElasticSearch7.6.x(ElasticsearchRestTemplate)包含类型转换踩坑

使用ElasticSearch7.6.x 的时候&#xff0c;和7之前的版本有很大的不同&#xff0c;下面列举了一些踩坑记录&#xff1a;eg &#xff1a;StringTerms 类型转换失败问题&#xff0c;聚合查询自动拆分搜索关键字问题…等等&#xff08;之后出现问题还会回头补坑&#xff09; 聚合…

观念 信仰的价格

转 观念 信仰的价格 观念 信仰的价格 要点&#xff1a;在社会上&#xff0c;有很多关于怎样训练创造力的讨论&#xff0c;而很少有人去讨论人为什么去创造。本问引入一个新的单位PH&#xff08;幸福值&#xff09;&#xff0c;来统一经济利润最大化和精神价值追求者之间的分歧…

一周总结: 2020.3.2-2020.3.8

所有资料来源于网络&#xff0c;非原创 1.mysql 1对多查询 分页&#xff0c;并且用多表字段对查询结果表进行排序 分页暂时无法实现&#xff0c;在数据库进行分页&#xff0c;返回由mybatis对结果进行处理&#xff0c;多的映射为list集合 2.MySQL 取分组后每组的最新创建的记…

Debezium系列之:同一张表的数据始终进入Kafka Topic的相同分区,同时表结构变化的DDL事件也发送到相同分区

Debezium系列之:同一张表的数据始终进入Kafka Topic的相同分区,同时表结构变化的DDL事件也发送到相同分区 一、需求背景二、实现思路三、核心参数和参数详解四、创建表五、提交Debezium Connector六、插入数据,并消费Topic七、修改表结构,消费Topic八、再次插入数据,消费T…

为什么当贝F3依然是家用投影仪性价比之王 有哪些惊艳之处

最近在网上4G冲浪时&#xff0c;看到许多网友对于家用投影仪当贝F3的宠爱&#xff0c;都觉得当贝F3是家用投影仪界的性价比之王。但是也有网友在评论下发问在如今新品众多的情况下&#xff0c;当贝F3是如何稳坐性价比之王的宝座的&#xff1f;那么今天小编就来和大家说说为什么…

为什么 Mac 适合编程?

强劲的 GPU 和 CPU。我的家用电脑和笔记本都配了顶级的显示器和 GPU。Steam 上有 2000 游戏&#xff0c;我和孩子玩了很多&#xff0c;并且我对 CUDA 和 深度学习很感兴趣。而 Mac 对此就无能为力了。对我来说&#xff0c;强大的 GPU 是非常重要的&#xff0c;所以我配了一台搭…