URAL 1542. Autocompletion 字典树
2024-08-25 15:53:38
给你最多10w个单词和相应的频率 接下来最多1w5千次询问 每次输入一个字符串让你从前面的单词中依照频率从大到小输出最多10个以该字符串为前缀的单词
開始把单词建成了字典树 然后每次询问找到全部满足条件的单词 在排序输出 不是超时就是超内存 还来了一发数组越界
最后换方法 由于最多仅仅要输出前10个 那么能够把要询问的字符串建字典树 每一个结尾节点在做一个映射 存10个单词(当然仅仅是存下标)
然后再把单词依照频率从大到小排序一个一个插入字典序 满足有前缀是结尾节点就放进去
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxnode = 400110;
const int sigma_size = 26;
const int maxn = 100010;
const int maxm = 15010;
int ch[maxnode][sigma_size];
int val[maxnode];
int sz; struct word
{
int v;
char s[22];
}w[maxn]; char p[maxm][22];
int ans[maxm][12];
int sum[maxm], id[maxn];
bool cmp(word a, word b)
{
if(a.v != b.v)
return a.v > b.v;
return strcmp(a.s, b.s) < 0 ? 1 : 0;
}
void init()
{
sz = 1;
memset(ch[0], 0, sizeof(ch[0]));
memset(sum, 0, sizeof(sum));
} void insert(char *s, int v)
{
int u = 0, n = strlen(s);
for(int i = 0; i < n; i++)
{
int c = s[i] - 'a';
if(!ch[u][c])
{
memset(ch[sz], 0, sizeof(ch[sz]));
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] = v;
} void find(char *s, int v)
{
int n = strlen(s), u = 0;
for(int i = 0; i < n; i++)
{
int c = s[i]-'a';
if(!ch[u][c])
return;
u = ch[u][c];
if(val[u] && sum[val[u]] < 10)
{
ans[val[u]][sum[val[u]]] = v;
sum[val[u]]++;
}
}
} int main()
{
int n, m;
while(scanf("%d", &n) != EOF)
{
init();
for(int i = 0; i < n; i++)
{
int x;
scanf("%s %d", w[i].s, &w[i].v);
}
sort(w, w+n, cmp);
scanf("%d", &m);
for(int i = 0; i < m; i++)
{
scanf("%s", p[i]);
insert(p[i], i+1);
}
for(int i = 0; i < n; i++)
{
find(w[i].s, i);
}
for(int i = 0; i < m; i++)
{
int u = 0;
for(int j = 0; p[i][j]; j++)
u = ch[u][p[i][j]-'a'];
u = val[u];
if(i)
puts("");
for(int j = 0; j < sum[u]; j++)
printf("%s\n", w[ans[u][j]].s);
}
}
return 0;
}
最新文章
- Android公共title的应用
- Delphi基本类型--枚举 子界 集合 数组
- hdu 2120 Ice_cream&#39;s world I
- Grid分组汇总
- 检测iOS的APP性能的一些方法
- HDU 4509 湫湫系列故事——减肥记II(暴力模拟即可)
- linux网络编程笔记——UDP
- CSS的总结(选择器,伪类等...)
- Nginx 介绍和安装
- Delphi 3D Glscene安装
- 在配置wem.xml后,Tomcat遇到问题,启动失败的解决方法
- Error Handling in ASP.NET Core
- Android图表库MPAndroidChart(十四)——在ListView种使用相同的图表
- [easyUI] lazyload 懒加载
- OI回忆录第一章 逐梦之始
- spring data jpa在使用PostgreSQL表名大小写的问题解决
- Python常见问题系列
- Linux——系统引导流程学习简单笔记
- [转]VS 2010 : 如何开发和部署Outlook 2010插件(Add-in)
- 机器学习之利用KNN近邻算法预测数据
热门文章
- nls 字符编码文件对应的国家语言
- [NOI.AC#33]bst 线段树
- 43.c++指针类型转换
- php中 重载(二)
- 一起talk C栗子吧(第九十 三回:C语言实例--进程间通信之临界资源)
- 初识ThreadLocal
- ImportError: No module named tornado.ioloop 记录过程
- 终于研究出如何设置新版paypal付款时汇率损失方的问题了
- 指示函数(indicator function) 的作用
- 1.1 Introduction中 Kafka as a Messaging System官网剖析(博主推荐)