本章我的代码见github。
7.4节例题7-5 uva129
7.4节例题7-7 uva1354
标程很值得学习,用位运算处理子集,用vector<pair<double,double>>存储某个子集对应的所有可能的L,R值,并且预处理计算sum。注意如果s=1那么答案就是0,我因为算ans时把0作为初始值,最后判断如果ans=0就输出-1而WA1次。
7.6节例题7-12 uva1343
不要被lrj骗了,BFS+判重是要TLE的!原因在于转移代价很高,而且如果选定的目标数字不对的话BFS会遍历相当多的状态还没用。正确的做法只能是IDA*,估价函数为8-目标位置中出现最多数字的次数(因为每次操作最多把1个目标数字加入目标位置中)。
7.6节例题7-14 uva1602
标程也很值得学习,用set<pair<int,int>>以散点的形式存储网格,在套上一个set以查重。大量使用STL和foreach能使代码变简洁。 值得注意的是编程时发现的一个小地方:如果f(T&)的实参是const T&类型的,C++编译器会隐式类型转换,创造一个从调用的实参拷贝过来的临时变量作为真正的实参。
习题7-4 uva818
IDS要打开的圆环,判断剩下的圆环是否都形成链以及是否满足开环数+1>=链数。连通集形成链的条件是要么d0=1要么d2=2且d(>=3)=0(这里dn表示度数为n的点的个数)。
写的时候问题颇多。写BFS,莫名其妙地RE2次(推测是队列开的不够大),写IDS先是忘了判重TLE1次,然后是漏了d0=1(即单个圆环)的条件WA1次。
习题7-7 uva12558
IDA*,剪枝条件是1/n<a/b<=rd/n,这里rd表示剩余层数。只要用long long就可以无视题目中关于溢出的提示。注意判断被排除的分母时可能会超出数组范围导致RE,以及要对最后一个分母做排除判断。然后不要漏了文件尾的,输出用%lld而不是%I64d否则会PE。这些莫名其妙的细节错误一直改不对,前前后后错了20次。
习题7-8 uva12107
先IDDFS修改方案,再DFS判断是否有唯一解。注意第二层DFS的时候只要枚举出左边两个数就可以直接判断等式是否成立了。做的时候有很多细节性的错误导致WA……感谢uDebug和用户szp14提供的随机数据。
习题7-9 uva1604
这绝对是我做过的最恶心的一题!!!用9个0~6表示方阵状态,用hash表判重(也可以用八位六进制数+空格坐标作为状态直接存储,开一个\(9\times 6^8\)的数组,反正uva空间多)。
先写BFS然后TLE,怒写双向BFS然后还是TLE。搜题解发现要控制正向和反向的搜索层数(因为反向初始状态有\(2^8\)个),正向21层反向9层最好,改了以后程序的时间从>3000ms变成了230~240ms。
习题7-13 uva817
注意表达式中一定要有至少一个运算符!或者直接单独处理输入2000=的情况也行。这里再次感谢uDebug和用户szp14。
习题7-15 uva11882
DFS,但是因为是求最大数所以不容易剪枝,R*C=30的时候又容易TLE。我统计了数字格的个数,当目前最优解取满了所有数字格后就开始剪枝,居然就AC了……