[C#] 逆袭——自制日刷千题的AC自动机攻克HDU OJ

前言

　　做过杭电、浙大或是北大等ACM题库的人一定对“刷题”不陌生，以杭电OJ为例：首先打开首页（http://acm.hdu.edu.cn/），然后登陆，接着找到“Online Exercise”下的“PRoblem Archive”，然后从众多题目中选择一个进行读题、构思、编程、然后提交、最后查看题解状态，如果AC了表示这一题被攻克了，否则就要重做了~一般情况下，“刷题”要求精神高度集中且经验丰富，否则很难成功AC,有时候甚至做一题要浪费半天的时间！（有时网速卡了，比抢火车票还要急！）

　　楼主在这里先给广大辛勤“刷题”的ACMer赔个不是，因为本文所介绍的AC自动机其实是利用爬虫从网上搜索题目答案，然后再利用C#的web控件和鼠标、键盘事件来自动提交题目的投机式机器人（纯属楼主自娱自乐，多多见谅！）。

注：下图依次是①主页面；②题目列表页面；③题目页面；④提交代码页面；⑤提交结果查看页面

成果

　　参看杭电OJ的RankList(http://acm.hdu.edu.cn/ranklist.php)，目前我用这个AC自动机粗略的刷一遍整个题库共提交12391次，解决2688个题目，正确率21.69%，总排名第8。同时我还发现至少2个和我属于同一类的考机器人刷题的“捣蛋鬼”，其中一个是排名第2到第7的三国蜀国的将领们，另一个是几乎占据17~28名的hdujudge0~n。为什么能发现他们？哈哈，①没人会连续几天不停的刷题的；②总提交数高的离谱；③正确率低的吓人；④我在浙大OJ上也遇到了他们（哈哈哈）。在此，我想邀请二位合伙做一个自动爬题+自动分析代码的题库解析的网站，也算是我们利用自己捣蛋的玩具做的一点好事~嘿嘿~（此外，我非常佩服排名第一的那位，如果是人刷的其毅力和能力绝对一流；如果是机器刷的，能达到53.80%的正确率也是非常高明的爬虫！）

业务流程与状态转换机

　　其业务流程主要是模拟人在浏览器里的操作过程，从登陆到搜索，从搜索再到提交，从提交再到获取提交状态，如果AC了就转到下一题，如果没有AC就进行第二次尝试（每道题目进行10次尝试），如果中间出现异常就直接进行下一次尝试，来保证程序顺利进行。其整个过程通过下面四个状态变量来控制。状态转换正常情况下发生在webBrowser1_DocumentCompleted以及timer1_Tick事件中，其中前一个事件是每次web文档加载完毕时响应，后一个事件是每隔一定时间响应，此外当代码提取和状态提取的web文档解析线程中如果发生异常，也会触发状态转变。

 1 /// <summary> 2 /// 0初始状态；1填写用户名和密码状态；2输入找到的代码；3查看是否AC； 3 /// </summary> 4 static int input_state = 0; 5 /// <summary> 6 /// 0初始状态；1移动鼠标聚焦name和passWord输入；2移动鼠标聚焦code输入 7 /// </summary> 8 int mouse_state = 0; 9 /// <summary>10 /// 0初始页面；1登陆页面；2提交代码页面；3查看AC页面11 /// </summary>12 int page_state = 0;13 /// <summary>14 /// 0初始情况；1已搜索链接；2代码解析中；3代码解析完毕15 /// </summary>16 /// <summary>17 /// 0:初始状态；1:Queuing状态；2：Accepted状态；3：错误状态18 /// </summary>19 private static int AC_state = 0;

搜索答案

　　本程序的核心部分在于爬代码的爬虫的设计，这里调用百度搜索并从搜索结果中解析相关链接，然后转到对应链接提取答案代码。首先我想到的是一般对ACM题目写解答的地方一般是博客，所以顺手写了个从百度搜索结果获取以http://开头含blog的链接作为目标链接C#代码，用下面的代码顺利找到了杭电1202题的三个可能含有解答代码的链接放在D://1.txt中：(下面是搜索结果，前一个链接为代码链接)

[1]http://blog.csdn.net/vsooda/article/details/7989833[2]http://blog.csdn.net/libin56842/article/details/8798301[3]http://blog.csdn.net/lulipeng_cpp/article/details/7496022

　　但是，很快我发现这并不是一个很好的主意！因为通过解析百度搜索结果的html文件会发现搜索结果一般一次在div id="content_left"内列出10条搜索结果，并且一般给出的链接并不是目标地址的直接链接，值得庆幸的是这10条搜索结果排列整齐，而且非直接链接输入浏览器中会转为相应的目的链接，于是又顺手写了个爬这10个链接的程序：(点击看GitHub中的源码，下面是搜到的结果)

[1]http://www.baidu.com/link?url=2O6LRDmjhJM8xn-Igu5wlgkwq5aZfdxxJ4r3RLoX_AzzJrz0vmi3sWTd96ktLE0hQvzR4ea3ejgVZGPElTh6zq[2]http://www.baidu.com/link?url=jvZjI4hHOKIzBkclLKizXM6CUHbJrWUIS3RyRUryCDKVjsszzs7bqYh7bTwqt306xZgDsIt7dMjAhG-RcdkpCQY1_UGqbXbd9FS0SEdix0u[3]http://www.baidu.com/link?url=Wf5w0vIJa319PEwImt7JAqKzbLxLSsR1FP4o6LJIwojMR9xgm3gBVvU6uTkxbgMEhJ6uvj2_aScJaZeJC9sbuz-OV4Vjr_pOS6s9MEhRclC[4]http://www.baidu.com/link?url=KzVFkFeRcnZbRd9-xQ_pSW-qEG9w49FnNk8pJafCGB5JkCTJVrydtcK9A5TAooIp7Efd1kKkg3pbSi8jdZ-5s9gYaGWRCNPpC0dVqch6aZk265kQQDFaxnAQBi6ShYFh[5]http://www.baidu.com/link?url=1P-1b_x2MtGF5ixNlsflUcv-qokmPg2U4DCcqVvQ8ZMZXhWCnnWt6DKw9HoOb7dI[6]http://www.baidu.com/link?url=nVipZInn7U4yAyPtkOZRT6N_FNDi_iqYfihdtBt7OUs3LQ_SZXZQu_PoHEsUG8kDAEQvHCUx4Xw79Bf6YybwHhzp0xBEz-buI19fPDQtXbe[7]http://www.baidu.com/link?url=Kj82Etn86GRJ19AdR3L3BPJvzlRN1K2Cvv2DrqiNFijbvk3FBTPlpnT8iB2jRYzNXQTLeqGrg7w3KhlYjfYzZxsCU4mJGWD3OZVDjIPGrRC[8]http://www.baidu.com/link?url=WFNnxqS9m-erR9iBWGUCtWP1neSEOPb_Jzi_Qz1PExLy-scAHVk6DY4d1OslE-5Ns_NsX3bb1_tfgWInj1xngq[9]http://www.baidu.com/link?url=QV5i9N8Xz7JhakxPGHsxBc8oO1zVcVMsYux105JtFB_hFwUse_9f_CKd1M2ll6vZznLsHNt6RwJvKiL2zU_-sc6MhyxL7iHmxqA9oAMigge[10]http://www.baidu.com/link?url=1kG1wvoAOwdndtSKIr5wE_1TgoYudR_xyKIRQpPK_kVPhGOKkr-qw3TJ1IcIQ3GV0Cbg7Ye_vvPEh31l2gjzpa

　　现在，咱们爬到了链接，那么该如何从杂乱的目标页面中找寻答案代码呢？哈哈，我就不卖关子啦！其实分析众多含有代码的页面可以发现，一般情况下代码是放在body中，而且往往以#include开头（这里只找C或C++写的代码的答案）。所以，根据这个规律我设计了一个首先定位body,然后寻找第一个#include的位置作为代码起始位置，然后找到main，接着根据花括号对称的原理找到代码的结尾位置，从而从html中扣出相应的代码行。(代码请见GitHub，其中op_getCode1(string temp, int num)是新增解析目标html的函数)。下面是10个目标页面中找代码的结果，这里仅列出前5个：

1 没东西

 1 #include<iostream> 2  2 #include<cstdio> 3  3 #include<string.h> 4  4 #define N 1010 5  5 #define INF 2000000000 6  6  7  7 using namespace std; 8  8  9  9 int map[N][N],lowcost[N],visited[N],d[N],p[N];10 10 11 11 12 12 void dijkstra(int s,int n)13 13 {14 14     memset(visited,false,sizeof(visited));15 15     int i,j,k,min;16 16     for(i=1;i<=n;i++)17 17     {18 18         lowcost[i]=map[s][i];19 19     }20 20     d[s]=0;21 21     visited[s]=true;22 22     for(i=1;i<n;i++)//我又写成 i<=n 了 调试很久！！！23 23     {24 24         min=INF;25 25         for(j=1;j<=n;j++)26 26         {27 27             if(!visited[j]&&min>lowcost[j])28 28             {29 29                 min=lowcost[j];30 30                 k=j;31 31             }32 32         }33 33         d[k]=min;34 34         visited[k]=true;35 35         for(j=1;j<=n;j++)36 36         {37 37             if(!visited[j]&&lowcost[j]>map[k][j]+d[k])38 38                 lowcost[j]=map[k][j]+d[k];39 39         }40 40     }41 41 }42 42 43 43 int DFS(int s,int n)44 44 {45 45     if(p[s]) return p[s];46 46     if(s==2)  return 1;47 47     int i,sum=0;48 48     for(i=1;i<=n;i++)49 49     {50 50         if(map[s][i]<INF&&d[s]>d[i])51 51         {52 52             if(p[i]) sum=sum+p[i];53 53             else sum=sum+DFS(i,n);54 54         }55 55     }56 56     sum=sum+p[s];57 57     p[s]=sum;58 58     return p[s];59 59 }60 60 61 61 int main()62 62 {63 63     int i,j,n,m,u,v,w;64 64     while(cin>>n&&n)65 65     {66 66         cin>>m;67 67         memset(p,0,sizeof(p));68 68         for(i=1;i<=n;i++)69 69         {70 70             for(j=1;j<=n;j++)71 71             {72 72                 map[i][j]=(i==j?0:INF);73 73             }74 74         }75 75         for(i=0;i<m;i++)76 76         {77 77             scanf("%d%d%d",&u,&v,&w);78 78             map[u][v]=map[v][u]=w;79 79         }80 80         dijkstra(2,n);81 81         cout<<DFS(1,n)<<endl;82 82     }83 83     return 0;84 84 }