題目分類
|
| Adventures in Moving - Part IV |
DP |
| Pairsumonious Numbers |
搜索 |
| Snow Clearing |
簡(jiǎn)單題 |
|
|
| Stack 'em Up |
模擬 |
Adventures in Moving - Part IV：
這題DP的階段和決策都非常明顯。g[i][j]=min( g[i-1][j+dis[i]-dis[i-1]-buy]+buy*pirce[i] )
g[i][j]表示將要離開(kāi)第i個(gè)加油站時(shí)，有j升汽油，所要花費(fèi)的最少的錢。
Pairsumonious Numbers ：
首先 n==3 時(shí)很容易求出答案，a1+a2, a1+a3, a2+a3,兩兩相加再減去另一個(gè)
然后 n > 3 時(shí)首先我們排序，有順序就是成功的一半，
如果那 n 個(gè)數(shù)的大小是 a1 < a2 < a3 < ... < an
那么最小的是 a1+a2, 次小的是 a1+a3，如果我們知道 a2+a3 在哪 那該多好啊
幸運(yùn)的是 a2+a3只可能出現(xiàn)在第 3 位到第 n 位之間，n又是小于10的數(shù)，那我們只要枚舉
每種情況就可以了
這樣我們就能求出a1 , a2, a3 那對(duì)解題有什么用呢？
這時(shí)我們把 a1+a2, a1+a3, a2+a3 刪掉，剩下的最小的是不是肯定只有 a1+a4,那是不是
a4也求出來(lái)了
接著我們把 a1+a4, a2+a4, a3+a4都刪掉，剩下最小的不就是 a1+a5了嗎
不斷進(jìn)行上述過(guò)程就能求出答案
至于有相同元素的時(shí)候，很容易就知道也符合上述做法，正因?yàn)橛邢嗤兀虚g可用multiset
實(shí)現(xiàn)上述功能
Snow Clearing：
只需要把每條街加起來(lái)再乘以2就是總的距離，除以速度然后化成時(shí)間即可！
Stack 'em Up：
這題只要把題意看懂之后，就沒(méi)問(wèn)題了。首先給你n種洗牌策略，然后再給你若干個(gè)k，在前一次洗好的牌的基礎(chǔ)上，按照第k種洗牌策略洗。每洗一次，輸出目前的牌的順序。
Waterloo Local 2002.01.26
題目分類
|
| |
|
| Discrete Logging
|
求離散對(duì)數(shù) |
| Hardwood Species |
簡(jiǎn)單題 |
Forests
|
水題（stl運(yùn)用）
|
| A Star not a Tree? |
牛頓迭代法
|
Discrete Logging
：
求以b為基模于n的離散對(duì)數(shù)我們有O(n^0.5*logn)的算法
有興趣者可查看Shank's Baby-Step-Gaint-Step Algorithm
A Star not a Tree? ：
給你平面上 n ( n < 100)個(gè)點(diǎn)， 要求一個(gè)點(diǎn)p，使得 p 到各個(gè)點(diǎn)的距離之和最小
用牛頓迭代，能證明x,y偏導(dǎo)為0時(shí)，有最小值，但我不會(huì)證
（
回去學(xué)高數(shù)）
既然知道方程x，y偏導(dǎo)為0時(shí)有最小值，那就好辦了，取平均值為初值，然后不斷迭代，
但我精度調(diào)到 1e-4 才能過(guò)，這樣我的迭代跑了300ms，別人都跑0ms，總感覺(jué)有問(wèn)題
貼出迭代代碼，希望大家給我指正
while( !( zero(x1 - x0) && zero(y1 - y0) ) )
{
x0=x1, y0=y1;
for( fx=0, i=0; i < n; i++)
fx+= (x0 - p[i][0])/ sqrt( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
for(fxx=0, i =0; i < n; i++)
fxx+=( 2*(x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) ) / ( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
x1 = x0 - fx/fxx;
for(fy=0, i=0; i < n; i++)
fy+=(y0 - p[i][1])/ sqrt( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
for(fyy=0, i=0; i < n; i++)
fyy+=( (x0 - p[i][0])*(x0 - p[i][0]) + 2*(y0 - p[i][1])*(y0 - p[i][1]) ) / ( (x0 - p[i][0])*(x0 - p[i][0]) + (y0 - p[i][1])*(y0 - p[i][1]) );
y1=y0 - fy/fyy;
}
Waterloo local 2002.07.01
題目分類
|
| Hay Points |
簡(jiǎn)單題 |
| Jogging Trails |
圖論，中國(guó)郵路問(wèn)題 |
| Beavergnaw |
簡(jiǎn)單題 |
| Power Strings |
水題 |
Relatives
|
歐拉函數(shù)
|
Jogging Trails：
題目意思是給定一些點(diǎn)，然后一些邊，并且兩個(gè)點(diǎn)之間可能有多條邊，問(wèn)從一個(gè)點(diǎn)出發(fā)，遍歷完所有的邊至少一次且最后在回到出發(fā)點(diǎn)需要走的最少距離！
如果這個(gè)圖是歐拉圖，那么距離就是邊之和，一個(gè)圖存在歐拉圖的充要條件是每個(gè)定點(diǎn)的度為偶數(shù)！
但是如果不是歐拉圖，那么我們就要把這個(gè)圖變成歐拉圖，只需要添加一些邊，頂點(diǎn)的度全部為偶數(shù)就好了，因?yàn)橐粋€(gè)圖中奇數(shù)度頂點(diǎn)一定有偶數(shù)個(gè)！所以只要枚舉這樣的奇數(shù)度頂點(diǎn)，添加邊使其度為偶數(shù)，很明顯添加的邊不會(huì)影響其他偶數(shù)度頂點(diǎn)的奇偶性！并且由于要距離最小，所以添加的邊一定是這兩個(gè)頂點(diǎn)的最短距離！這一步可以用記憶化搜索實(shí)現(xiàn)！
歐拉函數(shù)的一些題目（
轉(zhuǎn)
http://hi.baidu.com/wuxyy/blog/item/33957f1ee03a1cf51bd5761d.html ）
歐拉函數(shù)入門(mén)題目：poj3090 Visible Lattice Points poj2407 Relatives
poj2478 Farey Sequence
歐拉函數(shù)高級(jí)應(yīng)用：poj2480 Longge's problem poj1091 跳蚤
跳蚤題目很有意思，推薦