ACM/ICPC

ACM-ICPC 知識點 經驗

一:知識點 資料結構: 1,單,雙連結串列及迴圈連結串列 2,樹的表示與儲存,二叉樹(概念,遍歷)二叉樹的 應用(二叉排序樹,判定樹,博弈樹,解答樹等) 3,檔案操作(從文字檔案中讀入資料並輸出到文字文 件中) 4,圖(基本概念,儲存結構,圖的運算) 數學知識 1,離散數學知識的應用(如排列組合、簡 […]

P09揹包問題問法的變化

以上涉及的各種揹包問題都是要求在揹包容量(費用)的限制下求可以取到的最大價值,但揹包問題還有很多種靈活的問法,在這裡值得提一下。但是我認為,只要深入理解了求揹包問題最大價值的方法,即使問法變化了,也是不難想出演算法的。 例如,求解最多可以放多少件物品或者最多可以裝滿多少揹包的空間。這都可以根據具體問 […]

生日蛋糕(noi99)

經過幾天的研究。。。終於完成了生日蛋糕~(noi99)剪枝非常明顯~注意:2*(n-v)/r s>=opt,不能寫成2/r*(n-v) s,之前犯了這個錯誤,就tle,估計還可能是死迴圈。。。main函式裡就不要用for迴圈了,用了也會tle.3個重要的剪枝:當已有體積加上剩餘的最小體積大於總 […]