NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » phat 的個人資料 » 顯示文章
 主題

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

主題 - phat

頁: [1]
1
NPSC2003高中組決賽 / NPSC 2003 高中組 決賽 G.考古問題
« 於: 七月 15, 2011, 06:08:46 pm »
題目是這樣的:

給兩個序列,輸出最長的一組遞減的LIS,保證同一個序列每個數字只出現一遍,N<=512


我們可以把他想成一張DAG,每個數字都是一個節點。

然後A->B有邊的條件:(1)A在序列1和序列2都排在B之前 (2)A比B大。

建完之後求DAG最長路,總複雜度O(N^2)


話說這題好像還有其他作法...

2
NPSC2010國中組初賽 / NPSC 2010 國中組初賽 pE.傘兵
« 於: 十一月 27, 2010, 05:20:39 pm »
這題可以做N源點的最短路,複雜度是O(RC lg(RC)) (用Dijkstra實作)


可是提供一個純Flood Fill的作法:

先將N個可行的降落位置依照風險由小排到大,將最小的加入一個Queue,

以後每次檢查如果Queue的front的風險跟未加入的降落位置中風險最小者一樣,

就將該降落位置加入Queue,等到所有點都遍歷過就結束。


一個小細節是如果這個降落位置還沒加入Queue就已經可以從其他位置到達,

要直接忽略此降落位置。


3
轉化後就是求出最大生成樹的最小邊。

需要注意的是 1.要判斷生成樹是否存在 2. N=1要輸出"No way."

代碼: [選擇]
#include <cstdio>
#include <algorithm>
#define MAX 100100

struct edge {
    int i,j;
    double cost;
    bool operator<(const edge&b) const { return cost > b.cost; }
}e[MAX];

int T, N, M, added, ee;
int r[MAX];
int find(int a){return a==r[a] ? a : r[a]=find(r[a]);}
double min;

int main() {
    scanf("%d", &T);
    while(T--) {
scanf("%d%d", &N, &M);
ee = 0;
for(int i=0; i<=N; i++)r[i]=i;
for(int i=0; i<M; i++) {
scanf("%d%d%lf", &e[i].i, &e[i].j, &e[i].cost);
}
std::sort(e, e+M);
for(int i=0; i<M; i++) {
int a=e[i].i, b=e[i].j;
int ra = find(a), rb = find(b);
if(ra != rb) {
min = e[i].cost;
r[ra] = rb;
ee++;
}
}
if(N == 1) puts("No way.");
else if(ee == N-1)
printf("%.4f\n", min);
else puts("The empire of Arcturus is ending.");
}
}


4
NPSC2010高中組初賽 / NPSC 2010 高中組 初賽 B.卡卡跑丁車
« 於: 十一月 27, 2010, 05:04:13 pm »
簡單的說就是動態規劃。

可以用DP[ i ][j][k]表示走完第i條道路還剩下j個加速器、這次甩尾累積了k次的最小耗時。


有一點要注意的是需要開到64位元整數才不會溢位。



我寫得很亂,沒什麼參考價值所以就不貼code了。




頁: [1]