SRM 514 DIV 2 500P 1000P
2011年8月10日上午9点，SRM 514 DIV 2，由于 SRM 513 的教训，赛前已补习过Java语言了。

250P：review过代码，没发现错误，也没人cha，最后还是 Failed System Test，原来是一个判断失误，把正方形的边界当圆形判断了。
500P：思路很明显，BFS。(注：这只是我比赛时的做法，虽然AC了，但现在细想确实有问题，1.边界的判断应该设置的更大些才对，我代码里超过边界的点就没有加入队列了，怪不得有人cha，我只是运气好罢了；2.DIV 1 250P与此题一样，只不过数据条件大了太多，BFS就不行了。于是想整理下这个好题，感谢下本文一楼评论人——8月14日)

我每提交一题的得分都不高，思维不够敏捷啊，还有就是总是一边敲代码一边想，250P就是这个情况。
总结：不要急于敲代码，想清楚了再编码，可提高准确度和效率。

500P Problem
起点(0, 0)，给定一个整数数组，对于数组中每个整数 n 都有八种走法，如：(n, 1), (n, -1), (-n, 1), (-n, -1), (1, n), (-1, n), (1, -n) or (-1, -n)，可以无限次数使用。
判断是否能够到达指定点 (x ,y)。

500P Solution
解法的话一楼评论人已经描述过了，但一直不明白它的原理是什么。
论坛里 cpphamza 有漂亮的解释 http://apps.topcoder.com/forums/?module=Thread&threadID=717223&start=0&mc=15#1412343

1000P Problem
一个字符串数组A，前 K 个字符串是已知的(字符只有'0'或'1')，后面的字符串有公式：
A[i] = A[i-1] + A[i-K-1] + A[i-2K-1] + ...(while i-m*K-1 is not less than 0)
求字符串 A[n] 从索引 lo 到 hi 有多少个'1'。

1000P Solution
数据限制不大，所以看上去很简单，模拟即可，但实际上后面的字符串的长度可以大的要命。
只能寻找巧妙的方法了，来自practice room的一个代码：

public class MagicalGirlLevelThreeDivTwo {String[] strs;int K;long[] len;public int theCount(String[] first, int n, long lo, long hi) {K = first.length;strs = new String[K];len = new long[n+1];System.arraycopy(first, 0, strs, 0, K);for (int i = 0; i <= n; i++) {if (i < K) {len[i] = first[i].length();} else {len[i] = 0;for (int j = i - 1; j >= 0; j -= K) {//len[i] += len[j]; 会溢出，long型都不够啊len[i] = Math.min(hi + 1, len[i] + len[j]);}}}int res = 0;for (long i = lo; i <= hi; i++) {res += isOne(n, i);}return res;}int isOne(int n, long i) {if (n < K) {return strs[n].charAt((int)i) - '0';}for (int j = n - 1; j >= 0; j -= K) {if (len[j] <= i) {i -= len[j];} else {return isOne(j, i);}}return 0;}}

1 楼 shiqicai 2011-08-12 500P才不是bfs呢，是个图论题。
如果原数列存在偶数则所有点都可达，
如果全部是奇数则将图奇偶染色，偶点可达，奇点不可达。 2 楼 wq294948004 2011-08-12 shiqicai 写道500P才不是bfs呢，是个图论题。
如果原数列存在偶数则所有点都可达，
如果全部是奇数则将图奇偶染色，偶点可达，奇点不可达。
谢谢提醒，在practice room里是看到一个这样的代码，只有几行。
可我图论又不行，不好意思。