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

[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 沒東西 op_getCode2_[1]結果.txt 沒有找到 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 } op_getCode2_[2]結果.txt 找到了，但是沒有慮掉代碼前的行號！ 1 什麼也沒有 op_getCode2_[3]結果.txt 沒有找到 1 #include<iostream>#include<queue>using namespace std;const int inf=10000;int map[1005][1005];int hash[1005][1005];int n,m,p;int x1,y1,x2,y2;int dir[4][2]={-1,0,1,0,0,-1,0,1};typedef struct node{ int x,y,times,direc; node(){} node(int xx,int yy,int tt,int ff):x(xx),y(yy),times(tt),direc(ff){}}NODE;bool bfs(){ queue<NODE> q; NODE temp,tt; q.push(NODE(x1,y1,0,-1)); hash[x1][y1]=0; while(!q.empty()) { temp=q.front(); q.pop(); for(int i=0;i<4;i++) { tt.x=temp.x+dir[i][0]; tt.y=temp.y+dir[i][1]; if(temp.direc==-1) {tt.direc=i;tt.times=0;} else if(i==temp.direc) {tt.direc=temp.direc;tt.times=temp.times;} else {tt.direc=i;tt.times=temp.times+1;} if(tt.x>=1&&tt.x<=n&&tt.y>=1&&tt.y<=m&&tt.times<=2&&tt.times<=hash[tt.x][tt.y]) { if(map[tt.x][tt.y]==0||(tt.x==x2&&tt.y==y2)) { hash[tt.x][tt.y]=tt.times; if(tt.x==x2&&tt.y==y2) return true; q.push(tt); } } } } return false;}int main(){ while(scanf("%d%d",&n,&m)!=EOF&&(m||n)) { int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&map[i][j]); scanf("%d",&p); while(p--) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) hash[i][j]=inf; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(map[x1][y1]!=map[x2][y2]||map[x1][y1]==0||(x1==x2&&y1==y2)) printf("NO\n"); else if(bfs()) printf("YES\n"); else printf("NO\n"); } } //system("pause"); return 0;} op_getCode2_[4]結果.txt 找到了，但是沒有換行！ 1 #include<stdio.h> 2 3 char str[110]; 4 5 int main() 6 7 { 8 9 int i; 10 11 while(gets(str)) 12 13 { 14 15 for(i=0;str[i];i++) 16 17 { 18 19 if(i==0||(str[i-1]==' 20 '&&str[i]!=' ')) 21 22 23 putchar(str[i]&0xDF);//0x開頭的數據是16進制的 24 &是與運算符 c&0xdf是把小寫轉化為大寫 25 x20是把大寫轉化為小寫 26 27 28 else putchar(str[i]); 29 30 } 31 32 putchar('\n'); 33 34 } 35 36 return 0; 37 38 } op_getCode2_[5]結果.txt 找到了，完整代碼

　　從上面得到的結果不難看出：雖然存在一些完美的代碼，但是有很大一部分需要修改一下也能變成完美代碼！然後我綜合分析了上述代碼存在的情況：①代碼行號沒去掉；②html的轉譯符沒有轉換成標准字符；③CSS樣式沒有去掉；④沒有有效的換行。針對問題②和問題③粗略的寫了一個op_getCode2函數來實現代碼精化的問題（詳細代碼請見GitHub），然後將代碼精簡下，省去不必要的html下載，嘗試下解決問題①和問題④（代碼中191行，沒有換行是因為<br />被我直接刪除了），並多添加幾個html轉譯符的轉換，結果雖然沒有解決問題①，但是搜到的代碼正確率已經相當高了~於是就偷下懶，不去解決問題問題①了（嘿嘿，其實解決問題①並不難，只是我不想讓程序看著太亂>_<，最終的完美版代碼見GitHub）

自動登錄與自動提交

　　進行到這裡看似可以大功告成了，其實還差著遠呢~我們只是獲得了代碼，那麼該如何自動登錄用戶並自動提交代碼呢？我想到了曾經惡搞的酷我音樂盒（軟硬結合第二篇——酷我音樂盒的逆天玩法），在那次我用到了邪惡的模擬鼠標點擊事件來戲弄酷我音樂盒，這次我們也要這麼干！yes,用程序發送鼠標事件來偽裝成人在操作~但是，如果直接在IE、Google或者火狐浏覽器裡來操作，不就有點在玩弄這些軟件的嫌疑嘛，上次惡搞酷我人家沒來找我，這次可不一定呀！哈哈，所以俺還得另尋辦法~（☆⌒(*＾-゜)v開個玩笑，其實是因為考慮到要更好的操控web頁面，所以才采用C#的webBrowser控件的）。下面是模擬鼠標點擊事件的相關API，當想點擊某個位置時只要調用SetCursorPos將鼠標位置設置為相應位置，然後發送一個Down和一個Up消息就完成了一次點擊模擬~如果想移動滾動條只要設置位置->Down->設置新位置->Up~

