8.03 / 10 …
。。。似乎本月题目的整体质量有所下降？。。。。
不过 Knight Moving && Annual Parade 对我来说还是十分困难。。）
（某种程度上说 Knight Moving 对我来说更加困难。。。
Level 1:
Racing Horses:
签到题，略。
Kisses & Hugs: 数列
开始错推成 http://oeis.org/A002620
。。。后来发现题目读的不对。。所以应该是这个。。http://oeis.org/A027383
Three is Crowd: 数列。。
http://oeis.org/A050231
取补集后得到 Tribonacci。。之后矩阵乘。。
Chef World：数列。。。。
先写了个暴力。。。http://paste.ubuntu.com/1185570/
F[n] = 0, 5, 18, 44, 96, 195, 380, 719, 1332 ..
发现 OEIS 里面没有记载。。。。。。
手推后得到…一个四阶线性递推数列。。（常数注意。。
（常数优化两处。。一个是矩阵乘法里面。另一个是先预处理出所有 A 的 k 次幂。。
ChefTown Parade: 给定一个排列，问其中连续 k 项排序后恰好布满一个长度为 k 的区间的区间数。。
。。注意 nlogn 的算法会 TLE 。稍作整理后可以得到一个基于单调队列的算法。
Queries About Numbers: 数论。。
。第二问和第三问是对称的。。因式分解即可。。
Lights：。。写了一个暴力二分。。居然过了。（求更好算法。。。
Level 2:
Annual Parade:
给定一副有向图，每条边有一个权值，要求用若干个路径和环对图进行覆盖，每条边可以使用任意多次。。
没有覆盖的点产生额外的 C 代价，如果是路径则也要产生额外的 C 代价进行返回。。
现在共 T 组询问，对每组询问不同的 C 值。。返回最小代价。
——————
感到这里的 C 很不自然，第一印象是最大权闭合子图，于是开始尝试网络流建模，不过似乎无法解决每条边可以使用任意多次的问题。。
。。只要对原图求传递闭包后，问题就转换成了哈密顿圈覆盖，对于不存在的边，用 C 赋值上即可。
。对哈密顿圈覆盖。使用 KM 的话。。至此就得到了 O(Tn3) 的算法。。。
之后考虑不同 C 之间的冗余。。。那么如果对询问进行排序，如果当前某对匹配的权值是 C，那么对于更大的 C。。一定也是这组匹配。。
于是对询问离线处理。。仍然得到了 O(Tn3)。。但是 n 的规模会逐渐减小。。。
但是仍然各种 TLE 。。。
赛后对 CLJ 的代码 使用了初级鹰眼术。。。
发现我这一步误区了。。（。。。我这里似乎一直认为对于二分图最有匹配问题。。用特定的 KM 算法总是比费用流来的有效。
。但是这题里使用费用流可以逐步推流。。从而在不同的询问之间得到很自然的优化。。。
Knight Moving:
给定两组步长，(AX, AY), (BX, BY)，问从 (0, 0) 开始出发到 (n, m) 结束。。
。有多少种不同的移动方案。。（无解或者无穷解或者有限解。。。
——————————————————
不同的移动方案定义为某一步所到达的格子不同。。。所以对于 AX == BX && AY == BY 的情况要单独处理。。。
。。除此之外还有各种各样的情况。。总之此题远比其看起来要复杂。。> <。
附加题:
Simultaneous Nim:
。。给定一组亦或和为 0 的数。。要求分割出尽可能多的组。。
使得每组内的亦或和同样为 0 .。。
——————————
写个暴力判断相同位置就能得到 0.03 分。。。
（。。ACRush 从第二天就开始狂刷这道题。。。而且我前面的题目没做完 。完全没动力做附加题啊。。。。
。。。后来最后几个小时实在没办法。。又回到这个题。。想了一个算法。。根据数字的最高为进行分组。。
然后从高组向下递降。。打印最高位为 0 （也就是亦或和为 0 ）的所有组合。。。不过最后当然是没调出来啦。
。。。。。
