topcoder srm 488 codefor

topcoder srm 488 codefor topcoder srm 488 codefor topcoder srm 488&codeforces beta round 412010-11-21 07:18这次两个srm隔的很近，还收到了codeforces的比赛通知。感觉生活一下充实了不少，真实令人兴奋，以至于当天我连一科第二天要交的作业都没写。 codeforces的比赛时间后来才知道可能是欧洲时间，于是就错过了。但就算知道，也是有课没法参加，后来我是作为练习参加的。先说srm 488，我的目标是通过前两，于是一上来还是打开了500分的题，题目很直接，就是两个字符串各取出两个字串，拼成两个一样的，返回这样能拼成的最长的。我于是就直接八重循环了。测试的时候发觉很慢，连样例都过不了，就想办法优化。其实在最里面加了长度相等再比较的优化之后，对于随机的长度为15的两个串已经能在1s左右出来，但我的思维还是受poj的影响，总觉得要控制在1s以内，其实topcoder的case时限应该是两秒。我于是浪费了大量时间在这上面，但其它边角的改动其实并没有多大的改善。第一题更容易，以至于都没什么可说的，我虽然还是做麻烦了一点，不过还是有240分以上。当时还挺高兴。我还打开第三题，想在结束之前提交一个，但没成功。coding结束后，我居然在room排第一，这次参加的人好像挺少，普遍水平可能低些，我一定非常激动，然后，悲剧就开始了。先是500p被cha了，事后我发觉我少看了一个条件，如果有相等长度的符合条件的串，返回最小的那个～后来在practice room提交了下，果然是加了这个判断就过了。到底英语不是母语，不过看来这题最暴力的还是可以的，我一时也想不出有什么更简洁的方法。cha我得那个人就是后来的room leader，但他的500p也fail了，他的方法我看了看没明白，就作罢了。如果是这样，凭借还比较快的第一题，应该结果不算太糟，但最最最最悲剧的是我的250pfail了～我是room唯一一个fail这题的，我于是一下落到了最后，其实这题最短的程序不到十行，我的方法当然也没问题，但数组开小了，n和m都是1-47，我于是就开了50的数组，但应该是开n+m大小才对。于是我就彻底悲剧了，rating降了不少，变灰了。后来我把1000p实现了提交了一下，果然超时，我使用的搜索的办法。后来看别人的代码应该可以有分析的办法，但当时还没人过这题，我cha了两个人的代码，有些小漏洞，但我受到些启发，感觉他们那样思路还是对的，等有时间再做一下。这次比赛说明欠 缺还非常多，经验也不够丰富，看来我还是每到div1的水平，只好在div2再磨练一阵了，也好。 codeforce真正的比赛上午就结束了，我作为练习参加了，结果前两题都很水，一个小时之内就过了(已经挺慢了)，第三个题是一个环上有四个整数，操作是相邻的都加1或都除以2，要把四个数都弄成1，然后输出一种步骤。思维还是不给力啊，又加上漏看了条件(又漏看了。)，以为4个弄成相等的就行，所以走了好多弯路，最后也没想到最简的办法，但总算是编出来了。看了别人hack的数据，才发觉1 11 2这组数据需要单独处理，加上这个还不过，才发觉漏看了条件。其实思路就是先把三个弄成1，再处理最后一个。很容易想到能把两个弄成1，第三个我当时没想清楚，用了有点绕的办法，还判断了不可能的情况，但测试中发觉总能出结果，于是就猜测总是有解。后来陈轩提到了弄出第三个1的办法，其实挺直接，思维还是不够敏锐。第四题是在srm之后做的，是一个完全图的所有哈密顿回路的总权值相同，让构造出一个这样的图的邻接矩阵。一上来完全没思路，后来跟陈轩讨论。当时我想到路径上任意相邻两点互换应该依然满足条件，于是邻接矩阵任意两行的相同位置的两点的差应该相等，列也一样，但当时缺乏进一步的转化。然后我看了hack的一个样例，得到了一个解的局部，然后就揣测思路。后来在讨论中进一步想到上述条件等于是对任意子矩阵的四个角上的元素，知道了三个就能确定第四个，于是就有了点构造的依据。当时我想由于矩阵是对称的，之用考虑上半部，但陈轩发觉跨对角线的矩阵也该满足上述条件，我当时一下醒悟了，这个结论本来其实就是没错的，但被对角线一搅和，就容易忽略，于是我感觉思路成形了:在矩阵中逐个贪心的填入元素，遇到已经确定的元素就算出来然后继续往下。题目有个限制是所有的变权值不能想等且都小于1000。我试着这么编了一下，发觉如果直接在那些未确定的位置(其实只有每列第一个～)填入当前最大值加一，就会超过1000，但如果是填当前可用的最小值，又会出现不符合条件的情况，于是加入搜索的成分，对每个不确定的点，循环尝试所有可能。用dfs的方法，实现还不算太麻烦。要注意的是如果是确定的位置再往下搜返回不可能，那就直接返回，否则要继续尝试下一个值。编完了虽然和那个局部答案不同，但我觉得好像是对的，就提交了，没想到一遍过了。后来改了不少地方，修正了些小问题，然后又提交了几遍。这题其实结果卡的并不严，或者说满足条件的情况挺多，所以开始我虽然在搜索中跳过了一些值，但还能得到一个可行的结果。 这题正解似乎是给每个点一个值，然后两点之间的边就是两个顶点的和，这样能保证所有的回路权值相等(思路～怎么想到的?)这样只要用贪心的方式生成这样一组值，每个值用O(n^3)的复杂度判断是否冲突就行了，无论是想法还是实现，都更加简练。我后来看也有人是用我类似的想法做的，但似乎没有不断尝试和回溯，不知道是不是我漏了什么限制条件。这题也就几十人做出来，总算让我有点慰藉，但这些题前后花了n多时间，连作业都没做，只能说明一个问题:还差的远呢。 最近打算更积极的生活，不被作业牵着走，主动寻求提高。嗯，时间的安排是重点，这非常困难，但一定要努力做到。