8.6
poj 1731[全排列生成]
参照白书上的做法, 关键在于
(1)递归的边界条件cur == n
(2)递归调用的条件c1(在生成序列中出现次数) < c2(在原序列中出现次数)
(3)!i || P[i-1] != P[i]判重
*需要注意, qsort可以直接对char排序
RQNOJ四周年模拟赛 -> 据说是NOIp难度 -> 审题压力很大
[七颗果子]给出一个数开七次方
30%的做法是直接开七次方
AC算法, 注意到输入不超过777位, 所以答案不超过[lg(10^(777/7))]+1 = 112位, 二分次数不超过log{2}{10^112} = 372.很明显对于每一个输入我们可以得到答案的位数, 先利用位数确定范围, 然后压位高精乘.
[七夕星夜]
此题无思路..只会模拟. 猜测标准算法是DP+优化
[七色彩虹]
将起点和终点各看做一朵云彩, 题目可以看作规定起点和终点的DAG最长路问题. 方程f(i, j) = min(f(k, j-1) + w(i, k)), 时间复杂度是O(N^7).由于每个点经过不止一次, 不能利用vis.想不到什么优化.
[七夕的礼物]
模拟或者利用公式[usaco friday涉及的蔡勒公式]
[估计]理论得分190, 实际上120左右, 还不一定调的出来. 去年做的话, 应该能90左右.
8.7
checker[DFS]
思路和昨天的生成全排列如出一辙, 可行性剪枝都在扩展节点的时候, 不同的是此题利用vis避免了循环检查.
*把vis数组利用位运算实现, 速度提升不大, 从0.73s到0.7s而已.
*M67给出的位运算做法只需要0.135s, 测试后发现两程序递归次数一样. 主要差别应该是在循环扩展节点.
*vis下标打反一次, 没有看对称性剪枝.
*发现一个惊人事实, USACO服务器计算能力加强了, NOCOW上据说0.9X的程序, 现在提交0.6X.
poj 1049[DFS], 1h, 3WA
直接套用生成全排列, 不同的是递归边界条件不是l而是c, 扩展节点注意满足A[i-1] < A[i]
*万般无奈找std对拍, 复习了随机数和bat的写法, 再次提示, 注意静态查错!!!
fence8
全排列生成+可行性剪枝, 时间复杂度O(K!), 只过了一个测试点 -_-
poj 3050[DFS], 50min
学习DFS-ID, 突然发现我昨天写的事实上就是DFS-ID. 不同的是, DFS-ID将深度逐渐递增, 进行多次搜索. 也就是说会存在一些冗余, 但是鉴于解答树的节点主要集中在最后两层, 所以前面的状态量并不大. 事实上DFS-ID结合了BFS处理距离节点最近的问题, 以及DFS的空间复杂度优势.
*调试了20min, 原因是因为对状态编码的一个循环写错了. -> 如果涉及多组易混变量的话, 一定要重点检查.
*Hash表的MaxState如何确定?
[Training关于BFS\DFS\DFS-ID的介绍]http://www.oiers.cn/usaco%20training/11-401.asp.htm
8.8
fence8[高仿dd_engi牛的程序]
枚举每一个board可以切成那些rail, 分析各种剪枝的动机.
优化:
1.排序后计算Σrail[1..i]>Σboard[1..N]的R=i的最小值 => 缩小R的可能性
2.二分[如何处理边界???] => 减少DFS-ID的枚举量
*关于边界处理的动机 by gXX
因为唯一的问题就是出现在[i, i + 1]这种区间, 你总是要调整mider的取法, 使得每次至少能够删掉一个元素。
(1)如果mider成功调整为[left, mider]否则是[mider + 1, right]
那么你需要写一个mider = (left + right + 1) / 2;
(2)如果mider成功调整为[mider, right]否则是[left, mider - 1]
那你就要写mider = (left + right) / 2
(3)在区间长度小于2的时候进行特判
3. rail[i] == rail[i-1] -> 这一个能切出来, 下一个直接试能不能切一个同样的
4. board[i] == board[i-1] -> 相等的情况下, 这个能切出来, 下一个显然也能切出来
[关于剪枝3和4]
如果有两个栏杆的长度相同，那么这两个栏杆从哪两块木板或者从一块木板中切出对最终结果是没有影响的，所以在遍历木板的时候，可以按照木板的顺序进行切割。比如规定一种次序，编号靠前的木板优先切割相同栏杆的第一个，以此类推，那么当rail[i]==rail[i+1]时,现在用第k块木板切出栏杆i，则栏杆i+1就从第k块或者更后面的木板进行切割，而不必再从头开始，因为i+1在i前面的情况已经搜索过了，其实将i+1与i的位置互换一下就是了；同理，如果两个木板相同，那么也规定靠前的优先切割栏杆；
[剪枝动机] by wh
这个剪枝主要是充分利用数据性质进行不等式控制，和生日蛋糕有点类似之处。所以说对于“切割”类的搜索题，通常他的“剩余部分”往往隐含着一些限制，可以作为剪枝的突破口
另外这个剪枝有个使用前提，就是要先转化成判定性问题，因此这也是我们必须id-dfs的原因
rqnoj 350[查找第k大]
这题对于类似快排来说数据比较强, Hoare划分法的时间常数比Lomuto划分法时间常数少一些, 平均复杂度O(N), 最差的话O(N^2). 真正意义上的O(N)算法似乎是非常麻烦的分治. 在本题中复杂度为O(MN). 使用平衡树的话可以做到O(MlogN).
*需要注意的是, 算法中存在swap操作, 故而如果求区间最值的话需要重新赋值
*Hoare的话实际上就是左右开弓..
*Lomuto的话实际上就是折腾序列最后一个数, 所以会多了很多不必要的swap
*这个随手写的例子不错
7 7
5 1 3 2 6 8 7
tyvj 1001[查找第k大/小 + 素数判断]
练习Lomuto划分法查找第k大
*查找第k大算法O(N)较直接排序O(NlogN)的差别不大, 而且更大的数据范围需要更高级的数据结构, 总的来说用处不大.
buylow[LIS+高精], 3h+1.5h.
方程考虑不周1h, 调试高精2h, 理解算法1h.
对于第二问, 注意到对于f[i] = f[j] + 1(j < i), 存在A[j] <= A[i](因为题目要求最长不下降子序列). 因而可以记录prev[i]表示f[i]的上一个f[j]的值, 注意f[i] > f[j]+1和f[i] == f[j+1]都要更新.然后会在第5个点挂掉.
即使是相同的A[j], 它们所对应的g[j]不同, 按照题意应取最大的. 故而prev[i]需要记录上一个j的下标.
f[i] = max(f[j]+1);
prev[i] = j(f[i] >= f[j]+1)
g[i] = Σmax(g[prev[i]]) (每个不同的A[j]对应的最大g[j]) -> 这里需要不断更新, 因而需要高精减
为了简化, 在序列末尾增加元素0, 故而f[n], g[n]即为答案.
*对于方程2, 可以用next[i]记录与A[i]相同且最近的值的下标, 计算方案时若next[i] && next[i]<i直接跳过. by BYVoid
->同样的A[i], 最后一个的g[i]最大. 假设A[j]==A[i], 存在g[j]<=g[i], 若区间(j, i)不存在A[k]>A[i]等号不成立.
*对于双目运算符, 函数()后要加const, 函数参数要加const和&, 注意利用初始化结合题目要求.
*第一版程序+=函数出现前导零
*对于每一道相似的题目, 要着重思考不同点, 在纸上得到正确的方程. 否则会在调试过程中浪费两倍的时间.
*静态查错可以避免浪费更多的调试时间, 要分析每个函数每条语句的动机, 以及实现情况. 不要盲目调数据.
8.9
fence6[DFS], 2h, 数据弱
*这题充分暴露了对题意分析不明, 贸然上手的后果. 此题应在40min内解决, 20min左右设计DFS, 剩余时间调试.
(1)标号. 利用map数组存储标号, 然后将下面的读入下标全部用map映射. -> 读题时应该完成
(2)DFS. 枚举每个点, 向右边DFS, 除了出发点不能再次加入. 但是题目中给出的left和right是乱序的, 也就是说必须记录prev, 然后从不含prev的一侧继续遍历. 所以DFS的状态为(起始边, 正在遍历边, 上次遍历边, 已遍历边权), 利用循环检查确定遍历方向.
*以前写Chapter2时就是这样, 题目在自己的能力范围内, 但是不注意题目的分析, 浪费大量时间.
cryptcow[算法1, 实现无能], 8h
读入原串后记录C\O\W的个数及位置, 个数不同则直接无解, 同时处理前缀和后缀(第一个C之前的和最后一个W之后的),然后深搜.
深搜过程(层数直接通过(原串-目标串)/3确定)中出现的新字符串用map记录下标, memcpy完成下标的复制和恢复, 利用vis判重(对于每个C\O\W).
其中比较麻烦的是C\O\W在变换后位置的更新和恢复, 花费了很多时间调试. 就算在纸上先算好下标的变换值, 还是很容易因为多个函数同时改变导致错误. 第二天上午最终过了3个数据点, 其余提示崩溃, 调试无能.
*了解一些细节:std关键字会引起冲突; memcpy(,,字节数), 一般为sizeof(类型)*数量
*比较奇怪的是利用fgets读入第一个数据会自动加回车.
8.10
ctyptcow[算法2], 5h
通过学习<string>的一些特性(《C++ Primer Plus》记录的很详细), 50min写完了不加任何优化的爆搜, 过了5个点.
1.得到s串的子串[i,j]: string newname(&s[i], &s[j]) -> 类似这样的函数还有别的一些神奇的写法
2.通过+\+=完成连接; .size()/.length()计算长度
3.getline(file, value) -> 有value的长度限制读入长度, 不必显式制定.
接下来是实现各种优化:
1.改变搜索顺序, 先顺序搜O, 然后顺序搜C, 最后逆序搜W(逐层if)
2.判断变换后的串COW间的子串是否为原串的子串, 可以记录原串每种字符出现的位置, 不是原串子串的话, 剪枝
3.判断变换后的串第一个C, 最后一个W的位置, 若C>W或从两端没有找到C/W但是找到O, 剪枝
4.利用ELF Hash. 严格意义上这步算骗分, 选取质数131071时恰好没有冲突. 但是严格意义上的Hash需要判重
5.找到第一个C和最后一个W, 确定DFS字符范围 -> 这个用了反而TLE
*对于涉及到数组的问题, 不一定要按照原来改变 -> 恢复的模式, 应该设法避免“恢复”过程.
*关于Hash, 参见WC2007李羽修《Hash函数的设计优化》, 很惊悚的发现我居然用直接取余A了.
*最后一个测试点卡着过的.
8.11
job[贪心(对称性) + 二分], 1h
首先要注意到这题是多机器并行工作, 所以不能使用DP, 可以贪心. 事实上如果从1到max{A[i]}*n逐个枚举t, 就可以得到最小的t. 这提示我们可以使用二分, 判定函数为Σt/A[i](1<=i<=n).
对于两种操作A、B, 要分别计算最短时间和方案(要保证A[]\B[]序列升序), 然后利用对称性找最大值.
*计算方案利用二重循环, 1..t为外层i, 1..na\nb为内层j, 未生产工件数为rest, 如果rest>0&&i|j, 那么ta\tb[n-(--rest)] = i;
*对于二分, 目前掌握两种写法. 一是lrj白书l>=r;check(m);l=m+1;r=m, 二是dd_engi在fence8中的l+1=r;check(m-1);l=n;r=m;
stall4[二分图最大匹配 -> 匈牙利算法]
[二分图最大匹配问题匈牙利算法]http://www.matrix67.com/blog/archives/39
[匈牙利算法]http://www.byvoid.com/blog/hungary/
[二分图最大匹配的K?nig定理及其证明]http://www.matrix67.com/blog/archives/116
第三项和这题关系不大.
[匈牙利算法] by M67
从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。
*可以从每个点开始找增广路, 最初的覆盖是空集, 第一个点过后就有了一条边, 之后边数会逐渐增多, 直到不存在交错路.
*似乎这题应该是无向图, 但是写有向图也不影响结果.
tyvj 1035[二分图最大匹配 -> 棋盘覆盖], 1h
对棋盘进行染色, 标记不能通过的点, 然后对于每个点(x,y), 分别和(x-1,y) (x,y-1) (x+1,y) (x,y+1)建立边(另一个点必须可以通过). 这里可以把二维坐标一维化, 之后这届套用匈牙利算法即可.
*注意输入中的坐标从1开始, 而实现中从0开始
*注意扩展边的时候, 新点同样可以访问 -> 卡了30min
poj 1422[二分图最大匹配 -> 最小路径覆盖], 20min, 1Y
[转载]在一个有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）
将图中的每个点拆为出点和入点, 将原来的边转化为出点和入点间的有向边, 利用匈牙利算法可以得到最大匹配数p. 显然二分图中每个匹配的出点都存在后继, 故而这些点不可能是DAG的重点, 因而答案为n-p.
[这个写得比较好]http://www.cnblogs.com/jackiesteed/articles/2043934.html
向gXX神牛请教如何对拍.
cowcycle[DFS], 2h
同时枚举F-组合和R-组合, 数据较弱, 加上可行性剪枝就A了.
1.搜索顺序
注意到题目要求答案字典序最小, 故而可以逆序枚举避免对字典序的判断.(也可以顺序, 然后找一个比较强的条件, 在完成找到答案后退出, 效率估计逆序的几倍.)
2.状态设置
dfs(当前F kf, 当前R kr, 剩余F数 nf, 剩余R数 nr).
3.终止条件
nf = nr = 0 || kf + 1 < F1 || kr + 1 < R1.
对于nf = nr = 0, 进行可行性剪枝(判断传动比率倍数) -> 注意这里是int
4.状态转移
非常麻烦, nf/nr为零的情况需要单独处理, 4种转移方式, 但是有8种情况.
5.优化
1)考虑到生成的待排序序列与排序后很接近, 而且数据量极小, 于是用冒泡代替快排
2)求平均值时, 先累加, 最后除; 求方差时直接忽略除, 不影响结果
这样可以把最后一个点从1.9s优化到0.6s, 很有效的控制常数.
*所有同时涉及double和int的语句, 必须进行强制类型转换
*memcpy(ansF+1, f+1, sizeof(int)*F)必须这样写, 如果将第三部分写作sizeof(f)或sizeof(f+1)导致错误 -> 原因不明
*对于这类比较复杂的搜索, 应该现在纸上写出大致模型, 并试图找出一些问题. 直接写程序很容易写错变量名, 或者出现设计问题. 这样应该能够大幅减少调试时间.
8.12
lgame[枚举 + 优化], 2h
1.读入目标串并记录分值.
2.读入字典, 如果字典中串的长度小于等于4, 且目标串长度大于7, 记录该串. 需要注意该串的每一个字母出现次数不应超过目标串出现字数.
3.如果该串分数大于等于目前记录最大分数, 则更新答案. 比较奇怪的是这里memcpy直接用sizeof(dic[t])不影响结果, 可能是字符串的原因.
4.对记录子串进行枚举, 并更新答案. 这里如果利用字符数组的话, 要注意计算连接处的坐标(不妨利用for, memcpy容易出错)
*对于字符串可以利用qsort间接排序, cmp函数先逐位比较, 然后比较长度.
*注意到题目中每个单词不超过7个字母, 但是输出中可能包含空格! 如果内存过小或不指定'\0'的话, 会继续输出后面的字符串.
*对于这类写代码都需要0.5h的题目, 需要思考如何减少调试时间, 现在调试时间是思考算法和写代码时间的两倍.