事实再次向我证明了RP的重要性。。。
第一题:进制转换
是我最没有把握AC的一道题目却是我唯一一道AC的题目,真是讽刺。看完题目几乎完全没有往正常的解法(取余倒序)去想,直接写了搜索,因为数据范围在2^16,感觉枚举每一位上的数应该就够了,但是在自己的电脑上连样例都用了3、4s,然后想不到任何有效的剪枝,就果断放弃了。最后写完其他三题之后还是回过头看了下这道题,还是没往正常的解法想。。。。结果惊人地AC了。。。RP真的太重要了。
然后经提醒终于想到了正常一点的解法,查了网上的题解之后开始自己写取余,结果犯了一个很逗的错误。。。关于负数的整除取余,C++是无法得到正确的答案的,需要进行处理。比如(-15)÷(-2),在C++里得到的是7...-1,而正确答案应该是8...1,然后。。我就很想当然地给余数加了个绝对值。。真是不能逗比更多。
事实上,当a和b都是负数时,假设a÷b=c...d是实际情况,而计算机得到的应该是a÷b=(c-1)...(d-b),所以应该对所得的商加上1,对所得余数加上b。
第二题:最大乘积
动规。f(i,j)表示在前i个数字中插入j个乘号。
f(i,j)=f(i-k,j-1)+s(i-k+1,i)
s(i,j)表示截取该数字从i到j的子串。
因为循环的边界写错所以WA了几次。
第三题:单词接龙
否决了动规,直接用搜索。对于两个字符串之间预处理他们拼接后字符串长度的增加量。然后深搜。
对于出题人的语文水平真的无力吐槽,歧义太多。首先,题目说“相邻的两部分不能存在包含关系,例如at和atide间不能相连“,这里可以有两种理解:1.相邻的两个字符串不能有包含关系 2.相邻的两个字符串拼接后的长度不能不发生变化,即at和atide这个例子。更坑爹的是一个字符串居然可以与自己相连!按照正常的思维,一个字符串当然是自己的子串了。于是WA了几次。但事实上样例的Hint里出现了tact+tact=tactact的结构,所以只能怪自己题目没看清。。。还有就是,ababa+ababa=ababababa。。。题目应该明确指出重叠部分应尽量小啊!做完此题RP已尽。。。
第四题:方格取数
在杭州讲过的动规,结果还是WA了。。。不能感动更多。。。
理解成两个人同时走,用f(i,j,k)表示两人都走了i步,且两人的横坐标为j和k。
但是弄错了一点:j并非不能等于k,只是j=k时两人相遇的格子上的数只能由一个人取得。
f(i,j,k)=max(f(i-1,j-1,k),f(i-1,j,k-1),f(i-1,j-1,k-1),f(i-1,j,k))+两人各自所在格点的数字
第一次提交时280分感动地滚粗。