楓蕭蕭

摘要： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1406這道題讓我見識了什么叫做坑跌。。。。用c輸入的時候一定要注意格式，我因為輸入格式沒控制好，導致一直以為算法錯了，調了一個多小時。。。用c++貌似好的多，沒有神馬空格換行的困擾，看來以后碰到格式復雜的輸入可以考慮用c++的流。。。。代碼如下：prim#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;# 閱讀全文

摘要： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1082很明顯的最短路題，但是提到最短路我就想起dj算法，但是這道題沒有固定從某一個點走，而是要求所有的最短路，因此用Floyd算法比較合適因為不常寫Floyd，因此郁悶了老半天，要注意一定循環先k，再i，再j，看來以后算法都要實現一遍。。。最短路還有dp和spfa可以用，但是我都只是了解了個皮毛，看會了再用吧。。。代碼如下：#include<iostream>#include<cstring>#include<cstdio>using 閱讀全文

摘要： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1008題目很長，讀完后很容易理解錯。題目中要求的不是移動三角形而是對整個矩形進行移動來達到目的?。?！題目讀懂后就容易寫了，很明顯是dfs+回溯的題，注意相同的矩形可以存儲在一塊，可以方便dfs。ac后發現運行時間竟達到5000+ms，還沒超時，看到有0s過的，無奈，只能仰視~~Orz。。。代碼如下：#include<iostream>#include<cstdio>#include<cstring>using namespace std 閱讀全文

摘要： http://acm.nyist.net/JudgeOnline/problem.php?pid=203做了一上午的01背包，快中午的時候想到了這道題，最短路加01背包，思路很簡單，但是runtime error和wa了幾次runtime time原因是數組開小了，但是我現在還不明白為嘛要那么大?。?！wa是因為一個小陷阱：可能同兩個城市之間有多個數據，要取最短的，而我默認的是后面輸入的覆蓋前面輸入的；這樣的陷阱以后需要注意！??！代碼如下：#include<iostream>#include<cstdio>#include<cstring>#include&l 閱讀全文

摘要： http://acm.nyist.net/JudgeOnline/problem.php?pid=456題目看上去和上次做的搜索nyoj 325 zb的生日很像，但是再用暴力搜索dfs的結果必然是TLE~~解決這題的模型是01背包問題：先計算所有的郵票值sum，然后sum/2作為容量，每一張郵票的值代表一個物體的體積和價值，這就將問題轉化為了經典的01背包問題。我又用這個思想做了一些zb的生日，結果超時了，又優化了一下才勉強過去，很無語。。。代碼如下：#include<iostream>#include<cstdio>#include<cstring>usi 閱讀全文

摘要： http://acm.nyist.net/JudgeOnline/problem.php?pid=44http://acm.nyist.net/JudgeOnline/problem.php?pid=104nyoj 44 字串和是經典的動態規劃問題，104題將44題的一維最大和擴展到矩陣中，求子矩陣的最大和。思路大體還是一致的，先來說nyoj44吧。最大字段和問題用枚舉，分治和動態規劃都能解決，時間復雜度分別為O(n^2), O(nlogn), O(n)。dp的狀態方程: b[j] = max{b[j-1] + a[j], a[j]}, 1<= j <= n； if b[j-1] 閱讀全文

摘要： http://acm.nyist.net/JudgeOnline/problem.php?pid=16很經典的dp題。。。剛開始想用貪心做，做了一半改成dp了，后來聽說貪心貌似也可以。。。dp的話貪心前做的一些排序準備工作就沒用了~~剛開始我用鄰接矩陣存儲結果內存達到了4000+，很不爽，又用vector優化了下，這才滿意。大致思路：先將數據根據能否嵌套化為圖的表示方法，一個DAG，然后在DAG上動態規劃dp方程：d(i) = max(d(j) + 1), (i, j) 屬于圖代碼如下：#include<iostream>#include<cstdio>#include 閱讀全文

