2020年华为软件精英挑战赛,京津东北赛区,bug水逆退散队题解
初赛成绩第18名,复赛练习赛第14名,复赛因为精度问题没有考虑到导致比赛2个半小时无成绩。虽然心里很失望,但是怀着和大佬相互交流的心情去学习和进步也让我感觉满足。
使用mmap对磁盘中文件空间和虚拟地址空间进行映射来达到快速读写的目的。在读入过程中,对于起点和终点不仅需要保存对应的32位无符号值,同时需要存储对应的字符串,这样输出的时候不需要再调用整形转字符串函数,从而减少程序运行时间。
反向dfs从u出发找长度为3的路径并保存下来,然后正向dfs找长度为4的路径做路径拼接。貌似大家都是这个搞法。
使用mmap+多进程的方式对数据进行输出,通过对输出字符串长度进行分割来使得每个进程输出长度相当的字符串来达到加快输出的目的。
- 反向建图,在找环是从到到小找,每次遍历到u的时候,将u出发的所有边加入图中,这样可以避免在从u出发找环时找到包含1~u-1的边。
- 改深搜为for套娃,减少程序调用函数进栈出栈的时间。
- 多线程需要考虑负载均衡,不然多线程的运行时长很可能比单线程长。(多线程代码线下测2000w环的数据比单线程快,但是未交到服务器上进行验证)