http://blog.sina.com.cn/raymond[订阅]
博文
|
标签：杂谈 |
分类：USACO 解题报告。 |
USACO1.5.4，不喜勿入。
----------分割线----------
这题比较水。最多8轮，除了首位可能是2，3，5，7，9以外，每轮只有可能是1，3，5，7，9，数量级很小。我是开了一个二维数组来存下所有结果的，感觉更像bfs一些，虽然其实开到[8][32]就能够用，但不确定的时候还是开得比较大。analysis则是用递归来写的，应该还是会占用堆栈空间，其实也差不多。
| 分类：USACO 解题报告。 |
USACO1.5.3，不喜勿入。
----------分割线----------
这题的数据还真恐怖，牵涉到100000000以下的质数，尝试开了一个1e的数组居然能算出来，不过时间明显是秒级的，而且提交的话直接资源超限了。于是很坚决的做打表。先算出所有1e以内的质数，再去判断每个数是不是“回数”，判断函数没写好纠结了老久，最后还是把int分成char[]来判断，打表过了。然后回去用hint的方法来做。复杂度这个东西真的要写出来算了才知道，原来枚举所有的“回数”，即便是到8位，也只有9^4种，还不过万，因为是质数首位也就是末尾还必须是奇数又减少一半。对于每个“回数”去验证它是不是质数，只需要sqrt(x)次，对1e也来说也只有一万次。其实这么来看时间也应该接近边缘了，可是跑出来的结果，时间居然和打表是一个数量级，都小于0.1s。唉，要是不看hint，怎么都想不到会有这种事。还有就是analysis里面用i*i<x来回避了sqrt，挺好。
P.S：看别人的题解发现个重要的剪枝。因为所有偶数位的回文除了11以外都是11的倍数，这个又可以减少一半的判断，其实analysis好像有说没细看。还有可以把10000以下的质数打成表来判断生成的数是不是质数，看似要优些，不过
| 分类：USACO 解题报告。 |
USACO1.5.2，不喜勿入。
----------分割线----------
不懂为什么1.5.1讲的是位操作，然后这题仿佛跟位操作一点关系都扯不上。看到滴第一反应就是dp，应该是倒过来走，就需要把所有数据先输入，结果我开了一个1024*1024的数组他说栈溢出了，很奇怪后来看到别人有用1000*1000数组过掉滴，汗。于是只能开了两个1024的一维数组，每次输入一排数据做更新，因为数据不大于100，本来想用char节省空间，结果fin赋值搞不定，又改回了int，就过了。个人觉得这种更新的思路更想贪婪，不像dp了。analysis基本一样，稍微不同的是他是每次输入一个数字就在更新，不过还是得开两个数组，时空占用完全一样。
|
标签：杂谈 |
分类：USACO 解题报告。 |
USACO1.4.5，不喜勿入。
----------分割线----------
这个倒是应该算很典型的bfs，自己看了写的，一次ac了，感觉还可以优化，这题数据太小，整个空间不可能超过(a+1)(b+1)，实际上我只开了400的就搞定了。扫了下analysis，里面还给了好像枚举（也许是深搜）和暴力。总之这题比较水。只是刚开始对它的状态空间很没概念，后来翻了翻图论教材才想起。
|
标签：杂谈 |
分类：USACO 解题报告。 |
USACO1.4.4，不喜勿入。
----------分割线----------
就是暴力去搜啊搜，自己写的卡在应该是第八组数据，太朴素了时间过不到，想了半天想不通。于是又看别人的报告了。其实是有结论滴，公差只需要去试相邻两个数的差就行了，但是这样的话最好bisquare元素之间要连续。而连续的bisquare在判断时又很吃力，其实bisquare完全可以既做一个连续的，再做一个标志的，我想了半天没想到两个一起用，ft。还有就是那个判断的公式，a+(n-1)b>max就可以停止了。还需要注意生成bisquare时可能出现重复的结果比如6^2+8^2=0^2+10^2。好家伙这么一改最bt的数据也不过1s就出来了。
心情不畅不想看analysis了。
|
标签：杂谈 |
分类：USACO 解题报告。 |
USACO1.4.3，不喜勿入。
----------分割线----------
习惯性的在网上搜题解来看，感觉现在做USACO的人好多啊，题解资源相当丰富啊。
这个题其实严格来所也不该算搜索题吧，除非把枚举也看作搜索。结合网上的各种说法以及正好前两天看到吴文虎的黑书有讲这题，写了四种实现。第一种是纯枚举，九层循环，并且考虑了多种结果组合，应该可以看作是dfs，其实时间空间都还不错。第二种也是网上说得很多也是analysis里面有提到的常数解法，拿到结论实现也很容易，并且时间上有所改进。从第二种的结论推测其实每个初始情况只有一种解的组合，于是后面都是这样做的。第三种是传说中的bfs，相当麻烦，最后是用了一个[262200][28]的char数组才ac掉，时间也相当滴慢，不知道对于搜索的中间结果有什么好的记录方法。第四种就是黑书上的优化后的枚举了，写输出的时候出了各种状况，呵呵，时间空间占用上其实跟常数算法差不多。
|
标签：杂谈 |
分类：USACO 解题报告。 |
USACO1.4.2，不喜勿入。
----------分割线----------
这题说是深搜，个人觉得还不如说是枚举贴切。情况其实蛮复杂滴，看了别人的解答才理清思路。用的办法是以输入的数据为原始数据，每一块方块可能有旋转或者不转两种情况，于是做一个2*2*2*2=16的循环，对于每一种情况，给四个方块做一个编号，就有4*3*2=24种排列，然后对每一个排列列举图中的六种模式，由于数字太小，复杂度完全够。六种情况中4直接跳过因为跟5是一样的，6是最麻烦的。这题处理起来比较繁琐但是数据不卡人，所以很好过。analysis的思路基本一样，代码比较精炼一些。
|
标签：杂谈 |
分类：USACO 解题报告。 |
唉，这个空间基本上没戏了。另一个空间暂不对外开放。这里就留下来完成那些应该完成的东西吧。
----------分割线----------
USACO1.3.5 & 1.3.6，不喜勿入。
----------分割线----------
1.3.5以前看过思路不过拖了这么久一直没去做，这次做的时候还是走错了路，想着从确定的头尾去找最长回文，可行，不过第八组数据超时（大概要1.6秒）。这才想起以每个位置为中心的搜索办法，分了三种情况。结果第八组数据甚至超过了256行，改大行数的时候还忘了改大len[]，都改了就过了。看了分析才发现其实只需要判断i,i+1就可以了，另外一种情况自然能够包括进来，ft~原始的文本也应该用一个一维数组来存这样输出的时候就方便多了while((c
= getc(fin)) != EOF) {}。下面是分析里面对复杂度的分析。
There are 20,000 letters, and we are assured that no
palindrome is more than 2,000 letters long, and we search for both
even and odd palindromes, for a total of about 20,000*2,000*2 =
80,000,000 operations, which is perfectly reasonable within the
time limit.
1.3.6因为前几天做
花了三个多小时精心打造的99秒扫雷视频，最终因为怨念太重，在即将生成的时候很华丽的死机了。难道做了三个小时的东西中间居然没有保存过？当然不是，我保存过。但是很不幸，我运行了完全影子系统，于是死机过后，一切烟消云散。打破100秒的神话，终究不让我拿出来show一下。
其实任何事情，都是注定滴。
成都到都江堰，往返100km。有了上次180km的经验，这次好很多，只是我还是掉队的那个～囧啊。就在上个星期，在人们已经逐渐淡忘掉地震这个蹦der的时候，地震不愿意了，于是余震又来了，只是很小，小到很多人都没能感觉到。然而这次的都江堰之行，却让我再一次的走近了一次地震，废墟还在，帐篷还在，安置木板房还在，抗震救灾的标语还在，特别是，在路旁的一个很简陋的小木屋前，“512便民理发店”还在。
2个多小时的车程，之后吃到了传说中的老福坛。其实砣沱菜明明是郫县的，为什么一行人非要跑到都江堰来吃这个，呵呵我也不明白。不过味道还不错，挺特别的。
成都阴了一个星期却让我们在都江堰见到了久违了太阳，在江边呆到接近三点开始返程。过半的时候很不争气的又胃疼了。然后天又很不争气的阴了下来。到红光的时候已经五点半了。于是原本去世界乐园拍照的计划被放弃了。吃完饭，于是我就回来了。
