09 2007 檔案
[動(dòng)態(tài)規(guī)劃]pku1185
摘要: 經(jīng)典的狀態(tài)壓縮DP,狀態(tài)是f[i][j],表示第i行,以3進(jìn)制j為狀態(tài)。j的位代表一個(gè)格子,只能是:0表示第i行和第i - 1行都沒有炮兵,1表示第i行沒有炮兵而第i-1行有炮兵,2表示第i行有炮兵。然后用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。一開始我做了超時(shí),后來預(yù)處理了一下合法狀態(tài),快了不少,才AC。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku1163
摘要: 今天郁悶了,貼個(gè)小代碼
閱讀全文
[動(dòng)態(tài)規(guī)劃]動(dòng)態(tài)規(guī)劃總結(jié) by Amber
摘要: 動(dòng)態(tài)規(guī)劃總結(jié) by Amber
閱讀全文
[計(jì)算幾何]pku3391
摘要: 問題是求平面歐幾里德最小生成樹的第n - k小邊。
平面歐幾里德最小生成樹是經(jīng)典問題,可以做到O(nlogn)。具體做法是先對(duì)平面點(diǎn)進(jìn)行三角剖分,時(shí)間復(fù)雜度是O(nlogn),三角剖分的邊就是可能的在最小生成樹的邊。因?yàn)槭瞧矫鎴D,所以有O(n)條邊,在其上應(yīng)用 Kruscal 算法即可。
閱讀全文
漫談扭結(jié)
摘要: 漫談扭結(jié)
閱讀全文
[計(jì)算幾何]pku1673
摘要: 此問題可轉(zhuǎn)化為求三角形垂心。我的做法是設(shè)垂心坐標(biāo)為(x, y),然后利用垂直關(guān)系解方程。
閱讀全文
Ubuntu 6.10 @ Dell XPS M1210 安裝手記
摘要: Ubuntu 6.10 @ Dell XPS M1210 安裝手記
閱讀全文
[轉(zhuǎn)載]好友的一首小詩(shī)
摘要: 一首小詩(shī)……
閱讀全文
[計(jì)算幾何]平面點(diǎn)的曼哈頓最小生成樹
摘要: 平面點(diǎn)的曼哈頓最小生成樹
閱讀全文
[計(jì)算幾何]pku1624
摘要: 簡(jiǎn)單計(jì)算幾何,我的做法是列出所有可能的切法(一共18種),求最優(yōu)值。
閱讀全文
[計(jì)算幾何]pku1408
摘要: 構(gòu)造所有的線段,然后枚舉每對(duì)水平-豎直線段,求交點(diǎn),然后計(jì)算四邊形面積,求最大值。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku3133
摘要: 強(qiáng)烈推薦此題!
狀態(tài)壓縮DP的好題!
分析見內(nèi)
閱讀全文
[計(jì)算幾何]pku3384
摘要: 強(qiáng)烈推薦此題。半平面交算法的一個(gè)應(yīng)用。
具體做法是,把多邊形的每條邊向內(nèi)平移r單位長(zhǎng)度,用這些線段所在直線和原多邊形作半平面交,得到的區(qū)域就是半徑為r的圓放入多邊形的可行域。可以證明這個(gè)區(qū)域一定是凸的,或者退化為一條線段,或一個(gè)點(diǎn)。那么,我們就可以在這個(gè)區(qū)域上求最遠(yuǎn)點(diǎn)對(duì)啦。
我的做法是O(n^2)的。應(yīng)該存在O(nlogn)的做法,因?yàn)槎际峭苟噙呅?,每次半平面交只有最多兩個(gè)交點(diǎn),可二分,而最后的求最遠(yuǎn)點(diǎn)對(duì)可以旋轉(zhuǎn)卡殼。比賽的時(shí)候時(shí)間少,就寫了個(gè)暴力O(n^2)的。
閱讀全文
[計(jì)算幾何]pku1410
摘要: 基本幾何題,判斷線段是否與矩形相交。轉(zhuǎn)化為線段在矩形內(nèi)或線段與四條邊相交。
唯一要注意的是題目中關(guān)于左上角和右下角的定義。
閱讀全文
[計(jì)算幾何]pku1319
摘要: 這個(gè)題需要分情況討論。如果是grid,就能直接算,如果是skew,就一層層往上模擬著堆。最后取最大值。
閱讀全文
[計(jì)算幾何]兩圓求交點(diǎn)
摘要: mmd 和 cz 的智慧結(jié)晶。某次比賽的時(shí)候?qū)懙摹?
閱讀全文
太難過了
摘要: 這是胡說八道
閱讀全文
[計(jì)算幾何]pku1586
摘要: 超級(jí)惡心的精度題。注意讀清題意,然后直接做就行了。
閱讀全文
[圖論][zz]給出一個(gè)沒有偶圈的簡(jiǎn)單無(wú)向圖,求兩個(gè)頂點(diǎn)間路徑的數(shù)目
摘要: 給出一個(gè)沒有偶圈的簡(jiǎn)單無(wú)向圖,求兩個(gè)頂點(diǎn)間路徑的數(shù)目
閱讀全文
[計(jì)算幾何]pku2954
摘要: Pick公式的應(yīng)用。先介紹一下Pick公式:
a = e / 2 + i - 1
a為多邊形(頂點(diǎn)都在格點(diǎn)上)面積,e為多邊形邊上的格點(diǎn)數(shù),i為多邊形內(nèi)部的格點(diǎn)數(shù)。
題目給出三點(diǎn)坐標(biāo),邊上的格點(diǎn)數(shù)可用gcd求得,剩下的事就是解方程了。
閱讀全文
唔,我喜歡這首詩(shī)
摘要: 喜歡搞笑的詩(shī)的請(qǐng)進(jìn)
閱讀全文
[計(jì)算幾何]pku1569
摘要: 枚舉三角形,然后判斷是否其余的點(diǎn)都不在形內(nèi),也不在邊上。時(shí)間復(fù)雜度是O(n^4)。
閱讀全文
[計(jì)算幾何]pku3129
摘要: 很簡(jiǎn)單的幾何題。直接硬搞即可。
閱讀全文
[轉(zhuǎn)]WinSock學(xué)習(xí)筆記[2]
摘要: Winsock入門
閱讀全文
[轉(zhuǎn)]WinSock學(xué)習(xí)筆記[1]
摘要: Winsock入門
閱讀全文
[計(jì)算幾何]pku一些關(guān)于多邊形的題目
摘要: 見內(nèi)
閱讀全文
[計(jì)算幾何]pku3130
摘要: 又是一個(gè)求多邊形的核的題。
閱讀全文
I Want A Wife
摘要: :)
閱讀全文
[計(jì)算幾何]pku2079
摘要: 先求凸包,然后再用旋轉(zhuǎn)卡殼方法求解。
具體做法是枚舉三角形的第一個(gè)點(diǎn)i,設(shè)j = i + 1,k = j + 1。然后做以下操作:
1.計(jì)算i,j,k構(gòu)成的三角形面積a1和i,j,k + 1構(gòu)成的三角形面積a2,如果a2 < a1,則進(jìn)行下一步,否則k++,重復(fù)此步。
2.記錄此時(shí)的三角形面積b,如果b < preb(就是上一個(gè)j對(duì)應(yīng)的三角形面積)j++,轉(zhuǎn)第一步,否則退出。
可以證明這個(gè)算法的復(fù)雜度為O(n2)。具體實(shí)現(xiàn)見代碼。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku1038
摘要: 經(jīng)典的狀態(tài)壓縮DP,《算法藝術(shù)與信息學(xué)競(jìng)賽》的例題。f[i][j]表示前i行,最后兩行狀態(tài)為二進(jìn)制數(shù)j,嵌入的最多芯片數(shù)。第i行到第i+1行用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。
由于第i+1行只和第i行有關(guān),故可以用滾動(dòng)數(shù)組優(yōu)化。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku3375
摘要: A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
有很多細(xì)節(jié)不好考慮,應(yīng)該是我的水平原因。最后我向updog要了數(shù)據(jù)才過的。而且代碼寫的不好。將就看一下吧。
閱讀全文
[計(jì)算幾何]pku1494
摘要: 其實(shí)是初等幾何題。在紙上畫一下就出來了。
閱讀全文
[計(jì)算幾何]pku1473
摘要: 很簡(jiǎn)單的題。直接按照題意模擬即可。
閱讀全文
無(wú)敵詭異的姓名測(cè)試
摘要: 對(duì)搞笑的事情感興趣的請(qǐng)進(jìn)
閱讀全文
[計(jì)算幾何]pku1039
摘要: 具體算法在《算法藝術(shù)與信息學(xué)競(jìng)賽》里有講。
閱讀全文
[計(jì)算幾何]pku1133
摘要: 這個(gè)題目我用的是枚舉。具體做法是,對(duì)于每個(gè)星座,把它的第1個(gè)點(diǎn)放在星圖的第i個(gè)點(diǎn)上,第2個(gè)點(diǎn)放在星圖的第j個(gè)點(diǎn)上(i != j),保持形狀不變,移動(dòng)這個(gè)星座中的其他點(diǎn),看看這些點(diǎn)是否都和星圖中的點(diǎn)重合。若滿足條件,則找到一個(gè)匹配。如此得到星座c對(duì)星圖的匹配數(shù)a。再得到星座c對(duì)它本身的匹配數(shù)b。那么星座c的出現(xiàn)次數(shù)就是 a / b。對(duì)于只有一個(gè)星星的星座,要特殊考慮一下。至于找出最亮星座,方法很簡(jiǎn)單:每次記錄亮度值,發(fā)現(xiàn)更亮的就更新解。
p.s. 我一開始是用STL的complex做的,超時(shí)。后來改成向量做了。
閱讀全文
[計(jì)算幾何]pku1092
摘要: 題目要求統(tǒng)計(jì)一個(gè)平面圖中所有邊數(shù)為k的面的個(gè)數(shù)。應(yīng)該是個(gè)經(jīng)典問題。說說我的算法吧。
枚舉每條邊,做以下的基本步驟。
基本步驟:以這條邊作起始邊,不斷地找下一條“最左轉(zhuǎn)”的邊,并且標(biāo)記每個(gè)點(diǎn)的訪問次數(shù),直到某個(gè)點(diǎn)第3次被訪問為止。
經(jīng)過這個(gè)步驟之后,得到一個(gè)頂點(diǎn)序列。容易知道,當(dāng)且僅當(dāng)這個(gè)頂點(diǎn)序列是2-重復(fù)(就是形如12341234這樣),并且是逆時(shí)針旋轉(zhuǎn)的,那么就是一個(gè)面。
接下去我們就把所有找到的邊數(shù)為k面進(jìn)行hash去重,就得到答案啦。
貌似我想的這個(gè)算法不夠好,如果有更好的算法,歡迎和我討論。
閱讀全文
友情鏈接邀請(qǐng)
[計(jì)算幾何]pku1471
摘要: 這題勉強(qiáng)算幾何吧。我寫了個(gè)超級(jí)慢的枚舉。
閱讀全文
[計(jì)算幾何]pku1434
摘要: 簡(jiǎn)單幾何題,但是容易WA。做法是二分水面高度,然后看看這個(gè)高度對(duì)應(yīng)多少水。
閱讀全文
到武漢啦!
摘要: 對(duì)我的悲慘人生感興趣的請(qǐng)進(jìn)
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku1170
摘要: 呼~今天去學(xué)校啦!早上7點(diǎn)起床寫題,挑了個(gè)簡(jiǎn)單題寫 ^_^
這個(gè)是IOI95的DP題。用一個(gè)b位的6進(jìn)制數(shù)i表示狀態(tài)。這個(gè)6進(jìn)制數(shù)的每一位分別表示相應(yīng)物品的數(shù)量。f[i]表示狀態(tài)i下的最小花費(fèi)。同樣也可以用6進(jìn)制數(shù)j表示優(yōu)惠。那么,f[i]就能轉(zhuǎn)移到f[i - j],如果優(yōu)惠j可用的話。代價(jià)是使用優(yōu)惠j時(shí)減少的花費(fèi)。最后的答案就是min(f[i]),0 <= i <= start(start是初始狀態(tài))。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku1160
摘要: 先預(yù)處理,把第i個(gè)村子到第j個(gè)村子中,建一個(gè)郵局的最小代價(jià)算出來,存在min_cost[i][j]里。
接下來就可以DP。設(shè)f[i][j]為前i個(gè)郵局,建在前j個(gè)村子的最小代價(jià)。那么f[i][j]可以轉(zhuǎn)移到f[i + 1][j + k],(1 <= k 且 j + k <= n),代價(jià)是min_cost[j + 1][j + k]。
閱讀全文
[圖論]pku1125
摘要: 簡(jiǎn)單題。很早以前做的。貼一下凌亂的代碼。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku1088
摘要: 簡(jiǎn)單的記憶化搜索。很早以前做的,代碼風(fēng)格很亂。將就一下啦。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku1737
摘要: 樓爺?shù)念}。遞推。f[n]表示n個(gè)結(jié)點(diǎn)的連通圖個(gè)數(shù),則有遞推公式:
void calc(int n)
{
f[n] = 0;
for (int i = 1; i < n; i++)
f[n] += f[i] * f[n - i] * (pow(i) - 1) * C(n - 2, i - 1);
//pow(x) == 2^x
}
因?yàn)閿?shù)據(jù)較多,所以預(yù)先算出f[1] -- f[50],再輸出。要用高精度。我用了標(biāo)程。
閱讀全文
[動(dòng)態(tài)規(guī)劃]pku1946
摘要: 首先明確一點(diǎn):最優(yōu)解必為奶牛1..n-1輪流領(lǐng)跑,奶牛n撞線。且跑了x圈后,未領(lǐng)跑過的奶牛都耗費(fèi)了x的體力。
設(shè)f[i][j][k]表示前i-1頭奶牛已領(lǐng)跑,現(xiàn)在由第i頭奶牛領(lǐng)跑,一共跑了j圈,奶牛i耗費(fèi)了k的體力。
則f[i][j][k]可以轉(zhuǎn)移到f[i][j + p][k + p^2](耗費(fèi)1分鐘,奶牛i以p圈/分鐘的速度繼續(xù)領(lǐng)跑),也可轉(zhuǎn)移到f[i + 1][j][j](換成奶牛i + 1領(lǐng)跑,不耗費(fèi)時(shí)間)。
時(shí)間復(fù)雜度為O(nde^2.5)。
閱讀全文
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
国产麻豆午夜三级精品 |
亚洲图片欧美一区 |
亚洲综合欧美 |
亚洲欧美不卡 |
亚洲男人第一网站 |
欧美中文字幕第一页 |
久久久久亚洲综合 |
欧美成人精品一区二区 |
亚洲电影免费在线观看 |
亚洲丰满少妇videoshd |
亚洲高清视频一区 |
亚洲婷婷在线 |
久久女同精品一区二区 |
欧美激情四色 |
国产欧美精品日韩精品 |
伊人精品在线 |
亚洲自拍偷拍色片视频 |
老司机成人网 |
一道本一区二区 |
久久久青草青青国产亚洲免观 |
美女国产一区 |
国产欧美日韩综合 |
亚洲精品一区二区三区四区高清 |
亚洲免费人成在线视频观看 |
久久视频精品在线 |
一本色道久久综合 |
久久尤物电影视频在线观看 |
欧美色偷偷大香 |
亚洲欧洲日本专区 |
久久久99国产精品免费 |
日韩一区二区精品视频 |
久久精品观看 |
国产精品国产三级国产aⅴ9色 |
精品999在线观看 |
亚洲一区二区动漫 |
欧美大片一区 |
欧美中文字幕在线 |
国产精品久久久久久久久久直播 |
亚洲品质自拍 |
久久亚洲免费 |
亚洲自拍偷拍网址 |
欧美激情一区二区久久久 |
国产深夜精品 |
亚洲午夜精品一区二区 |
欧美黑人在线播放 |
久久精品99国产精品日本 |
国产精品第2页 |
99国产精品国产精品久久
|
销魂美女一区二区三区视频在线 |
欧美成人一区二区在线 |
国产一区二区三区久久悠悠色av
|
欧美福利一区 |
久久精品72免费观看 |
国产精品网站一区 |
亚洲手机成人高清视频 |
亚洲美女在线观看 |
欧美日韩视频第一区 |
亚洲精品一级 |
亚洲靠逼com |
欧美日韩美女在线 |
亚洲天堂成人在线观看 |
99一区二区 |
国产精品扒开腿爽爽爽视频 |
一区二区日韩 |
亚洲午夜在线观看视频在线 |
国产精品久久夜 |
久久都是精品 |
久久久精彩视频 |
1024国产精品 |
亚洲经典在线看 |
欧美日韩亚洲高清 |
香蕉免费一区二区三区在线观看 |
亚洲深夜av |
国内精品国产成人 |
麻豆久久久9性大片 |
久久综合免费视频影院 |
亚洲精品国产精品久久清纯直播 |
亚洲福利在线观看 |
欧美丝袜一区二区三区 |
午夜精品美女久久久久av福利 |
亚洲一区二区在线免费观看视频
|
国产一区二区你懂的 |
久久人人97超碰国产公开结果 |
久久久久高清 |
9人人澡人人爽人人精品 |
一区二区三区日韩精品视频 |
国产美女精品视频 |
亚洲国产成人av |
国产精品盗摄久久久 |
久久久久久9 |
欧美美女福利视频 |
久久9热精品视频 |
欧美久久一级 |
一本色道久久99精品综合 |
日韩视频中文字幕 |
国产精品久久久久国产a级 |
久久精品一二三 |
欧美激情按摩 |
久久国产日韩欧美 |
欧美激情91 |
久久久精品五月天 |
欧美精品在线免费 |
久久久水蜜桃 |
欧美色网在线 |
欧美成人伊人久久综合网 |
欧美日韩亚洲成人 |
牛牛精品成人免费视频 |
国产精品黄色 |
亚洲精品激情 |
有码中文亚洲精品 |
午夜激情亚洲 |
亚洲激情欧美 |
亚洲免费婷婷 |
亚洲欧美日韩国产综合在线 |
亚洲国产婷婷 |
午夜欧美电影在线观看 |
中国成人黄色视屏 |
六月婷婷一区 |
老鸭窝毛片一区二区三区 |
国产精品久久夜 |
日韩一级大片 |
日韩午夜免费 |
欧美一区在线看 |
欧美一级理论性理论a |
欧美va天堂在线 |
欧美福利一区二区三区 |
国产一区二区三区网站 |
亚洲在线视频一区 |
亚洲欧美另类在线观看 |
欧美三日本三级三级在线播放 |
久久蜜桃香蕉精品一区二区三区 |
国产精品爽爽爽 |
一区二区三区高清视频在线观看 |
日韩亚洲精品视频 |
欧美xxx成人 |
亚洲国产91精品在线观看 |
亚洲日本精品国产第一区 |
欧美成人午夜激情视频 |
欧美国产一区二区三区激情无套 |
伊人色综合久久天天五月婷 |
久久久久久尹人网香蕉 |
久久综合久久综合久久综合 |
国语精品一区 |
农村妇女精品 |
亚洲精品国产品国语在线app |
亚洲精品在线一区二区 |
欧美激情一区二区三级高清视频 |
亚洲国产高清在线观看视频 |
日韩视频一区二区三区 |
欧美日本免费 |
亚洲小说区图片区 |
久久精品99国产精品酒店日本 |
国产午夜亚洲精品理论片色戒 |
欧美一区二区三区在线观看 |
欧美成人午夜激情 |
亚洲直播在线一区 |
亚洲欧美日韩天堂 |
久久岛国电影 |
欧美成人激情视频 |
日韩视频在线观看一区二区 |
欧美日韩国产一级片 |
亚洲午夜精品一区二区三区他趣 |
先锋影音久久 |
在线观看中文字幕不卡 |
欧美高潮视频 |
亚洲一二三级电影 |
久久天堂国产精品 |
一区二区免费在线播放 |
国产精品一区视频 |
欧美成ee人免费视频 |
亚洲一二三区在线 |
欧美成人一区二区在线 |
亚洲私人影院 |
原创国产精品91 |
欧美午夜电影完整版 |
久久精品在线播放 |
一区二区三区波多野结衣在线观看 |
久久久www |
亚洲一区观看 |
亚洲人精品午夜 |
国产视频久久久久 |
欧美色播在线播放 |
欧美+亚洲+精品+三区 |
亚洲一区二区三区精品在线观看
|
av成人免费在线观看 |
久久精品国产综合精品 |
日韩亚洲一区二区 |
在线观看久久av |
国产精品免费观看视频 |
欧美黑人在线观看 |
久久婷婷久久 |
午夜精品久久久久久久男人的天堂 |
欧美风情在线观看 |
久久亚洲一区 |
久久成人亚洲 |
欧美一区观看 |
亚洲一区二区三区免费观看 |
亚洲精品视频在线 |
激情视频一区二区三区 |
欧美日韩成人在线播放 |