| 题目名称 | 2623. [HZOI 2016][GDOI2016模拟3.14] hashit |
|---|---|
| 输入输出 | hahaha.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 半汪
于2017-03-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：35， 通过率：34.29% | ||||
 liumy |
100 | 0.086 s | 108.46 MiB | C++ |
 _Itachi |
100 | 0.270 s | 3.92 MiB | C++ |
|
6666 |
100 | 0.365 s | 3.18 MiB | C++ |
|
6666 |
100 | 0.369 s | 3.18 MiB | C++ |
|
6666 |
100 | 0.374 s | 3.18 MiB | C++ |
 半汪 |
100 | 0.376 s | 3.18 MiB | C++ |
|
半汪 |
100 | 0.412 s | 4.58 MiB | C++ |
|
6666 |
100 | 0.415 s | 3.18 MiB | C++ |
 小一米 |
100 | 0.425 s | 4.99 MiB | C++ |
 Lucida |
100 | 0.507 s | 3.18 MiB | C++ |
| 关于 hashit 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @FoolMike :
Mike就是强啊 半汪
2017-03-10 14:49
9楼
| ||||
|
set的比较真多！这让hash很尴尬啊
| ||||
|
回复 @AntiLeaf :
啊哦！好像假如你能够造出每次都让我删除根节点的数据，我的复杂度就渣了。。不过你事先不知道我的alpha是多少，除非捆绑评测然后每个点中加几个卡不同的alpha值的替罪羊的数据，否则也是卡不动的。 _Itachi
2017-03-08 08:00
7楼
| ||||
 AntiLeaf
2017-03-08 07:38
6楼
| ||||
|
回复 @半汪 :
我能说我替罪羊树是现学的,在做这道题之前只A过两遍普通平衡树,而且都是惰性删除的,强行YY勤勉删除再写出来真心很累啊！ _Itachi
2017-03-08 07:17
5楼
| ||||
|
回复 @_Itachi :
学Treap 半汪
2017-03-07 21:42
4楼
| ||||
|
写一颗勤勉删除+旋转的替罪羊是很痛苦的。。
_Itachi
2017-03-07 21:37
3楼
| ||||
|
| ||||
|
hash it?
has hit? ha shit?  splay
2017-03-02 18:56
1楼
| ||||
FoolMike2623. [HZOI 2016][GDOI2016模拟3.14] hashit
★★★ 输入文件：hahaha.in
输出文件：hahaha.out
简单对比时间限制：1 s 内存限制：128 MiB
【题目描述】
你有一个字符串S，一开始为空串，要求支持两种操作
1.在S后面加入字母c
2.删除S最后一个字母
现在有Q个操作，问每次操作后S有多少个不同的子串
Q<=1e5
【输入格式】
第一行输入一个M，表示操作个数
第二行给出一个长度为M的字符串，每个字符代表一次操作，如果为小写字母则表示在S后面插入该字母，如果是‘-’表示删除最后一个字母
【输出格式】
输出N个数，第i行表示第i次操作之后S有多少个不同的子串
【样例输入】
10 m-nk--z-p-
【样例输出】
1 0 1 3 1 0 1 0 1 0
【来源】
【GDOI 2016 模拟3.14】