GCA

ACM大量習題題庫 ACM大量習題題庫 現在網上有許多題庫，大多是可以在線評測，所以叫做Online Judge。除了USACO是为IOI准備外，其餘幾乎全部是大學的ACM競賽題庫。 USACO http://ace.delos.com/usacogate 美國著名在線題庫，專門为信息學競賽選手准備 TJU http://acm.tongji.edu.cn/ 同濟大學在線題庫，唯一的中文題庫，适合NOIP選手 ZJU http://acm.zju.edu.cn/ 浙江大學在線題庫 JLU http://acm.jlu.edu.cn/ 吉林大學在線題庫（一直上不去） PKU http://acm.pku.edu.cn 北京大學在線題庫 URAL http://acm.timus.ru 俄罗斯烏拉爾大學在線題庫 SGU http://acm.sgu.ru/ 俄罗斯聖薩拉托夫州大學在線題庫 ELJ http://acm.mipt.ru/judge/bin/problems.pl?lang=en 俄罗斯莫斯科物理技術學院 SPOJ https://spoj.sphere.pl/ 波蘭格但斯克理工大學 UVA http://acm.uva.es/ 西班牙的Universidad de Valladolid在線題 ACM聯系建議 一位高手對我的建議： 一般要做到50行以內的程序不用調試、100行以內的二分钟內調試成功.acm主要是考算法的 ，主要時間是花在思考算法上，不是花在寫程序與debug上。 下面给個計劃你練練： 第一階段： 練經典常用算法，下面的每個算法给我打上十到二十遍，同時自己精簡代碼， 因为太常用，所以要練到寫時不用想，10-15分钟內打完，甚至關掉顯示器都可以把程序打 出來. 1.最短路(Floyd、Dijstra,BellmanFord) 2.最小生成樹(先寫個prim,kruscal要用並查集，不好寫) 3.大數（高精度）加減乘除 4.二分查找. (代碼可在五行以內) 5.叉乘、判線段相交、然後寫個凸包. 6.BFS、DFS,同時熟練hash表(要熟，要靈活,代碼要簡) 7.數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式. 8. 調用系統的qsort, 技巧很多，慢慢掌握. 9. 任意進制間的轉換 第二階段： 練習复雜一點，但也較常用的算法。 如：

//伪代码，要用自己去改 //storm.dll //////////////////////////////////////////////////////////////////////////////////////////////////// //1503AE83    E8 58FDABED     call    GameStat.02AFABE0 // hook Storm #501号函数，Storm.dll库的详细函数列表请看 //  code.google.com/p/vgce/wiki/stormDLL //GameStatDota.dll( modulebase:0x2af0000,  size:0x1a000) void GameStatDota_02afabe0(str) //比较游戏中的一些字符串，获得游戏结果等等 {   if(!IsBadReadPtr(str))     Func_2af9980(str); //跟据字符串内容做出动作 } char * mystrstr(char * str1, char * str2, int len) {   int i = strlen(str1);   for( int j=0; j< i - len; j++)   {     if(memcmp(str1+j, str2, len) == 0)       return str1+j;   }   return NULL; } Func_2af9980(str) //判断内容，做出动作   //只要在游戏中显示出来的字符串，都可以在这里面弄到，然后做一些分析   //比如统计杀人次数，死亡次数，金钱，等级。。。等等 {   install_seh(); //?   if(mystrstr(str, utf-8("：|r"), 4) != 0) //  0x3A, 0x20, 0x7C, 0x72     //不知道做啥的，=我再研究下   if(mystrstr(str, utf-8("等待其他玩家中"), 0x15) != 0)      GetTickCount();   if(mystrstr(str, asc(&

#include #include #define SWAP(x,y) {int t; t = x; x = y; y = t;} #define BOX_SWAP(x,y) {box_t t; t = x; x = y; y = t;} typedef struct{ int no; int edge[12]; }box_t; using namespace std; int Greater(box_t b1,box_t b2,int dim){ int i; for(i=0;i<dim;i++){ /*cout<<b1.edge[i]<<" and "<<b2.edge[i]<<endl;*/ if(b1.edge[i]<=b2.edge[i])return 0; } return 1; } void sort_box(box_t box[],int box_num,int dim){ int i,j; for(i=0;i<box_num;i++){ for(j=i+1;j<box_num;j++){ if(Greater(box[i],box[j],dim))BOX_SWAP(box[i],box[j]); } } } void sort_edge(box_t box[],int box_num,int dim){ int i,j,k; for(i=0;i<box_num;i++){ for(j=0;j<dim-1;j++){ for(k=j+1;kbox[i].edge[k])SWAP(box[i].edge[j],box[i].edge[k]); } } } } void print_LIS(int x,int prev[],box_t box[],int choose){ if(prev[x]!=-1)print_LIS(prev[x],prev,box,1); if(choose==0){ cout<<box[x].no<<endl; } else{ cout<<box[x].no<<" "; } } int LIS(box_t box[],int prev[],int box_nu

動態規劃經典教程 引言：本人在做過一些題目後對DP有些感想，就寫了這個總結： 第一節 動態規劃基本概念 一，動態規劃三要素：階段，狀態，決策。 他們的概唸到處都是，我就不多說了，我只說說我對他們的理解： 如果把動態規劃的求解過程看成一個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的操作。顯然不同階段是對產品的一個前面各個狀態的小結，有一個個的小結構成了最終的整個生產線。每個狀態間又有關聯（下一個狀態是由上一個狀態做了某個決策後產生的）。 下面舉個例子： 要生產一批雪糕，在這個過程中要分好多環節：購買牛奶，對牛奶提純處理，放入工廠加工，加工後的商品要包裝，包裝後就去銷售……，這樣沒個環節就可以看做是一個階段；產品在不同的時候有不同的狀態，剛開始時只是白白的牛奶，進入生產後做成了各種造型，從冷凍庫拿出來後就變成雪糕（由液態變成固態=_=||）。每個形態就是一個狀態，那從液態變成固態經過了冰凍這一操作，這個操作就是一個決策。 一個狀態經過一個決策變成了另外一個狀態，這個過程就是狀態轉移，用來描述狀態轉移的方程就是狀態轉移方程。 經過這個例子相信大家對動態規劃有所瞭解了吧。 下面在說說我對動態規劃的另外一個理解： 用圖論知識理解動態規劃：把動態規劃中的狀態抽象成一個點，在有直接關聯的狀態間連一條有向邊，狀態轉移的代價就是邊上的權。這樣就形成了一個有向無環圖AOE網（為什麼無環呢？往下看）。對這個圖進行拓撲排序，刪除一個邊後同時出現入度為0的狀態在同一階段。這樣對圖求最優路徑就是動態規劃問題的求解。 二，動態規劃的適用範圍 動態規劃用於解決多階段決策最優化問題，但是不是所有的最優化問題都可以用動態規劃解答呢？ 一般在題目中出現求最優解的問題就要考慮動態規劃了，但是否可以用還要滿足兩個條件： 最優子結構（最優化原理） 無後效性 最優化原理在下面的最短路徑問題中有詳細的解答； 什麼是無後效性呢？ 就是說在狀態i求解時用到狀態j而狀態j就解有用到狀態k…..狀態N。 而求狀態N時有用到了狀態i這樣求解狀態的過程形成了環就沒法用動態規劃解答了，這也是上面用圖論理解動態規劃中形成的圖無環的原因。 也就是說當前狀態是前面狀態的完美總結，現在與過去無關。。。 當然，有是換一個劃分狀態或階段的方法就滿足無後效性了，這樣的問題仍然可以用動態規劃解。 三