noip2000提高组题解

事实再次向我证明了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分感动地滚粗。

上一篇:pyobjc-framework-Cocoa 5.1.2


下一篇:bzoj 3207 花神的嘲讽计划Ⅰ(哈希法+主席树)