1 private readonly int MOUSEEVENTF_LEFTDOWN = 0x2;
2 private readonly int MOUSEEVENTF_LEFTUP = 0x4;
3 [DllImport("user32")]
4 public static extern void mouse_event(int dwFlags, int dx, int dy, int dwData, int dwExtraInfo);
5 [DllImport("user32.dll", EntryPoint = "SetCursorPos")]
6 private static extern int SetCursorPos(int x, int y);
7 [DllImport("user32.dll")]
8 public static extern bool GetCursorPos(out Point pt);

　　可是問題又來了，如果只能用鼠標點點肯定是不能完成復雜的提交代碼工作的！於是想到了另一個邪惡的東西：模擬鍵盤消息~嘻嘻，這次我就能往對應的地方輸東西了。 如下：當鼠標將輸入聚焦移動到用戶名的輸入框後，調用SendKeys向對應對話框內輸入用戶名，然後發送Tab鍵轉至密碼輸入框，輸入密碼，最後發送回車，實現登陸！哈哈，怎麼樣？夠不夠炫酷呢？用我剛剛介紹的2個邪惡的工具再結合我玩酷我音樂盒時用的獲得窗口句柄來控制窗口的手段，大家應能能想到對QQ聊天做點什麼邪惡的事啦（是不是想到做一個和別人自動聊天的機器人呢？）

　　別得意太早，上面只是我們自以為軟件會很聽話的SendKeys("A")它就往框裡輸入A，可實際情況要糟糕的多~因為有輸入法的存在，所以在我嘗試往提交代碼的框裡發送code代碼時問題就出現了~試一下，當你的系統處於智能中文輸入法時，你想在某個框內輸入諸如"wos1"時會出現什麼效果呢？那麼，我們如何來解決這個問題呢？哈哈，我又想到了辦法——利用剪切板：我們板code復制到剪切板，然後在對應的代碼提交框內只要發送Ctrl+V即可實現代碼粘貼（我真是太奸詐啦，哈哈哈哈）

零碎的細節

　　到這裡基本上已經算完成了，但是一個沒有反饋的系統怎麼能算智能呢？於是我又對HDU OJ的提交代碼後的狀態list頁面進行解析，找到我的最新提交結果：如果AC了就做下一題，如果正在測試就再次刷新一遍知道有確定結果，如果錯了就嘗試下一個鏈接，直到10個鏈接全部試完轉到下一題。這裡要特別說明下，由於html下載與解析會造成長延時，如果放在主線程中去做會導致程序一卡一卡的，於是我將isAccept函數和另外兩個分別用於找10個鏈接的函數operator0、對某一個鏈接的目標頁面進行解析提取代碼的函數op_getCode1分別采用線程異步計算，這裡和上面實驗過程中采用的主線程中直接處理有不同，要稍微注意下。更多請看詳細代碼：https://github.com/beautifulzzzz/C4plus/tree/master/hdu_AC自動機

1 private static void isAccept(object obj) 2 { 3 try 4 { 5 html = html.Substring(html.IndexOf("table_text")); 6 html = html.Substring(html.IndexOf("table_header")); 7 html = html.Substring(html.IndexOf("center") + 5); 8 for (int i = 0; i < 15; i++) 9 { 10 html = html.Substring(html.IndexOf("center") + 5); 11 string temp = html.Substring(0, html.IndexOf("</tr>")); 12 int find1 = temp.LastIndexOf("userstatus.php?user=") + 20; 13 int length1 = temp.Substring(find1).IndexOf('"'); 14 int find2 = temp.IndexOf("font color=") + 11; 15 int length2 = 0; 16 while (find2 < temp.Length && temp[find2] != '>') find2++; 17 find2++; 18 while (find2 + length2 < temp.Length && temp[find2 + length2] != '<') length2++; 19 string user = temp.Substring(find1, length1); 20 string state = temp.Substring(find2, length2); 21 show += "user : " + user + "\r\n"; 22 show += "state: " + state + "\r\n"; 23 if (user.Equals("beautifulzzzz1")) 24 { 25 if (state.Equals("Queuing") || state.Equals("Compiling") || state.Equals("Running")) 26 { 27 AC_state = 1; 28 } 29 else if (state.Equals("Accepted")) 30 { 31 AC_state = 2; 32 } 33 else 34 { 35 AC_state = 3; 36 } 37 break; 38 } 39 //show += temp + "\r\n"; 40 } 41 } 42 catch(Exception e) 43 { 44 input_state = 3; 45 search_state = 2; 46 AC_state = 3; 47 } 48 } View Code

後記

　　這幾天忙著准備2015實習面試，所以也沒太多時間研究這些好玩的東西啦~謹以此篇博客證明我還活著，哈哈！其實樓主腦子裡還有很多炫酷的事，比如讓機器自編程、讓一些低級CPU學會交流與聯合、在全網內養殖虛擬機器人控制輿論...不過，這都要放放，首先得解決溫飽問題，不然注定孤獨寂寞冷呀~

 

相關鏈接

HDU AC自動機最終工程：https://github.com/beautifulzzzz/C4plus/tree/master/hdu_AC自動機

HDU AC自動機實驗版(要會用Github看歷史版本!)：https://github.com/beautifulzzzz/C4plus/tree/master/爬蟲