博客地址

写在前面：从20年3、4月份就开始准备华为的这个软件精英挑战赛，到5月16号复赛结束，也差不多肝了两个月了，看了自己备份的代码已有51份。赛制为各个初赛赛区1-32晋级赛区复赛。各个初赛赛区33-64，晋级复活赛区复赛，各个赛区(包含复活赛区)的32强可获得华为手环+笔试绿卡。区域赛区TOP4晋级总决赛，竞争20W奖金。

最终成绩：队名：龙卷风筝，初赛成渝赛区rank35，复赛复活赛区rank11。

初赛赛题

1.1 输入信息:
输入为包含资金流水的文本文件，每一行代表一次资金交易记录，包含本端账号ID, 对端账号ID, 转账金额，用逗号隔开。
	本端账号ID和对端账号ID为一个32位的正整数
	转账金额为一个32位的正整数
	转账记录最多为28万条
	每个账号平均转账记录数< 10
	账号A给账号B最多转账一次
举例如下，其中第一行[1,2,100]表示ID为1的账户给ID为2的账户转账100元：
1,2,100
1,3,100
2,4,90
3,4,50
4,1,95
2,5,95
5,4,90
4,6,30
6,7,29
7,4,28

1.2 输出信息
输出信息为一个文件，包含如下信息:
	第一行输出：满足限制条件下的循环转账个数
	第二行开始：输出所有满足限制条件的循环转账路径详情。
输出循环转账路径要按照指定排序策略进行排序：总体按照循环转账路径长度升序排序；同一级别的路径长度下循环转账账号ID序列，按照字典序（ID转为无符号整数后）升序排序。
举例如下：
4
1,2,4
1,3,4
4,6,7
1,2,5,4

1.3 限制条件
循环转账的路径长度最小为3（包含3）最大为7（包含7），例如账户A给账户B转账，账户B给账户A转账，循环转账的路径长度为2，不满足循环转账条件。

初赛方案

分析赛题其实可以简要概述为：

题意：给定一个有向图，求出图中所有长度在[3,7]之间的环。
输入：格式为[IDU,IDV,Weight]的边表，ID为32位无符号整数，边最多28W条，不重复，结点平均度数小于10。环中同一个ID不可以重复出现（若大环包括小环，则需要分开统计），环的个数不大于300W。
输出：环的个数，按照1.环长度；2.环的数字字典序输出所有环。

mmap读取文件，fwrite写入文件

因为线上数据较小，算法找环时间前排大佬普遍用时很短，所以导致I/O占比较大，mmap读取数据比fscanf快不少；mmap写入数据，需要通过写入答案的大小，预设文件的大小，通过测试fwrite比mmap写入文件快0.02以上，所以最后一直沿用mmap读取文件，fwrite写入文件的方案。

void read_file(string fileName)
{
    int fd;
    char *start;
    unsigned int dataSize = 0;
    fd = open(fileName.c_str(), O_RDONLY);

    // struct stat st; //定义文件信息结构体

    unsigned int len = lseek(fd, 0, SEEK_END);
    start = (char *)mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
    if(start == MAP_FAILED) /* 判断是否映射成功 */
        return;

    unsigned int temp = 0;
    unsigned int commaCount = 0;
    for(unsigned int i = 0;i < len;i++) {
           if(start[i] != ',' && start[i]!= '\n') {
               temp = temp*10 + (start[i] - '0');
           } else if (start[i] == ','){
               if (commaCount == 0) {
                   vecData.emplace_back (temp);
                   temp = 0;
                   commaCount++;
               } else if (commaCount == 1){
                   vecData.emplace_back (temp);
                   temp = 0;
                   commaCount=0;
               }
           } else if (start[i] == '\n') {
               dataSize++;
               temp = 0;
           }
           if (start[i] == 0) {
               break;
           }
    }
#ifdef __TEST__
    cout << dataSize<<endl;
#endif
    munmap(start, len); /* 解除映射 */
    close(fd);

}

建图

ID为32位无符号整数，读入数据后对ID大多是不连续的，所以讲ID映射到一个连续的区间是十分必要的。图的数据结构用二维数组当做邻接表,因为一个有向环的各个节点必定是有出度和入度的，通过拓扑排序删除不能成环的节点。

如上图所示，节点1是没有入度，所以改节点必不可能成环。我们将与节点1相连的边全部删除，发现节点2的入度也为0了，也将其删除。同理出度为0的节点，也可以用这种方法删除。

5+2的双向多线程并行DFS算法

如果用dfs寻找环长度为7的环，最大递归深度为7。非常深，层次越大，遍历的节点数目呈指数级上升。上图所示为1->2->3->4->5->6->7的有向环，我们发现从节点1出发，向前走5步来到节点6；从节点1出发，向后走2步也来到了节点6。即使说，正向DFS遍历走到第五层，就能知道是否有7环存在。用数据结构vector<unordered_map<unsigned int,vector<unsigned int> > > P2来保存反向2节点的数据。

初赛代码

链接：https://pan.baidu.com/s/1FVTxJlbm3JMHsuId3eV2RA
提取码：xk0r

复赛赛题

