首页 > 其他分享 >题解:P7475 「C.E.L.U-02」简易输入法

题解:P7475 「C.E.L.U-02」简易输入法

时间:2024-08-25 21:05:28浏览次数:12  
标签:02 node 输入法 ch string insert int 题解 tr

题意

给定词典 \(\text{U}\),每次询问读入一个字符串 \(s\),以及一个整数 \(x\) 对于这个字符串有以下几种情形:

设\(s_i \in \text{U}\) 且 \(s\) 为 \(s_i\) 的前缀的个数为 \(a\)。

当 \(a\ge x\) 时,请输出按照以输出次数从大到小为第一关键字,以字典序为第二关键字排序后的第 \(x\) 个 \(s_i\),并将其输出次数加 \(1\)。

当 \(x>a>0\) 时,请输出按照以输出次数从大到小为第一关键字,以字典序为第二关键字排序后的最后一个 \(s_i\),并将其输出次数加 \(1\)。

当 \(a=0\) 时,输出 404Error

分析

前缀相关的统计操作,考虑使用 Trie。

带修改查询第 \(x\) 大,考虑使用平衡树。

在每个 Trie 节点上维护一棵平衡树,维护所有包含该前缀的 \(s_i\) 以及该串输出次数。

因为 \(|s_i|\leq 10\),所以修改的时候直接模拟插入过程暴力修改每个节点上的平衡树的值。

查询的时候在尾节点上询问即可。

时间复杂度 \(O((n+q)|s|\log n)\)。

Code

因为不想重载运算符所以维护的是输出次数的相反数。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

struct node
{
    node* ch[26];
    tree<pair<int, string>, null_type, less<pair<int, string>>, 
         rb_tree_tag, tree_order_statistics_node_update> tr;
    node() {memset(ch, 0, sizeof ch);}
}*rt=new node;
unordered_map<string, int> mpt;

void insert(string s)
{
    node *x=rt;
    for(auto c:s)
    {
        x->tr.insert({0, s});
        if(!x->ch[c-'a']) x->ch[c-'a']=new node;
        x=x->ch[c-'a'];
    }
    x->tr.insert({0, s});
    mpt[s]=0;
}

void modify(string s)
{
    node *x=rt;
    int v=mpt[s];
    for(auto c:s)
    {
        x->tr.erase({v, s});
        x->tr.insert({v-1, s});
        x=x->ch[c-'a'];
    }
    x->tr.erase({v, s});
    x->tr.insert({v-1, s});
    mpt[s]--;
}

string query(string s, int v)
{
    node *x=rt;
    for(auto c:s)
    {
        if(!x->ch[c-'a']) return "404Error";
        x=x->ch[c-'a'];
    }
    string p=x->tr.find_by_order(min(v, (int)x->tr.size())-1)->second;
    modify(p);
    return p;
}

int main()
{
    int n, t, x;
    string p;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p, insert(p);
    cin>>t;
    while(t--)  cin>>p>>x, cout<<query(p, x)<<'\n';
}

标签:02,node,输入法,ch,string,insert,int,题解,tr
From: https://www.cnblogs.com/redacted-area/p/18379560

相关文章

  • 题解:P7401 [COCI2020-2021#5] Planine
    题意现有一座上下起伏的山。它可以抽象为一个包含\(n\)(\(n\)为奇数)个点\((x_i,y_i)\)以及\((x_1,-\inf)\)与\((x_n,-\inf)\)的多边形。对于所有满足\(i\neq1\),\(i\neqn\),\(i\bmod2=1\)的整数\(i\),\((x_i,y_i)\)都是山谷。现要放置若干个高度为\(h\)的点光......
  • 题解:SP1182 SORTBIT - Sorted bit squence
    题意将区间\([m,n]\)的所有整数按照其二进制位表示的数中\(1\)的数量从小到大排序。如果\(1\)的数量相同,则按照数的大小排序。求序列中第\(k\)个数。其中,负数使用补码来表示:一个负数的二进制数与其相反数的二进制数之和恰好等于\(2^{32}\)。分析考虑用uint32_t存......
  • 题解:P3266 [JLOI2015] 骗我呢
    题意有一个\(n\timesm\)的数组\(x_{i,j}(1\lei\len,1\lej\lem)\),满足:\(x_{i,j}\in[0,m]\)\(\foralli\in[1,n],\forallj\in[1,m),x_{i,j}<x_{i,j+1}\)\(\foralli\in(1,n],\forallj\in[1,m),x_{i,j}<x_{i-1,j+1}\)......
  • 题解:CF70D Professor's task
    题意实现以下两种操作:往点集\(S\)中添加一个点\((x,y)\)。询问点\((x,y)\)是否在点集\(S\)的凸包中。分析动态凸包板子。建议先完成P2521[HAOI2011]防线修建。上题维护的是上半个凸包,本题维护上下两个。将凸包中的点按\(x\)排序,通过\((x,y)\)前驱......
  • 题解:P2521 [HAOI2011] 防线修建
    题意给定若干个点,实现下列操作:删除一个点。查询上凸包的周长。分析建议先完成【模板】二维凸包。对于这个删除操作,我们没有好的方法去在线维护它。考虑离线询问。这样删除操作就变成了插入操作。插入一个新点有如下两种情况:新点在凸包内。新点在凸包外。我们回忆......
  • 题解:CF235C Cyclical Quest
    题意给定一个主串\(S\)和\(n\)个询问串,求每个询问串的所有循环同构在主串中出现的次数总和。分析后缀自动机好题。循环同构的过程可以看作从该串的头部删除一个字符,并在尾部加入一个字符。在后缀自动机上,跳parent树的过程就相当于删除头部的若干个字符。所以我们可......
  • 7z解压crc错误_7-Zip - 常见问题解答
    7z解压crc错误_7-Zip-常见问题解答7z解压crc错误_7-Zip-常见问题解答1.引言1.17-Zip简介1.2CRC错误概述2.7z文件和CRC错误2.1什么是7z文件2.2CRC错误的定义2.3CRC错误对文件的影响3.常见原因分析3.1文件传输过程中的错误3.2存储介质的损坏3.3不兼容的压......
  • 题解:P5680 [GZOI2017] 共享单车
    题目分析出题人是擅长隐藏题意的建树首先给你一张无向图,然后指定一个根节点\(k\),从根节点开始沿最短路到每一个节点。如果到某个节点有多条最短路径,选择上一个节点编号最短的。考虑记录前驱的Dijkstra。namespaceDJ{intdis[maxn],pre[maxn],val[maxn],vis[maxn]......
  • [20240824]利用gdb抽取kglnaobj内容.txt
    [20240824]利用gdb抽取kglnaobj内容.txt--//上午测试跟踪librarycachelocklibrarycachepin使用gdb,利用handleaddreess+0x1c8偏移可以取出kglnaobj内容.--//灵光一现,是否可以直接通过gdb抽取kglnaobj内容,新的gdb版本支持管道操作,在测试环境尝试一下.--//千万不要在生产系......
  • [20240824]跟踪library cache lock library cache pin使用gdb.txt
    [20240824]跟踪librarycachelocklibrarycachepin使用gdb.txt--//这几天一直想写一个gdb脚本实现这个功能,先开始自己尝试,遇到一些问题,冷静下来看了以前的学习笔记,网上查了相关链接,能找到--//的资源很少:--//https://nenadnoveljic.com/blog/tracing-library-cache-locks/......