計算機(jī)考研機(jī)試攻略 - 滿分篇-試讀

第PAGE第6頁目錄寫在前面的話 2關(guān)于N諾 4如何使用本書？ 5目錄 6第一章技巧之巔 7輸入輸出加速外掛 8調(diào)試技巧 10位運(yùn)算技巧 12考試最佳策略 16預(yù)處理與打表技巧 18對數(shù)器技巧 21第二章滿分之路上 24計算幾何基礎(chǔ) 25進(jìn)階背包問題 32毛毛蟲算法 36博弈類問題 40二分答案技巧 50前綴和技巧 53雙指針技巧 56第三章滿分之路中 58線段樹單點更新 59線段樹區(qū)間更新 65字符串匹配問題 72二分圖的匹配問題 79kmp算法的應(yīng)用 83路徑進(jìn)階問題 84圖的連通性問題 91單調(diào)隊列/棧 95第四章滿分之路下 98容斥與抽屜原理 99除法取模問題 103組合數(shù)取模類問題 105矩陣快速冪 109帶狀態(tài)壓縮的搜索 112數(shù)位類型動態(tài)規(guī)劃 116FFT快速傅里葉變換 120機(jī)試押題 125完結(jié)撒花 126N諾考研系列圖書 127計算機(jī)考研忠告 錯誤！未定義書簽。第一章技巧之巔建議大家在閱讀本書之前先閱讀本書的姊妹篇：。這本書是高分篇的加強(qiáng)版，適合學(xué)習(xí)完高分篇的同學(xué)繼續(xù)學(xué)習(xí)，拿到機(jī)試滿分。N輸入輸出加速外掛10WC++cincoutcincoutmain()里首先寫入下面兩行代碼。C++cin/cout1. ios_base::sync_with_stdio(0);2. cin.tie(0);cout.tie(0);100WCscanfprintf如果在這種情況下還超時，那么你就需要用到下面的輸入輸出加速外掛了。//適用于正負(fù)整數(shù)2. template<classT>3. inlineboolscan_d(T&ret){4. charc;intsgn;5. if(c=getchar(),c==EOF)return0;//EOF6.while(c!='-'&&(c<'0'||c>'9'))c=getchar();7.sgn=(c=='-')?-1:1;8.ret=(c=='-')?0:(c-'0');9.while(c=getchar(),c>='0'&&c<='9')ret=ret*10+(c-'0');10. ret*=sgn;11. return1;12.}13.inlinevoidout(intx){14.if(x>9)out(x/10);15.putchar(x%10+'0');16.}加速外掛原理：getchar的速度快于 scanf的速度速度比較getchar > scanf > cinputchar > printf > 參考代碼1. 1n的和2. #include<bits/stdc++.h>3. usingnamespacestd;4.5. //適用于正負(fù)整數(shù)6. template<classT>7. inlineboolscan_d(T&ret){8. charc;intsgn;9. if(c=getchar(),c==EOF)return0;//EOF10. while(c!='-'&&(c<'0'||c>'9'))c=getchar();11. sgn=(c=='-')?-1:1;12. ret=(c=='-')?0:(c-'0');13. while(c=getchar(),c>='0'&&c<='9')ret=ret*10+(c-'0');14. ret*=sgn;15. return1;16.}17.inlinevoidout(intx){18. if(x>9)out(x/10);19. putchar(x%10+'0');20.}21.請注意只有在大量輸入或大量輸出的時候才能看出時間的區(qū)別22.intmain(){23. intn;24. scan_d(n//加速輸入25. longlongsum=0;26. for(inti=1;i<=n;i++)27. sum+=i;28. out(sum);//加速輸出29. return0;30.}PAGEPAGE10頁調(diào)試技巧快速定位錯誤的調(diào)試技巧。會再問了。其實，斷點調(diào)試也不在我們的討論范圍之內(nèi)。巧。但是我們的機(jī)試有一些特殊的情況。1、機(jī)試的代碼往往很短，幾行到幾十行不等。2、比賽中爭分奪秒，我們對調(diào)試時間要求更為迫切。3、我們的錯誤往往是由于代碼細(xì)節(jié)沒考慮周全導(dǎo)致的。所以，斷點調(diào)試更適于項目代碼中且對時間的迫切度沒有那么高的情況。接下來，給大家介紹一種超級棒的調(diào)試技巧，當(dāng)你熟練掌握它以后你會深深的迷戀上它。輸出調(diào)試顧名思義，就是通過輸出的方式定位我們的錯誤所在。大部分沒有足夠調(diào)試經(jīng)驗的同學(xué)使用輸出調(diào)試的時候，不知道應(yīng)該如何使用輸出調(diào)試。如果從前往后逐條語句輸出調(diào)試去排查錯誤，那么很容易要找很久。不知道同學(xué)們是不是發(fā)現(xiàn)了點什么，對，沒錯，上面兩種方法是不是就是順序查找的方法。那么，與此對應(yīng)的就應(yīng)該是二分查找的方法。使用二分查找的思想來調(diào)試定位錯誤，可以更快，更節(jié)約時間。特別注意：輸出調(diào)試完成之后提交代碼之前一定要刪除或注釋掉調(diào)試信息。位運(yùn)算技巧速度比較取模時間>四則運(yùn)算時間>位運(yùn)算時間1. 1. if(a%2==1){3. }a/=2;2.1. 1. if(a&1==1){3. }a>>=1;2.異或運(yùn)算的特殊性異或同一個數(shù)2次或者偶數(shù)次，那么本身的值不變。例如：a^b^bax^y^y^y^y=x接下來我們來看一下它的應(yīng)用。缺頁問題缺頁問題題目描述：PAGEPAGE13頁小明的漫畫書撕了扔進(jìn)垃圾桶。小明的漫畫書撕了扔進(jìn)垃圾桶。小明放學(xué)后從垃圾桶里將漫畫書撿了回來，缺發(fā)現(xiàn)漫畫書少了一頁。小明的漫畫書一共有N頁嗎？第一行輸入一個整數(shù)第一行輸入一個整數(shù)N（N<1000000），表示小明書的總頁數(shù)。第二行輸入N-1個數(shù)整數(shù)，代表小明找到的頁碼。輸出描述：請輸出小明缺失的頁碼在單獨的一行。請輸出小明缺失的頁碼在單獨的一行。請注意：本題的空間很小，要求你盡量不使用額外的空間來解決。662153662153輸出樣例#:44DreamJudge1506題目來源：DreamJudge15061NN-1個數(shù)，那么答案就是缺失的那個數(shù)。參考代碼1. #include<bits/stdc++.h>2. usingnamespacestd;3.4. intmain(){PAGEPAGE14頁5. intn,x;6. scanf("%d",&n);7. intsum=0;8. for(inti=1;i<=n;i++){9. sum^=i;10. }11. for(inti=1;i<n;i++){12. scanf("%d",&x);13. sum^=x;14. }15. printf("%d\n",sum);16. return0;17.}常見位運(yùn)算問題位操作實現(xiàn)乘除法數(shù)a向右移一位，相當(dāng)于將a除以2；數(shù)a向左移一位，相當(dāng)于將a乘以2inta=2;2.2. a>>1;>13.a<<1;>4取相反數(shù)1，也即~n+1(n^-1)+1。1. 1. /*判斷是否是奇數(shù)*/3. {5. }return(n&1==1);4.2. boolis_odd(intn)不用臨時變量交換兩個數(shù)1. a^=b;2.2. b^=a;//相當(dāng)于bb^a^b3. a^=b;1. 1. count=03.a=a&(a-1);5. }count++;4.2. while(a){DreamJudge1118將軍的書題目練習(xí)DreamJudge1118將軍的書考試最佳策略下面我們來講一下如何應(yīng)對一場考研的上機(jī)考試。提前準(zhǔn)備1、算法模板一定要提前準(zhǔn)備好，不管是單獨打印還是記錄在書上。2、算法模板一定要驗證它的正確性，在驗證的過程中也知道了該如何使用。3、手機(jī)調(diào)成靜音模式，最好再開一個飛行模式，不要上交以備不時之需。開考前1、驗證鼠標(biāo)鍵盤是否可用，如果不可用及時向老師反應(yīng)，更換電腦。2IDE（如：codeblocks）是否可用，如果不可用及時向老師反應(yīng)，更換電腦。3、提前將頭文件和主函數(shù)框架寫好，最好創(chuàng)建兩個文件，代碼復(fù)制一份就行。因為在做題過程中遇到卡題情況，可以及時切換到另一道題上繼續(xù)寫?？荚囍?、機(jī)試中的題目難度不是從簡單到難，難度是隨機(jī)的，所以剛開始一定要將所有題目都看一遍。2、找到你認(rèn)為最簡的那道題開始做，記住，一定要從最簡單的題目開始做。3、考試過程中要注意看排行榜，通過人數(shù)最多的題目一般都是最簡單的題目。4、注意：要看通過人數(shù)的多少來判斷難易程度，而不是第一個人通過的時間來判斷。5、如果你的水平強(qiáng)，可以選擇先做那種代碼不長但是需要算法思維的題，快速解出來將6、之所以要赤裸裸的將上一條寫出來，就是為了告誡那些頭鐵的同學(xué)，不要在一棵樹上吊死，都走復(fù)試這一步了，還這么死腦筋基本沒得救了，變多。8、當(dāng)無法通過一個題的時候，先看看有沒有其他能做的題，如果也沒有其他題能做了。度。如果是老師自己構(gòu)造的數(shù)據(jù)，你睡著都會笑醒。9、不要被題目的數(shù)據(jù)范圍嚇到，有可能后臺都是小數(shù)據(jù)，沒有更好的解法的時候一定要試試暴力。速來看看能不能水過去。另一方面可以采用小數(shù)據(jù)暴力，大數(shù)據(jù)隨機(jī)的思想來解決問題。小數(shù)據(jù)暴力、大數(shù)據(jù)隨機(jī)據(jù)來驗證算法正確性，再加上兩組大數(shù)組驗證算法復(fù)雜度。舉例說明背包問題我們背包問題一般使用動態(tài)規(guī)劃來解，但是你不會怎么辦？那么我們就可以小數(shù)據(jù)暴力搜索，大數(shù)據(jù)直接貪心。對于數(shù)據(jù)不夠強(qiáng)的題就能水過去。更簡單的例子給你很多個數(shù)，要你從中找出最大的數(shù)。如果是這樣幾個數(shù)：527163如果是這樣幾個數(shù)：827163我們是不是只需要找到第一個就能找到最大那個數(shù)了一般情況下，判題數(shù)據(jù)就像上面那樣，你可以通過不嚴(yán)謹(jǐn)?shù)拇a通過題目。主要是領(lǐng)悟思想，不同的題都有不同策略。預(yù)處理與打表技巧預(yù)處理預(yù)處理是指將答案提前處理好然后再進(jìn)行查詢的方法。什么時候會用到預(yù)處理？查詢量特別大的時候。例題<10000）。10錯誤的超時解法1.1. #include<bits/stdc++.h>3.5. intmain(){7.scanf("%d"&t);//查詢次數(shù)9.intn;11.f[1]=1;13.for(inti=3;i<=n;i++){15.}17.}19.}return0;18.printf("%d\n",f[n]);16.f[i]=f[i-1]+f[i-2];14.f[2]=1;12.,&n);//k項10.while(t--){8.intt;6.4. intf[10005];2. usingnamespacestd;每一次查詢，我們都遞推了一遍斐波那契數(shù)列，如果每一次查詢的都是最后一項。那么最壞情況就是：100000*10000，必然是會超時的。正確的預(yù)處理解法1.1. #include<bits/stdc++.h>3.5. intmain(){7.f[2]=1;9.f[i]=f[i-1]+f[i-2];11.intt;13.while(t--){15.,&n);//k項17.}19.}return0;18.printf("%d\n",f[n]);16.intn;14.scanf("%d"&t);//查詢次數(shù)12.}10.for(inti=3;i<=10000;i++){8.f[1]=1;6.4. intf[10005];2. usingnamespacestd;可以發(fā)現(xiàn)兩段代碼驚人的相似，有什么區(qū)別呢？區(qū)別在于下面的代碼只會遞推一遍斐波那契數(shù)列，然后將所有的答案都存儲于f數(shù)組中。一般打表技巧際需求去直接輸出提前記錄好的答案。例題x(1<=x<=10)解析：110分別求出來，可能要等上幾分鐘，然后直接判斷輸入的值對應(yīng)輸出結(jié)果即可。打表找規(guī)律從而幫助我們解出該題。例題輸入一個整數(shù)a(a<10^9),b可以取任意值，求a%b的可能產(chǎn)生多少種不同的結(jié)果。baa=1ans=1，a，ans=a/2+1，a時，ans=a/2+2。DreamJudge1488數(shù)字填充題目練習(xí)DreamJudge1488數(shù)字填充對數(shù)器技巧大多數(shù)同學(xué)應(yīng)該都有過這樣的經(jīng)歷...?。孔タ?..然后開始瘋狂diss管理員，管理員在嗎？你這個小破站，為什么不能告訴我是哪一組數(shù)據(jù)出錯了？你有沒有考慮過我們這種新手的感受？你看看別人某站，錯誤還會給我反饋錯誤的數(shù)據(jù)，你們是不是技術(shù)不行?。块g去查找去比較，還不如再認(rèn)真檢查一下代碼。使用對數(shù)器進(jìn)行對拍，可以快速的找到的你的代碼錯誤所在。然后比較你的代碼的輸出結(jié)果和正確代碼的輸出結(jié)果是否一致，從而來驗證你的代碼的正確性。當(dāng)然，隨機(jī)的數(shù)據(jù)越多，正確性也就越高。下面我們舉個排序的例子別人的正確的排序的算法代碼，我如何比較呢？我的排序算法代碼1. for(inti=1;i<=n;i++)2. for(intj=1;j<n;j++)3. if(b[j]>b[j+1])4. swap(b[j],b[j+1]);正確的排序算法代碼1.sort(c+1,c+n+1);下面就是完整的對數(shù)器使用的模板1. #include<bits/stdc++.h>2. usingnamespacestd;3.4. structnode{5. inta[105];//隨機(jī)的數(shù)6. intb[105];//我的方法排序后的數(shù)7. intc[105];//正確的方法排序后的數(shù)8. intn;9. 按照題意隨機(jī)一些輸入數(shù)據(jù)10. voidRand(){11. n=rand()%100+1;12. for(inti=1;i<=n;i++)13. a[i]=rand()%10000;14. }15. 使用我的解法得到的答案16. voidMy_method(){17. for(inti=1;i<=n;i++)18. b[i]=a[i];19. for(inti=1;i<=n;i++)20. for(intj=1;j<n;j++)21. if(b[j]>b[j+1])22. swap(b[j],b[j+1]);23. }24. 使用其他正確的解法得到的答案25. voidRight_method(){26. for(inti=1;i<=n;i++)27. c[i]=a[i];28. sort(c+1,c+n+1);29. }30. 比較我的答案和正確答案是否一致31. 如果不一致輸出測試數(shù)據(jù)然后分析32. intCheck(){33. for(inti=1;i<=n;i++){34. if(b[i]!=c[i]){35. printf("mycodeiserror!\n");36. printf("thetestdata:\n");37. for(intj=1;j<=n;j++){38. printf("%d",a[j]);39. }40. printf("\n");41. return1;42. }43. }44. return0;45. }46.};47.48.49.intmain(){50. srand(time(NULL));//將時間作為隨機(jī)種子51. intt100;//樣本大小52. while(t--){53. nodecode;54. code.Rand();55. code.My_method();56. code.Right_method();57. if(code.Check())return0;58. }59. printf("mycodeisright!\n");60.}最后分析自己的算法問題所在。第二章滿分之路上90分以上的成績，題目不難的情況下甚至能拿到100分。在少數(shù)難度較大的院校也足夠拿到80分左右的分?jǐn)?shù)，如果你基礎(chǔ)比較薄弱，我們建議你掌握高分篇的內(nèi)容就可以了。本書滿分的把握。距離滿分只有一步之遙，你！愿意放棄嗎？中所涉及到的各類較難的問題。提示：滿分篇的內(nèi)容選擇性的學(xué)就行，不要求全部掌握，會其中一部分就很厲害了。計算幾何基礎(chǔ)二維坐標(biāo)下介紹一些定義：點：A(x1，y1), B(x2，y2),y2-y1)=(x, y)|AB|sqrtx*xy*y)點積x1*x2y1*y2。點積的結(jié)果是一個數(shù)值。a向向量b|a|*cos(a,b)ab上的投影，即點積是一個向量在另一個向量上的投影乘以另一個向量，且滿足交換律。x1*x2+y1*y2/(|a|*|b|)叉積x1*y2-x2*y1abz上，上面結(jié)果是它的模。是叉積的方向）叉積的集合意義：1ab為相鄰邊形成平行四邊形的面積。sin（a，b）180°為負(fù)值。3、叉積不滿足交換律應(yīng)用：若axb>0ab的順時針方向上若axb<0ab的逆時針方向上xb==0ab共線，但不確定方向是否相同2、判斷折線拐向，可轉(zhuǎn)化為判斷第三點在前兩的形成直線的順逆時針方向，然后判斷拐向。3、判斷一個點在一條直線的那一側(cè)，同樣上面的方法。4、判斷點是否在線段上，可利用叉乘首先判斷是否共線，然后在判斷是否在其上。5、判斷兩條直線是否想交（跨立實驗）ok。凸包凸多邊形凸多邊形是指所有內(nèi)角大小都在[0,π]凸包在平面上能包含所有給定點的最小凸多邊形叫做凸包。其定義為：SX的凸包。實際上可以理解為用一個橡皮筋包含住所有給定點的形態(tài)。是最小，如下圖。根據(jù)三角不等式，凸多邊形在周長上一定是最優(yōu)的。凸包的求法如何使用凸包算法的模板。凸包面積凸包面積題目描述：麥兜是個淘氣的孩子。一天，他在玩鋼筆的時候把墨水灑在了白色的墻上。再過一會，麥兜媽麥兜是個淘氣的孩子。一天，他在玩鋼筆的時候把墨水灑在了白色的墻上。再過一會，麥兜媽能告訴麥兜最小需要面積多大的凸多邊形才能把這些墨點蓋住嗎？現(xiàn)在，給出了這些墨點的坐標(biāo)，請幫助麥兜計算出覆蓋這些墨點的最小凸多邊形的面積。T，T，TN(0<N<=105NXiYi（0<=Xi,Yi<=2000），表示每個墨點的坐標(biāo)。每行的坐標(biāo)間可能包含多個空格。輸出描述：留一位即可，不需要多余的空格。輸入樣例#:2400100111200011.0輸出樣例#:1.0PAGEPAGE29頁0.00.0DreamJudge1113題目來源：DreamJudge1113解題分析：使用求凸包面積的算法模板即可。1. 1. #include<bits/stdc++.h>3. usingnamespacestd;5. inlinedoublesqr(doublex){returnx*x;}7.doublex,y;9.point(double_x,double_y):x(_x),y(_y){}11.booloperator==(constpoint&b)const{13.14.}pointoperator-(constpoint&b)const{16.}18.intoperator^(constpoint&b)const{20.}22.intoperator*(constpoint&b)const{24.}26.booloperator<(constpoint&b)const{28.}30.structline{32.line(){}points,e;31.29.};returnx-b.x==0?y-b.y<0:x<b.x;27.//重載小于號 求最左下角的點25.returnx*b.x+y*b.y;23.//點積21.returnx*b.y-y*b.x;19.//叉積17.returnpoint(x-b.x,y-b.y);15.returnx-b.x==0&&y-b.y==0;12.//判斷兩點相同10.point(){}8.6. structpoint{4. constintmaxn=1005;2. #include<math.h>PAGEPAGE29頁33. line(point_s,point_e):s(_s),e(_e){}34.};35.doubledis(pointa,pointb){//求兩點之間的距離36. returnsqrt(1.0*sqr(a.x-b.x)+1.0*sqr(a.y-b.y));37.}38.structpolygon{39. intn;40. pointp[maxn];41. voidadd(pointq){p[n++]=q;}42. structcmp{43. pointp;44. cmp(constpoint&p0):p(p0){}45. booloperator()(constpoint&aa,constpoint&bb){46. pointa=aa,b=bb;47. intk=(a-p)^(b-p);48. if(k==0){49. returndis(a,p)-dis(b,p)<0;50. }51. returnk>0;52. }53. };54. //極角排序先找到左下角的點55. 的'<'56. voidnorm(){57. pointmi=p[0];58. for(inti=1;i<n;i++)mi=min(mi,p[i]);59. sort(p,p+n,cmp(mi));60. }61. 0--n-162. voidGraham(polygon&convex){63. norm();64. int&top=convex.n;65. top=0;66. if(n==1){67. top=1;convex.p[0]=p[0];return;68. }69. if(n==2){70. top=2;convex.p[0]=p[0];convex.p[1]=p[1];71. if(convex.p[0]==convex.p[1])top--;72. return;73. }74. convex.p[0]=p[0];convex.p[1]=p[1];top=2;75. for(inti=2;i<n;i++){PAGEPAGE30頁76.76.while(top>1&&((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0)top--;78.}80.}82.doublesum=0;84.returnsum/2.0;86.};88.intmain(){90.cin>>t;92.intn,x,y;cin>>n;C.n=0;94.cin>>x>>y;96.}98.doubleres=ans.getarea();100.}102.}return0;101.printf("%.1lf\n",res);99.polygonans;C.Graham(ans);97.C.add(point(x,y));95.for(inti=0;i<n;i++){93.while(t--){91.intt;89.87.polygonC;}85.for(inti=0;i<n;i++)sum+=(p[i]^(p[(i+1)%n]));83.doublegetarea(){//求凸包的面積81.if(convex.n==2&&(convex.p[0]==convex.p[1]))convex.n--;79.convex.p[top++]=p[i];77.總結(jié)：對于機(jī)試中的計算幾何來說，記住上面的算法模板并知道是如何使用的即可。簡單的變形應(yīng)用50小明最多可以放多少頭牛？PAGEPAGE31頁求凸包的面積，將凸包面積/50即為可以放牛的數(shù)量。題目練習(xí)DreamJudge1160球的半徑和體積DreamJudge1183FrecklesDreamJudge1211矩形相交DreamJudge1596球形空間產(chǎn)生器DreamJudge1615多邊形的面積DreamJudge1620放牧DreamJudge1621玩具進(jìn)階背包問題在高分篇中，我們學(xué)習(xí)了簡單背包問題，和01背包問題。當(dāng)時我們用的二維數(shù)組來進(jìn)行遞推的，仔細(xì)思考就可以發(fā)現(xiàn)其實我們沒有必要開這么大的數(shù)可完成這個過程。我們還可以進(jìn)一步壓縮空間，前半段和后半段也可以進(jìn)行滾動。滾動數(shù)組（上下滾動）1. #include<stdio.h>2. #include<string.h>3.4. intmain(){5. int{0};//01進(jìn)行滾動6. intw[1005];7. ints,n;8. while(scanf("%d%d",&s,&n)!=EOF){9. for(inti=1;i<=n;i++)10. scanf("%d",&w[i]);11. memset(dp,0,sizeof(dp));12.dp[0][0]=1;13. for(inti=1;i<=n;i++){14. intnow=i&1;15. ;;){//i-1i^116.if(dp[now^1][j]==1)dp[now][j]=1;17.if(j-w[i]>=0&&dp[now^1][j-w[i]]==1)dp[now][j]=1;18. }19. }20. if(dp[n&1][s]==1)printf("YES\n");21. elseprintf("NO\n");22. }23. return0;24.}滾動數(shù)組（前后滾動）1. #include<stdio.h>2. #include<string.h>3.4. intmain(){5. intdp[1005{0};//前后滾動6. intw[1005];7. ints,n;8. while(scanf("%d%d",&s,&n)!=EOF){9. for(inti=1;i<=n;i++)10. scanf("%d",&w[i]);11. memset(dp,0,sizeof(dp));12. dp[0]=1;13. for(inti=1;i<=n;i++){14. for(intjsj0;j//從后往前枚舉15. if(j-w[i]>=0&&dp[j-w[i]]==1)dp[j]=1;16. }17. }18. if(dp[s]==1)printf("YES\n");19. elseprintf("NO\n");20. }21. return0;22.}完全背包NV的背包，每種物品都有無限件可用ic[i]，價大。完全背包問題完全背包問題題目描述：n（每一種有無數(shù)個Wi,ViW的物品，求所有方案中價值總和的最大值。輸入包含多組測試用例，每一例的開頭為兩位整數(shù)n、W（1<=n<=10000,1<=W<=1000），接下來有n行，每一行有兩位整數(shù)Wi、Vi（1<=Wi<=10000,1<=Vi<=100）輸入包含多組測試用例，每一例的開頭為兩位整數(shù)n、W（1<=n<=10000,1<=W<=1000），接下來有n行，每一行有兩位整數(shù)Wi、Vi（1<=Wi<=10000,1<=Vi<=100）輸出描述#:PAGEPAGE34頁輸出為一行，即所有方案中價值總和的最大值。輸出為一行，即所有方案中價值總和的最大值。輸入樣例#:3412253735233445107107題目來源：DreamJudge1569DreamJudge1569題目解析：這個題是一個完全背包的算法模板題，直接套用完全背包的模板即可。參考代碼1. #include<bits/stdc++.h>2. usingnamespacestd;3.4. intn,W,v[10005],w[10005],dp[1005];5. intmain(){6. while(cin>>n>>W){7. for(inti=0;i<n;i++)8. cin>>w[i]>>v[i];9. memset(dp,0,sizeof(dp));10. for(inti=0;i<n;++i) //種類11. for(intj=w[i];j<=W;++j//重量從小到大枚舉12. dp[j]=max(dp[j],dp[j-w[i]]+v[i]);13. cout<<dp[W]<<endl;14. }PAGEPAGE35頁15. return0;16.}想用二進(jìn)制方式拆分求解，另一種方法是用單調(diào)隊列來維護(hù)。PAGEPAGE36頁毛毛蟲算法式故得名。SubsequenceSubsequence題目描述：S（S<100000000）NNS，并以一輸出描述：對于每種情況，程序都必須將結(jié)果打印在輸出文件的單獨一行上。如果沒有答案，則打印對于每種情況，程序都必須將結(jié)果打印在輸出文件的單獨一行上。如果沒有答案，則打印0。21015210155135107492851112345輸出樣例#:223DreamJudge1570題目來源：DreamJudge1570這是一個典型的毛毛蟲算法的應(yīng)用實例，下面詳細(xì)講解一下算法過程。asSas+...at-1，這時as+1+...+at-2<as+...+at-2<Sas+1Sas+1+...+at’-1t<=t’一性質(zhì)便可以設(shè)計出如下算法：stsum0初始化。sumSsumatt1.>=Sres=min(res,t-s)。sumas，s1然后回到(2)。參考代碼#include<bits/stdc++.h>usingnamespacestd;3.4. inta[100005];5. intmain(){6.intT,n,s;7.scanf("%d",&T);8.while(T--){9.scanf("%d%d",&n,&s);10.for(inti=1;i<=n;i++)11.scanf("%d",&a[i]);12.intl=1,r=1,sum=0,ans=0x3f3f3f3f;13.while(1){while(sum<s&&r<=n)sum+=a[r++];if(sum<s)break;ans=min(ans,r-l);17. sum-=a[l++];18. }if(ans==0x3f3f3f3f)printf("0\n");elseprintf("%d\n",ans);21. }22. return0;23.}DreamJudge1591逛畫展題目練習(xí)DreamJudge1591逛畫展滑動窗口算法毛毛蟲算法有時候又叫做滑動窗口算法，我們可以換個方式來理解這類解題思想。協(xié)議的一種應(yīng)用，用于網(wǎng)絡(luò)數(shù)據(jù)傳輸時的流量控制，以避免擁塞的發(fā)生。該協(xié)議允許發(fā)送方此該協(xié)議可以加速數(shù)據(jù)的傳輸，提高網(wǎng)絡(luò)吞吐量。大小，有時也可以是固定窗口大小。應(yīng)用在數(shù)組和字符串上。（長度等xxx（的xx”這類問題都可以使用該方法進(jìn)行解決。需要注意的是，滑動窗口算法更多的是一種思想，而非某種數(shù)據(jù)結(jié)構(gòu)的使用。實戰(zhàn)例子例題：盡可能使字符串相等給你兩個長度相同的字符串，s和t。將s中的第i個字符變到t中的第i個字符需要|s[i]t[i]|（開銷可能為也就是兩個字符的ASCII碼值的差的絕對值。意味著字符串的轉(zhuǎn)化可能是不完全的。st如果s中沒有子字符串可以轉(zhuǎn)化成t中對應(yīng)的子字符串，則返回0。示例1：輸入：s="abcd",t="bcdf",cost=3輸出：3解釋：s"abc""bcd"3，3。示例2：輸入：s="abcd",t="cdef",cost=3輸出：1解釋：st21。示例3：輸入：s="abcd",t="acde",cost=0輸出：1解釋：你無法作出任何改動，所以最大長度為1。博弈類問題我們把機(jī)試中會考到的博弈問題分為了下面四類1、簡單博弈問題2、巴什博奕3、尼姆博弈4、威佐夫博弈兩個人都足夠聰明，然后判斷最終誰會取得勝利。簡單博弈一眼能看出勝敗關(guān)系的博弈或者存在必勝或必敗的博弈。簡單博弈簡單博弈題目描述：2*nk并且這K枚硬幣必須相鄰才能拿，每次最少要拿走1枚硬幣，沒有硬幣拿的一方輸?shù)舯荣悺＜僭O(shè)兩個人都足夠聰明，甲先拿，問甲能取得最后的勝利嗎？多組數(shù)據(jù)輸入。多組數(shù)據(jù)輸入。nk。（k<=n，n<=10^9）輸出描述：11輸入樣例#:11輸出樣例#:PAGEPAGE41頁LOSELOSEDreamJudge1632題目來源：DreamJudge1632對稱的位置拿一樣的數(shù)量，這樣不管甲怎么拿，都是乙必勝。參考代碼1.1. #include<stdio.h>3. intmain(){5.while(scanf("%d%d",&n,&k)!=EOF){7.}9. }return0;8.printf("LOSE\n");6.intn,k;4.2.簡單變種問題方獲勝。問是否有一種策略可以判斷是先手獲勝還是后手獲勝？如果有，策略是什么？提示：也是利用圓的對稱性PAGEPAGE42頁巴什博奕問誰會勝利？我們從最簡單的情景開始分析1?m個時，毫無疑問，先手必勝m+2?2mm+1個，先手必勝我們不難發(fā)現(xiàn)，面臨m+1個石子的人一定失敗。m+1個我們考慮往一般情況推廣設(shè)當(dāng)前的石子數(shù)為n=k?(m+1)+rrx終一定失敗n=k?(m+1)xm+1?x個，這樣下去先手一定失敗BraveBraveGame題目描述：十年前讀大學(xué)的時候，中國每年都要從國外引進(jìn)一些電影大片，其中有一部電影就叫《勇敢者十年前讀大學(xué)的時候，中國每年都要從國外引進(jìn)一些電影大片，其中有一部電影就叫《勇敢者專題；所以，大家現(xiàn)在玩的也是“勇敢者的游戲”，這也是我命名這個題目的原因。PAGEPAGE43頁的結(jié)果，我也相信大家一定能做到的~的結(jié)果，我也相信大家一定能做到的~勇敢者要玩的第一個游戲是什么呢？很簡單，它是這樣定義的：1、 本游戲是一個二人游戲;2、 有一堆石子一共有n個；3、 兩人輪流進(jìn)行;4、 每走一步可以取走1…m個石子；5、 最先取光石子的一方為勝；如果游戲的雙方使用的都是最優(yōu)策略，請輸出哪個人能贏。如果先走的人能贏，請輸出“first”，否則請輸出“second”，每個實例的輸出占一行。輸入描述：如果先走的人能贏，請輸出“first”，否則請輸出“second”，每個實例的輸出占一行。輸出描述：共T行，如果對于這組數(shù)據(jù)存在先手必勝策略則輸出Yes，否則輸出No，每個單詞一行。共T行，如果對于這組數(shù)據(jù)存在先手必勝策略則輸出Yes，否則輸出No，每個單詞一行。2232223243輸出樣例#:firstfirstsecondDreamJudge1636題目來源：DreamJudge1636題目解析：n=0的時候后手必勝(P態(tài)),n=1~m這幾種狀態(tài)由于先手(N態(tài))。n=m+1時，因為先手無論取走幾個都會使后手一次全部取走導(dǎo)致后手必勝；n=m+2~2*mm+1個，導(dǎo)致無論后手取幾個，最后都會使先手一次全部取完，導(dǎo)致先手必勝。PAGEPAGE44頁m+1的倍數(shù)個，由n%(m+1)=0時，后手必勝，否則先手必勝。參考代碼1.1. #include<stdio.h>3. intmain(){5.scanf("%d",&t);7.intn,k;9.if(n%(k+1)==0){11.}13.printf("first\n");15.}17.}return0;16.}14.else{12.printf("second\n");10.scanf("%d%d