记录我在解 CCF - CSP 时遇到的一些问题以及总结的经验。
简单模拟。
Dijkstra + 最小生成树。
注意使用边链表存储图时,快速获取最短路上任意一条边的长度的方式:https://github.com/Heliovic/My_CCF-CSP_Answer/blob/master/201609/20160904/main.cpp#L73, https://github.com/Heliovic/My_CCF-CSP_Answer/blob/master/201609/20160904/main.cpp#L112
为了取得最小总长度,Dijkstra 算法在遇到相同长度的路径时,应选择 graph[u][j]
最小的 https://github.com/Heliovic/My_CCF-CSP_Answer/blob/master/201609/20160904/main.cpp#L75 (画个图就清楚了)
两趟遍历。
正向求解难,反向顺推易。
STL map、string 的使用。
石子相邻合并的动态规划问题。
简单模拟。
最小生成树。
时间模拟,使用 event 保存某个时刻的事件,之后将所有事件按照时间排序,最后模拟一连串事件的发生。
简单模拟。
改变 dijkstra 最短路路径长度求解方法即可,有 20 分没拿到,暂不知原因。
通过将 int 改为 long long 又多得了 10 分。
正向、反向分别进行深搜,检查是否能够全部访问,若能, count++。
刚开始使用 int 二维数组,60分, 超时。改用邻接 vector 数组,100 分。
使用树状数组。
为避免超时,此题要注意的点非常多。
数值范围够用时,不用 long long,而用 int 来节省运算时间
[树状数组更新时,若 delta 为零,无需任何更新](https://github.com/Heliovic/My_CCF-CSP_Answer/blob/master/201709/20170905/main.cpp#L58, https://github.com/Heliovic/My_CCF-CSP_Answer/blob/master/201709/20170905/main.cpp#L62)
简单模拟。
简单模拟。
字符串处理
博弈搜索。
-
对于 Alice,她想获得高分。因此需要遍历当前棋盘下每一种落子方案,选择使得自己得到较高的分数。
-
对于 Bob,要抑制 Alice 获得高分,就要从每一种落子方案中选择使得 Alice 得分最低的那一个。
-
注意,在选择落子之前,要检查是否已经决出胜负或平局。
-
有 10 分没拿到,暂时不知为何。这 10 分注意区分平局和以最后一子取胜的情况即可!
20190315:精简了代码
回溯。 运行超时。 记忆化搜索解决运行超时。
简单模拟。
简单模拟。
复杂模拟 + 字符串处理。运行超时。
Kruskal + 并查集求最小生成树。