[C#] 逆襲——自制日刷千題的AC自動機攻克HDU OJ

前言

　　做過杭電、浙大或是北大等ACM題庫的人一定對“刷題”不陌生，以杭電OJ為例：首先打開首頁（http://acm.hdu.edu.cn/），然后登陸，接著找到“Online Exercise”下的“PRoblem Archive”，然后從眾多題目中選擇一個進行讀題、構(gòu)思、編程、然后提交、最后查看題解狀態(tài)，如果AC了表示這一題被攻克了，否則就要重做了~一般情況下，“刷題”要求精神高度集中且經(jīng)驗豐富，否則很難成功AC,有時候甚至做一題要浪費半天的時間！（有時網(wǎng)速卡了，比搶火車票還要急！）

　　樓主在這里先給廣大辛勤“刷題”的ACMer賠個不是，因為本文所介紹的AC自動機其實是利用爬蟲從網(wǎng)上搜索題目答案，然后再利用C#的web控件和鼠標、鍵盤事件來自動提交題目的投機式機器人（純屬樓主自娛自樂，多多見諒！）。

注：下圖依次是①主頁面；②題目列表頁面；③題目頁面；④提交代碼頁面；⑤提交結(jié)果查看頁面

成果

　　參看杭電OJ的RankList(http://acm.hdu.edu.cn/ranklist.php)，目前我用這個AC自動機粗略的刷一遍整個題庫共提交12391次，解決2688個題目，正確率21.69%，總排名第8。同時我還發(fā)現(xiàn)至少2個和我屬于同一類的考機器人刷題的“搗蛋鬼”，其中一個是排名第2到第7的三國蜀國的將領(lǐng)們，另一個是幾乎占據(jù)17~28名的hdujudge0~n。為什么能發(fā)現(xiàn)他們？哈哈，①沒人會連續(xù)幾天不停的刷題的；②總提交數(shù)高的離譜；③正確率低的嚇人；④我在浙大OJ上也遇到了他們（哈哈哈）。在此，我想邀請二位合伙做一個自動爬題+自動分析代碼的題庫解析的網(wǎng)站，也算是我們利用自己搗蛋的玩具做的一點好事~嘿嘿~（此外，我非常佩服排名第一的那位，如果是人刷的其毅力和能力絕對一流；如果是機器刷的，能達到53.80%的正確率也是非常高明的爬蟲！）

業(yè)務(wù)流程與狀態(tài)轉(zhuǎn)換機

　　其業(yè)務(wù)流程主要是模擬人在瀏覽器里的操作過程，從登陸到搜索，從搜索再到提交，從提交再到獲取提交狀態(tài)，如果AC了就轉(zhuǎn)到下一題，如果沒有AC就進行第二次嘗試（每道題目進行10次嘗試），如果中間出現(xiàn)異常就直接進行下一次嘗試，來保證程序順利進行。其整個過程通過下面四個狀態(tài)變量來控制。狀態(tài)轉(zhuǎn)換正常情況下發(fā)生在webBrowser1_DocumentCompleted以及timer1_Tick事件中，其中前一個事件是每次web文檔加載完畢時響應(yīng)，后一個事件是每隔一定時間響應(yīng)，此外當代碼提取和狀態(tài)提取的web文檔解析線程中如果發(fā)生異常，也會觸發(fā)狀態(tài)轉(zhuǎn)變。

 1 /// <summary> 2 /// 0初始狀態(tài)；1填寫用戶名和密碼狀態(tài)；2輸入找到的代碼；3查看是否AC； 3 /// </summary> 4 static int input_state = 0; 5 /// <summary> 6 /// 0初始狀態(tài)；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:初始狀態(tài)；1:Queuing狀態(tài)；2：Accepted狀態(tài)；3：錯誤狀態(tài)18 /// </summary>19 private static int AC_state = 0;

搜索答案

　　本程序的核心部分在于爬代碼的爬蟲的設(shè)計，這里調(diào)用百度搜索并從搜索結(jié)果中解析相關(guān)鏈接，然后轉(zhuǎn)到對應(yīng)鏈接提取答案代碼。首先我想到的是一般對ACM題目寫解答的地方一般是博客，所以順手寫了個從百度搜索結(jié)果獲取以http://開頭含blog的鏈接作為目標鏈接C#代碼，用下面的代碼順利找到了杭電1202題的三個可能含有解答代碼的鏈接放在D://1.txt中：(下面是搜索結(jié)果，前一個鏈接為代碼鏈接)

[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

　　但是，很快我發(fā)現(xiàn)這并不是一個很好的主意！因為通過解析百度搜索結(jié)果的html文件會發(fā)現(xiàn)搜索結(jié)果一般一次在div id="content_left"內(nèi)列出10條搜索結(jié)果，并且一般給出的鏈接并不是目標地址的直接鏈接，值得慶幸的是這10條搜索結(jié)果排列整齊，而且非直接鏈接輸入瀏覽器中會轉(zhuǎn)為相應(yīng)的目的鏈接，于是又順手寫了個爬這10個鏈接的程序：(點擊看GitHub中的源碼，下面是搜到的結(jié)果)

[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

　　現(xiàn)在，咱們爬到了鏈接，那么該如何從雜亂的目標頁面中找尋答案代碼呢？哈哈，我就不賣關(guān)子啦！其實分析眾多含有代碼的頁面可以發(fā)現(xiàn)，一般情況下代碼是放在body中，而且往往以#include開頭（這里只找C或C++寫的代碼的答案）。所以，根據(jù)這個規(guī)律我設(shè)計了一個首先定位body,然后尋找第一個#include的位置作為代碼起始位置，然后找到main，接著根據(jù)花括號對稱的原理找到代碼的結(jié)尾位置，從而從html中扣出相應(yīng)的代碼行。(代碼請見GitHub，其中op_getCode1(string temp, int num)是新增解析目標html的函數(shù))。下面是10個目標頁面中找代碼的結(jié)果，這里僅列出前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 了 調(diào)試很久！！！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 }