Beef McNuggets
数论，动态规划。
确定一个数c能否由a1,a2,a3...,an线性组合而成等效于求一次不定方程
a1*x1+a2*x2+...+an*xn=c ( x1,x2,...,xn>=0 ) (方程A)
是否有解。
裴蜀定理：裴蜀等式ax+by=m(a,b>0)有解当且仅当m是a b的最大公约数gcd(a,b)的倍数。
若gcd(a,b)>1 则方程对于无限个m无解。
若gcd(a,b)=1。当a,b>1时，如果要求x y非负数，m取某些值时无解，比如m=1时。那么是否只有有限个m无解呢？答案是肯定的：
设a,b互质，x0,y0是此方程的特解。其通解可以表示为x=x0+[b/gcd(a,b)]*t , y=y0+[a/gcd(a,b)]*t (t为任意整数)。
令x>=0且y>=0，得-x0/b<=t<=y/a，显然y0/a+x0/b>1时存在t满足此不等式，也即方程有解。令y0/a+x0/b>1，有a*x0+b*y0=m>ab。
可见当m大于ab时方程必有解。
把此结论推广到方程A可知：当gcd(a1,a2,...,an)=1时，有有限个c无解，也就是说我们可以求出一个最大的不能被表示的c；否则有无限个c无解。
确定一个数能否被表示出来可以简单地应用动态规划，如果连续出现256个数字可以被表示出来，那么之后所有数字均可以被表示出来，此时可以停止动态规划。
USACO题解中第二种方法认为数据中必有两个数字互质，所以可以只搜索256*256-2*256以内的数字能否被表示（因为“Given two relatively prime numbers N and M, the largest number that you cannot make is NM - M - N”）。
这个方法对于USACO的数据是正确的，因为这些数据只要有一个大于零的解，都有其中两个数字互质的情况出现。但是显然某些情况下n个数互质，但是两两不互质，比如21 35 15。所以我认为这个方法是有漏洞的。
Fence Rails
搜索，需要精心剪枝。
迭代加深搜索（IDDFS: Iterative deepening depth-first search）：控制搜索层数的DFS，即首先允许深度优先搜索K层搜索树，若没有发现可行解，再加大搜索层数（如K+1）重复搜索。
“一般来说，如果目标结点离根结点远，需要遍历整棵树，可以考虑使用深度优先搜索；如果目标离根结点近，或求最小步数，则考虑广度优先搜索或迭代加深搜索；若广度优先搜索存在空间不够的问题，则考虑使用迭代加深搜索。”（本段来源于：http://wenku.baidu.com/view/ce41b54669eae009581bec4a.html）
首先对rails从小到大进行排序，确定所给的boards能否切出n个rails实际上等效于确定所给的boards能否切出排序后的前n个rails。为此我们使用IDDFS，先确定一个搜索深度（即上述的n），再深搜每个rail对应的board，搜索到第一个可行的切割方式时就返回。
搜索时先搜索较大的rail，这样可以让搜索树比较“瘦”（相对于先搜索较小的rail），也就是说树基部的分支较少。
显然这时搜索的时间很大程度上取决于搜到可行解之前我们探索了多少失败的方式，如果能剪掉这些“失败树枝”就好了。所以我们需要提前预知必然的失败并且果断停止在这些“失败树枝”上继续搜索。设boards总长度是B，rails总长度是R，搜索过程中的边角料（不能再切出其他rail）的总长度为W，当B-R<W时可以剪枝。
board最大长度是128，但是rail总数会达到1023之多，可见长度重复的rails有很多，要避免因此产生的重复搜索，比如rail1=rail2=5，那么搜索rail2时只需从rail1对应的board开始。
Fence Loops
水搜索，简单地使用dfs就可以秒杀所有数据。实际上求图中最小环的正统方法是枚举环上的一条边然后求最短路径，不过输入数据是边的邻接信息，而最短路径算法是基于结点的邻接矩阵或者邻接表的，需要重构一下。构造邻接矩阵时可以保留所有篱笆的端点（即使它们会重合），这样最多200个结点，发现两结点重合就将距离置为0。
Cryptcowgraphy
搜索加剪枝。
两个剪枝：
（1）判断C O W字符之间的片段是否是明文的子串，不是就剪枝。
（2）判断第一个和最后一个加密用字符是不是分别为C和W，不是就剪枝。
防止重复搜索相同状态：
如果搜索到的C O W，它的CO或者OW区间内包含上次使用的C O W，就剪枝；比如本次搜索到的COW用红色表示，上次使用的COW用黑色表示，以下情况需要剪枝：CCOWOW 或 COCOWW 。这是因为先应用黑色COW和先应用红色COW效果相同。
使用以上剪枝还不够，为了配合第2个剪枝，我将搜索顺序设定为先搜索跨度较大的COW再搜索跨度较小的COW。至此AC。
评论 (0)
