2021年寒假热身赛 5

2021年寒假热身赛 5

踏莎行·候馆梅残

[宋]欧阳修

候馆梅残,溪桥柳细。
草薰风暖摇征辔。
离愁渐远渐无穷,迢迢不断如春水。

寸寸柔肠,盈盈粉泪。
楼高莫近危阑倚。
平芜尽处是春山,行人更在春山外。

# 未完成,简单说说思路

A. 进位制变换

由于数字最多1000位,并且可能是36进制,所以要自己编写运算。用字符串表示数字,实现字符串与数字的整除与取模运算即可。

B. 乘积为整数

小数点后可能有9位,那么两个小数点后都是9位的数字相乘则精度会超过double允许的类型,所以可以将小数转化为分数 .

因为从小数化为分数,分数的分母都是从\( 10^L \)开始,并可能被约分,最后分母只剩\(2^a5^b\)的形式,也就是说如果要将一个数字的分母\( 2^a⋅5^b\)约去,只需要看这个数字的分子与另一个数字的分子之积是否含有\(2^a⋅5^b\)的因子,其它的因子都不会有影响 。

这样,在本题中,我们将每个数字用\( (a,b) \) 描述,对应于\( 2^a⋅5^b\)。若两数相乘为整数,则两数 \(2^a⋅5^b\) 与 \(2^c⋅5^d\)的乘积是 \(2^{a+c}⋅5^{b+d}\),即\( (a+c,b+d) \) ,若有\( a+c≥0 \)  and \( b+d≥0\) ,则两数之积为整数。

C. 蛤蟆吐球消消乐

按题意说的做就行。本题进行插入和删除操作,就可以利用C++ STL的vector实现。

参考代码(C++)

D. 楼高莫近危阑倚

先DFS找到树根(唯一没有父结点的那个)。然后维护一个树状数组,或者线段树,则在\( O(N \log(N)) \)的时间内解决。

E. TA也超级加倍?

\( \lceil \frac{N}{2^a3^b5^c} \rceil \) 和 \( \lfloor \frac{N}{2^a3^b5^c} \rfloor \)

F. 上下文无关文法

动态规划

发表评论

电子邮件地址不会被公开。 必填项已用*标注