[其他] [編輯][高一排名賽-2015] 賽前測試題解

[複製鏈接]

visitorIKC

TA的每日心情

	開心 2015-6-17 11:50

簽到天數: 177 天

[LV.7]常住居民III

15 主題	315 帖子	1437 積分

金牌會員

Rank: 6 Rank: 6

積分: 1437

發消息

樓主

發表於 2015-5-20 20:59:31 | 顯示全部樓層

本帖最後由 visitorIKC 於 2015-5-20 21:48 編輯

第三題另解

直接hash所有後綴
就可以O(1) 得知某個後綴有無出現

對每個Query
枚舉前綴
直接查詢後綴存不存在
複雜度 O(TcNQ)

實作直接用lookup Table
MLE - 10/100

若改用std::map(複雜度退化)
TLE - 10/100

用Array,再快樂的作一些優化
AC - 100/100

成功AC ^_^
到目前為止還沒有被Challenge掉 : )
XXXXXXD