這不是一個家庭作業問題,而是我打算知道這是如何學習編程。我保持登錄到TopCoder不是實際參與,而是基本瞭解問題是如何解決的。但就我所知,我不明白這個問題是什麼,以及如何將問題轉化爲能解決問題的算法。 剛纔我碰巧看到在中國舉辦的ACM ICPC 2010 World Finals
。這些小組分別給予習題集,其中一個是這樣的:能夠解決谷歌代碼堵塞問題集
Given at most 100 points on a plan with distinct x-coordinates,
find the shortest cycle that passes through each point exactly once,
goes from the leftmost point always to the right until it reaches the
rightmost point, then goes always to the left until it gets back to the
leftmost point. Additionally, two points are given such that the the path
from left to right contains the first point, and the path from right to
left contains the second point. This seems to be a very simple DP: after
processing the last k points, and with the first path ending in point a
and the second path ending in point b, what is the smallest total length
to achieve that? This is O(n^2) states, transitions in O(n). We deal
with the two special points by forcing the first path to contain the first
one, and the second path contain the second one.
現在我不知道我應該閱讀設置問題後解決。
,並有一個另外一個從谷歌代碼果醬:
Problem
In a big, square room there are two point light sources:
one is red and the other is green. There are also n circular pillars.
Light travels in straight lines and is absorbed by walls and pillars.
The pillars therefore cast shadows: they do not let light through.
There are places in the room where no light reaches (black), where only
one of the two light sources reaches (red or green), and places where
both lights reach (yellow). Compute the total area of each of the four
colors in the room. Do not include the area of the pillars.
Input
* One line containing the number of test cases, T.
Each test case contains, in order:
* One line containing the coordinates x, y of the red light source.
* One line containing the coordinates x, y of the green light source.
* One line containing the number of pillars n.
* n lines describing the pillars. Each contains 3 numbers x, y, r.
The pillar is a disk with the center (x, y) and radius r.
The room is the square described by 0 ≤ x, y ≤ 100. Pillars, room
walls and light sources are all disjoint, they do not overlap or touch.
Output
For each test case, output:
Case #X:
black area
red area
green area
yellow area
需要它的人誰的程序應該是應該能夠解決這些類型的問題?
我會很感激,如果有人可以幫助我解釋谷歌代碼堵塞問題集,因爲我希望參加今年的Code Jam
看看我能不能做東西。
謝謝。
更容易的問題?這個問題集是代碼堵塞 – JPro 2010-02-09 10:52:16
中的第一個問題,這裏是一個簡單的(r)問題,將羅馬數字中的阿拉伯數字(例如:X中的10,2010)轉換爲MMX,然後將這個反轉的羅馬字符轉換爲阿拉伯文XLIX到49 – Pentium10 2010-02-09 11:28:04
@ Pentium10 This是一箇舊帖子,但我的問題有點類似於OP,我可以理解這個問題,但我不知道在哪裏/如何開始解決它。所以一般我關注什麼?我是否錯過像NLP這樣的知識?機器學習?或某種CS理論(我不是大學畢業生)或者這只是簡單的算法設計和數學?學習像編譯器設計這樣特定的東西有幫助嗎? – gideon 2012-02-07 04:51:34