1WA + 5TLE 求助

P1054 [NOIP2005 提高组] 等价表达式

4TLE
by Catcats @ 2022-08-08 11:40:01


python其实效率不太高,TLE很正常。解释一下就是replace的时间复杂度是$O(n)$以上,甚至到$O(n^2)$,eval的效率也没那么高。 因此,这个程序实际的时间复杂度高达$O(n^2)$甚至$O(n^3)$,在大数据下会TLE。
by c_cpp_a @ 2022-08-08 11:51:11


@[Catcats](/user/658875) 所以能不用python就不用python,用的话算法也要优化。
by c_cpp_a @ 2022-08-08 11:52:22


@[c_cpp_a](/user/346332) 可是 $n\le26$ 哎
by Catcats @ 2022-08-08 11:53:31


@[Catcats](/user/658875) 但是每个字符串的长度$\le$50哎,一乘就知道真正的n是多少了,那才是程序处理的数据量。
by c_cpp_a @ 2022-08-08 11:55:58


26^3=17576确实在题目容忍的范围内,可是(26*50)^2=1690000就太大了,会超
by c_cpp_a @ 2022-08-08 11:58:44


|