1）复活赛练习：5月6日9:00-5月15日18:00
2）复活赛：5月16日14:00-16:30
本阶段每个团队每天可提交作品5次
复赛会对赛题和数据集进行调整，最终排名以复赛（5.16下午）的成绩为准

复赛练习赛题

1.1 输入信息
输入为包含资金流水的文本文件，每一行代表一次资金交易记录，包含本端账号ID, 对端账号ID, 转账金额，用逗号隔开。
	本端账号ID和对端账号ID为一个32位的无符号整数
	转账金额为一个32位的无符号整数
	转账记录最多为200万条
	账号 A给账号B最多转账一次
举例如下，其中第一行[1,2,100]表示ID为1的账户给ID为2的账户转账100元：
1,2,100
1,3,100
2,4,90
3,4,19
4,1,95
2,5,95
5,4,90
4,6,30
6,7,29
7,4,28
1.2 输出信息
输出信息为一个文件，包含如下信息:
	第一行输出：满足限制条件下的循环转账个数
说明：数据集经过处理，会保证满足条件的循环转账个数小于2000万。
	第二行开始：输出所有满足限制条件的循环转账路径详情。
输出循环转账路径要按照指定排序策略进行排序：每条循环转账中，ID（ID转为无符号整数后）最小的第一个输出；总体按照循环转账路径长度升序排序；同一级别的路径长度下循环转账账号ID序列，按照字典序（ID转为无符号整数后）升序排序。
举例如下：
3
1,2,4
4,6,7
1,2,5,4
1.3 限制条件
	循环转账的路径长度最小为3（包含3）最大为7（包含7），例如：账户A给账户B转账，账户B给账户A转账。循环转账的路径长度为2，不满足循环转账条件。
	转账金额浮动区间约束为[0.2, 3] ：循环转账的前后路径的转账金额浮动，不能小于0.2，不能大于3。如账户A转给账户B 转X元，账户B转给账户C转Y元， 那么进行循环检测时，要满足0.2 <= Y/X <= 3的条件；如果转账金额为0，则不满足这个约束，不符循环转账的条件。

复赛正式赛题

复赛赛题变更点

在练习赛基础上，加入以下变更点，作为正式赛题，答题时间2个半小时，最终排名仅以正式赛排名为准，每队5次提交机会。

变更一
循环转账的路径长度最小为3（包含3）最大为8（包含8）
变更二
转账金额变更为浮点数：整数部分大于0，小于2的31次方；小数部分用小于等于2位数的数字表示。如下方式都是正确的表示
整数部分.YY 如 1000.53 1000.50 1000.00
整数部分.Y 如 1000.5 1000.0
整数部分如 1000

复赛方案

初赛数据量小，采用的5+2的寻环方式，当数据量大了之后，这种方式正向走了5步，非常废时间。考虑7环的最大平均拆分是4+3或者3+4。决定做正向4步搜索，反向3步搜索的思想，即4+3的双向多线程并行找环DFS算法。为了更好的配合多线程，舍弃初赛首先对所有的节点反向建图的方案。对有效的每个节点先做反向3步的节点保存，在做正向4步的节点保存，这样反向搜索也能充分的利用多线程的资源。

另外复赛正式赛题，对金额做了更改。对程序影响较大。庆幸当时做出了正确的判断，放弃了mmap读取文件，放弃了多线程并行找环，首先做出一个单线程的demo跑出有效成绩了，在利用剩下的时间优化代码。

赛后了解到，很多队伍由于正式比赛只有2个半小时，没有来得及成功修改好代码，导致复赛没有成功提交，非常遗憾。策略选择也同样重要。

转账金额处理

因为转账精度要满足0.2 <= Y/X <= 3的条件,考虑到使用浮点型判断等于，会产生精度问题，所以将金额乘以100以unsigned long long类型保存，将判断表达式，左右同乘以5X得X<=5Y<=15X,以整形来处理，处理速度和精度都有所保障。

#define CONDITION(value1,value2) ( ((unsigned long long)value2<=(unsigned long long)value1*5 && (unsigned long long)value1*5<=(unsigned long long)value2*15) )

vector<unsigned int> vecData;
vector<unsigned long long> vecMoney;
void read_file(string testFile)
{
    vecData.reserve(2000000*2);
    vecMoney.reserve(2000000);
        FILE* file=fopen(testFile.c_str(),"r");
        unsigned int u,v;
        char c[100] = {0};
        while(fscanf(file,"%d,%d,%s",&u,&v,&c)!=EOF){
            vecData.push_back(u);
            vecData.push_back(v);
            unsigned long long tmp = 0;
            unsigned int i =0;
            for(;c[i]!=0;++i) {
                if (c[i] == '.') {break;}
                tmp = tmp*10 + c[i]-'0';
            }
            if(c[i]=='.') {
                for(unsigned int j =i+1;j<i+3;j++) {
                    if(c[j]>='0') {
                        tmp = tmp*10 + c[j]-'0';
                    } else {
                        tmp = tmp*10 + c[j]-0;
                    }
                }
            } else {
                tmp = tmp*100;
            }
            vecMoney.push_back(tmp);
        }

 }

复赛代码

链接：https://pan.baidu.com/s/1y3IMGvwSaNEDPleMjtKKfg
提取码：97nz

华为软件精英挑战赛2020