fzyz校内训练20200904

· · 个人记录

作为一个提高组知识尚未完备的蒟蒻，今年打的第一场提高组模拟赛，算是正常发挥吧……rank\ 14/41

T1

Problem

看到这题第一反应就是模拟，关键是怎么模拟

一开始想到的是直接把两个数转成long\ long型的，然后进行乘法运算

但是，单纯这么做乘完的结果会超出long\ long的范围

于是便换了一种思路：把每个数转成最简分数，然后看能否约分成整数

这样做正确性显然，而时间复杂度O(n^2)只能拿到40pts

（本人考场上就是这么打的）

Code

正解如下：

先把所有数转化成以10^9为分母的分数，这样在两个数相乘的时候只需要考虑分子相乘是否为10^{18}的倍数即可

再仔细一想，考虑每个分子，将其转化成2^α·5^β·t的形式，将两个数a_i和a_j相乘时只需满足α_i+α_j≥18,\ β_i+β_j≥18即可

其中的α_i,\ β_i的情况数可以用桶存

照着这个思路打就是正解

Code

（但是，Linshey用主席树过了这道题……）

T2

Problem

这题似乎是本场最容易想的题（本人考场上差判个收敛就A了……

思路没什么特别的，就是模拟加上一个差分优化

本来想着时间复杂度是O(nk)能卡过60pts

结果挂了20pts

（悲剧……

Code

正解就是在上述代码中加个判收敛，时间复杂度就趋近于O(k\log{n})

Code

T3

Problem

考场上想的思路和正解几乎一样？！

只是没想到Trie怎么用……

思路其实就是模拟+找规律

对于一个字符串S而言，只需要考虑一个字符+在这个字符之后的一段后缀是否构成字符串T

考场上想到的是直接枚举，复杂度O(n^2|S|)

结果玄学的卡过了两个点

后面讲评的时候，说第6个点数据错了，然后几乎所有50pts的都加了10pts

而我就成了全场唯一一个50pts的……？

Code

正解就是把每个字符串倒插入字典树，然后对于每个字符串而言，只要统计它能够从多少个字符串得到即可

Code