阶段学习总结

阶段学习总结

这周看了搜索有关的资料和题目，大部分接触的都是模拟+搜索+剪枝，部分涉及到bfs+kmp，做题还是比较少，总结不是很到位。用bfs的题目一般都可以用dfs解决（除了最短路），codeforces比赛div3还是ab题还是以思维题为主，后面的题没有思路。div2a题一般可以出（这周俩a题都在细节出问题，测试案例没过，比如数据量应该用long long），b题可以用bfs解决，时间太短代码没有写完（一直在调a题浪费太多时间）。

[NOIP2002 普及组] 选数 - 洛谷

给n个数,挑k个数,问有几种情况k个数和为素数。

DFS试除法判断素数(数据量过大，不建议打表)，bool数组避免重复选数，若选完k个：若sum为素数则ans++，并返回。从0到n开始递归，每次递归更新状态：sum，当前为第几个数，数组下标。注意递归回溯对称(标记与删除标记）

求细胞数量 - 洛谷

给出一个n行m列的矩阵,矩阵中连续的(上下左右)非零数看作一个块，求有多少个块

bfs，开两个数组记录坐标偏移量，广搜中判断点非零且没有标记，若符合，则将该点入队，答案++，并标记，循环（队列非空），记录队首元素并弹出，将四个偏移量依次进行判断，在区域内且未被标记且元素非零则入队并标记。循环结束后可得到答案

海战 - 洛谷

与上题求细胞数量一样，唯一区别是加了一个判断条件，若#不是方形则输出bad…

与上题求细胞数量一个思路，再加一个判断条件，判断当前格与右，下，右下构成的方格是否存在#为3的情况，若存在就输出bad，否则再进行bfs。（不算是剪枝）

[USACO10OCT]Lake Counting S - 洛谷

依旧考察bfs，坐标偏移量改为8个即可。

Problem - 2717

最短路问题，求最小步数，bfs。之前的bfs基本都是遍历所有坐标，而此次是求最短路，一旦满足结束条件就终止。结束条件：若pos==n，则输出step，这样不管push进多少种情况，总是最先输出最短路。不满足结束条件：三种走法push进+标记，三种走法作为一大类，后退的作为一大类，走哪种前先进行判断pos和n的位置，pos<n，走三种，pos>n只能后退，并标记已走过的位置，达到剪枝的效果。

3414 -- Pots

是上一题的进阶版。最短路问题，bfs。模拟，把a，b壶中水量作为状态，每次操作看作状态变化，同时考虑操作的条件以及操作后的a和b的状态标记，达到剪枝效果。代码中涉及存储的一部分还未读懂，但bfs部分已理解（说实话，读题之前压根一点头绪都没有，看完题解豁然开朗，还可以这样进行模拟？？长见识了，感觉所有最短路问题都可用bfs。）