摘要： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2081剛看到最短路就想到了bfs搜索，但是看完題后發現bfs搜索解決完最短路問題后不好處理炸彈問題。我想過在state里邊加上一個Boolean常量，來判斷這個最短路是否過地雷，后來突然想到可以再dfs一下來判斷過雷的最短路徑的數目，所以那個方法就沒有再嘗試。dfs很容易想到要剪枝，有點像hdu1010的路徑剪枝吧。。。悲劇的是我一直以為要求的是間諜被炸的概率，因此一直wa，更悲劇的時樣例數據正好是50.00%，因此這個錯誤好難發現。。。?？村e題的孩紙傷不起啊。。。。要吸 閱讀全文

摘要： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2050同樣是一道bfs題，只不過難在如何對狀態進行存儲。我想了好長時間也沒思路，看了別人的代碼，理解后才寫出來的。沒法用狀態數組標記(可能用set可以實現吧，沒試過~~)，所以用二進制來存儲，比如都是白色，1111111111111111，最大時為2^16-1 = 65535,用很小的數組就可以存下。因為用到了二進制，就少不了位運算，因此要理解位運算后才能很好的理解這道題的算法。代碼如下：#include<iostream>#include<cstdio 閱讀全文

摘要： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1438還是很經典的搜索題，有意思的是把原來的二維迷宮改為了立體迷宮，用三維數組來存儲。易錯的是三維容易把坐標弄錯，我因為這wa了好多次。。。在紙上多畫畫就ok。代碼如下：#include<iostream>#include<cstdio>#include<queue>#include<cstring>using namespace std;int dx[] = {-1, 1, 0, 0, 0, 0};int dy[] = { 閱讀全文

摘要： http://acm.nyist.net/JudgeOnline/problem.php?pid=37回文字符串時間限制：3000 ms | 內存限制：65535 KB難度：4描述所謂回文字符串，就是一個字符串，從左到右讀和從右到左讀是完全一樣的，比如"aba"。當然，我們給你的問題不會再簡單到判斷一個字符串是不是回文字符串。現在要求你，給你一個字符串，可在任意位置添加字符，最少再添加幾個字符，可以使這個字符串成為回文字符串。輸入第一行給出整數N（0<N<100）接下來的N行，每行一個字符串，每個字符串長度不超過1000.輸出每行輸出所需添加的最少字符數樣例輸入 閱讀全文

摘要： http://acm.nyist.net/JudgeOnline/problem.php?pid=214單調遞增子序列(二)時間限制：1000 ms | 內存限制：65535 KB難度：4描述給定一整型數列{a1,a2...,an}（0<n<=100000），找出單調遞增最長子序列，并求出其長度。如：1 9 10 5 11 2 13的最長單調遞增子序列是1 9 10 11 13，長度為5。輸入有多組測試數據（<=7）每組測試數據的第一行是一個整數n表示序列中共有n個整數，隨后的下一行里有n個整數，表示數列中的所有元素.每個整形數中間用空格間隔開（0<n<=1000 閱讀全文

摘要： http://acm.nyist.net/JudgeOnline/problem.php?pid=2014.作業題 小白同學這學期有一門課程叫做《數值計算方法》，這是一門有效使用數字計算機求數學問題近似解的方法與過程，以及由相關理論構成的學科... 今天他們的Teacher S，給他們出了一道作業題。Teacher S給了他們很多的點，讓 他們利用拉格朗日插值公式，計算出某嚴格單調函數的曲線。現在小白抄下了這些點，但是問題出現了，由于我們的小白同學上課時走了一下神，他多抄下來很多點，也就是說，這些 點整體連線不一定還是嚴格遞增或遞減的了。這可怎么處理呢。為此我們的小白同學制定了 以下的取點規則 閱讀全文

摘要： http://acm.hdu.edu.cn/showproblem.php?pid=1175連連看Time Limit: 20000/10000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 7173Accepted Submission(s): 1847Problem Description“連連看”相信很多人都玩過。沒玩過也沒關系，下面我給大家介紹一下游戲規則：在一個棋盤中，放了很多的棋子。如果某兩個相同的棋子，可以通過一條線連起來（這條線不能經過其它棋子），而且線的轉折次數不超過 閱讀全文

摘要： http://acm.hdu.edu.cn/showproblem.php?pid=1072NightmareTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3220Accepted Submission(s): 1636Problem DescriptionIgnatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. 閱讀全文