NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

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

顯示文章

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

文章 - phat

頁: [1]
1
NPSC2011高中組初賽 / Re: pD. 巨集危機
« 於: 十一月 27, 2011, 07:13:30 am »
因為這題範圍很小

其實可以2^(括號對數)次方枚舉留下哪些括號

再用x = a + b * c + d    random選幾組a, b, c, d檢查是否和原本算式一樣

這樣有個保證正確的2^N * N的做法。

另外. 出題者表示可以做到O(N)

2
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)


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

3
其實這題是可以作到O(N^2)的。


要先有一個概念:如果最後有合奏的學姐序列依照合奏時間用S1~Sk表示。

那麼對任意i,一定有Si的編號 < S(i+1)的編號。

也就是不會有a區間比b區間前面 但是a學姐比b學姐晚合奏完的情況。

 

怎麼證明呢?假設最佳序列是S'1~S'k而且其中存在一個i,S'i的編號 > S'(i+1)的編號

但經過一點點的小證明可以發現,把這兩個學姐交換順序也一定存在一個合法的合奏方案。

//因為區間有非嚴格遞增性才會合理。

 

所以我們可以用DP[j]表示做完前i個學姐,取了j個學姐時最右界的位置。

每個轉移O(1),總複雜度O(N^2)


代碼: [選擇]
#include <cstdio>
#define INF 1000100
int dp[1010], N, D, R, P, dm;

inline int fmax(int a, int b) {return a>b?a:b;}

int main() {
while(~scanf("%d", &N) && N) {
for(int i=1; i<=N; i++) dp[i] = INF;
for(int i=0; i<N; i++) {
scanf("%d%d%d", &D, &R, &P);
for(int j=i; j>=0; j--) {
dm = fmax(D, dp[j]+1);
if(dm+P-1 <= R && dp[j+1] > dm+P-1)
dp[j+1] = dm+P-1;
}
}
for(int i=N; i>=0; i--)
if(dp[i] != INF) {
printf("%d\n", i);
break;
}
}
}

4
NPSC2010高中組初賽 / 回覆: NPSC 2010 高中組 初賽 C.
« 於: 一月 03, 2011, 06:07:26 pm »
其实是有一种算法叫做KMP....

可以达到O(n),而且代码超短。


問一下怎麼用KMP做到...

因為之前大家想了好久結果沒想到如何用KMP達到O(n)

5
綜合討論區 / 回覆: 2010NPSC決賽[純粹閒聊]
« 於: 一月 01, 2011, 10:09:08 am »
引用

//講解的大神我猜是蚯蚓>\\\\\\\\\\\\\\\<


你應該記錯了xD(?



引用

就DP吧,大概啦,我也只掃過題目。


對,就狀態壓縮DP,狀態是顏色數^寬 * 高。

不過我在想有沒有數學解,因為這樣DP有很多浪費掉...



6
綜合討論區 / 回覆: 2010NPSC決賽[純粹閒聊]
« 於: 十二月 13, 2010, 12:09:07 am »
不過 . .

sagit老師呢 ?

有人知道嗎 ?

我今天才剛從日本回來, 所以這次決賽我沒有去,
不過我在日本的時候還是有連上來刪廣告....
一般我都是等測資出來之後, 才會開始解題,
只是這樣看來, 今年好像沒有我出場的必要了,
各位同學都太優秀了,
希望以後也可以繼續,
這樣我只要管好這個網站就行了....

還有pG還沒有人PO XDD

不過據說某一個場外隊有寫出來(?)



7
綜合討論區 / 回覆: 2010NPSC決賽[純粹閒聊]
« 於: 十二月 12, 2010, 04:54:40 pm »
(大家都在討論pB OAO  插個題外話(?
然後一堆國中生都有橘色氣球(pG Q
(跑掉

輕鬆洩漏你的身份欸XD



我覺得這裡大部分人不認識我(點頭



啊啦感覺太少內容



是說這樣pE可以出個加強版,問三條LIS xD

應該可以作到N^2 lg N

8
綜合討論區 / 回覆: 2010NPSC決賽[純粹閒聊]
« 於: 十二月 12, 2010, 04:19:51 pm »
(大家都在討論pB OAO  插個題外話(?


國中組似乎還沒出現半篇文也還沒有題目(?


不過從記分板看起來這次國中組應該算是頗難(?



然後一堆國中生都有橘色氣球(pG Q



(跑掉

9
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 F.
« 於: 十二月 11, 2010, 11:44:32 pm »


是說剛才稍微測試一下您的程式碼,

對於以下測試資料:

代碼: [選擇]
1
3 3 9
0 0 2
0 1 3
0 2 2
1 0 3
1 1 1
1 2 3
2 0 3
2 1 2
2 2 2


似乎正確輸出是YES

        x->
2 3 2 y
3 1 3 |
3 2 2 ˇ

(沿著x=0 x=1 y=1炸?)


可是您的程式輸出了NO


還是我有誤解的地方,還請指正...
我也是覺得這樣跟我們這對AC(我們有遞迴可是好像沒報蒐完全...)都是假解...
話說請問大大SCC是啥?


樓上不覺得PO中文比較方便嗎OAO

可以參考DJWS的http://www.csie.ntnu.edu.tw/~u91029/ConnectedComponent.html#a3



簡單的說一下2-SAT的SCC算法正確性好了。

上文有提到,若A狀態必定導致B狀態的發生,那我們就把(A狀態)到(B狀態)建一條有向邊。

而且這個關係是可遞移的,也就是如果(A狀態)連到(B狀態),(B狀態)連到(C狀態),

那麼A狀態的發生將會導致C狀態的發生。


所以可以推之,如果(A狀態)到最後會導致(反A狀態)的發生;(反A狀態)最後會導致(A狀態)的發生,

那不論何者都矛盾,所以此問題一定無解。


SC,強連通性質講的是這個子圖內任一點對(A, B)皆存在A到B的路徑 and B到A的路徑。


所以如果(A狀態)會跟(反A狀態)在同一個SCC之內,那麼一定會產生矛盾。



以上是粗略的說明,詳細請參考以下投影片

http://forum.byr.edu.cn/wForum/boardcon.php?bid=212&id=15887&ftype=3&ap=369



至於找出一組解又是另一回事了...

10
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 F.
« 於: 十二月 11, 2010, 10:47:57 pm »

代碼: [選擇]
#include <iostream>
#include <queue>

using namespace std;

struct node{
    int x,y;
}pla;

queue<node> q;

bool row[102],col[102],ca[102][102];
int s[102][102];

int main(){
    int p,h,w,k;
    int yi,xi,ci;
    bool tf;
    scanf("%d",&p);
    while(p--)
    {
        scanf("%d %d %d",&h,&w,&k);
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
        memset(ca,0,sizeof(ca));
        memset(s,-1,sizeof(s));
        tf=true;
        for(int i=0;i<k;i++)
        {
            scanf("%d %d %d",&yi,&xi,&ci);
            if(ci==0)row[yi]=col[xi]=true;
            else if(ci==1)
            {
                s[yi][xi]=2;
                pla.y=yi;
                pla.x=xi;
                q.push(pla);
            }
            else if(ci==2)ca[yi][xi]=true;
            else{
                s[yi][xi]=1;
                pla.y=yi;
                pla.x=xi;
                q.push(pla);
            }
        }
        while(!q.empty())
        {
            pla=q.front();
            if(s[pla.y][pla.x]==1)
            {
                if(!row[pla.y])
                {
                    for(int i=0;i<h;i++)
                    {
                        if(s[pla.y][i]>0)s[pla.y][i]--;
                        if(ca[pla.y][i])col[i]=row[pla.y]=true;
                    }
                    row[pla.y]=true;
                }
                else if(!col[pla.x])
                {
                    for(int i=0;i<w;i++)
                    {
                        if(s[i][pla.x]>0)s[i][pla.x]--;     
                        if(ca[i][pla.x])row[i]=col[pla.x]=true;
                    }
                    col[pla.x]=false;
                }
                else
                {
                    puts("NO");
                    tf=false;
                    break;
                }
            }
            else if(s[pla.y][pla.x]==2)
            {
                if(!row[pla.y] && !col[pla.x])
                {
                    for(int i=0;i<h;i++)
                    {
                        if(s[pla.y][i]>0)s[pla.y][i]--;
                        if(ca[pla.y][i])col[i]=row[pla.y]=true;
                    }
                    for(int i=0;i<w;i++)
                    {
                        if(s[i][pla.x]>0)s[i][pla.x]--;
                        if(ca[i][pla.x])row[i]=col[pla.x]=true;
                    }
                    row[pla.y]=col[pla.x]=true;
                }
                else
                {
                    puts("NO");
                    tf=false;
                    break;
                }
            }
            q.pop();
        }
        if(tf)puts("YES");
        while(!q.empty())q.pop();
    }
    return 0;
}


是說剛才稍微測試一下您的程式碼,

對於以下測試資料:

代碼: [選擇]
1
3 3 9
0 0 2
0 1 3
0 2 2
1 0 3
1 1 1
1 2 3
2 0 3
2 1 2
2 2 2


似乎正確輸出是YES

        x->
2 3 2 y
3 1 3 |
3 2 2 ˇ

(沿著x=0 x=1 y=1炸?)


可是您的程式輸出了NO


還是我有誤解的地方,還請指正...

11
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 E.
« 於: 十二月 11, 2010, 08:48:02 pm »
還是很不甘心啦XDD


我寫了一個只要增廣兩次的花費流一直TLE QQ


等有官測來測一下LIS + 一次最短路多快XD


12
NPSC2010高中組決賽 / 回覆: NPSC 2010 高中組 決賽 F.
« 於: 十二月 11, 2010, 07:48:58 pm »
這題其實是典型的2-Satisfaction問題(2-SAT),

這類問題的原型是,


有很多人,每個人都可以選或不選,然後某些人可能存在互斥關係,

也就是假設A, B互斥,那麼選A就不能選B;選B就不能選A。

問有沒有一組合法解 / 請輸出一組合法解。



這個問題的作法可以參考網路上或是大陸的論文:由对称性解2-SAT问题


簡單的來說就是,

如果A, B互斥,那麼(選A)到(不選B)建一條有向邊、(選B)到(不選A)建一條有向邊。

如果p到q建一條邊,表示如果p事件成立那就強迫q事件得成立。

作一次SCC,如果有一個點他的選和不選在同一個元件裡面,這題就無解。


正確性請參考論文或其他網站wwww


這題的建圖是,每行每列都有要炸不炸兩個選項,你可以想成有(H+W)個點的2-SAT問題

0. 醫院(不能炸),那就是該行該列都不能炸。 所以建(選x)到(不選x)、(選y)到(不選y)

1. 堡壘(炸兩下),就是一定要炸。所以建(不選x)到(選x)、(不選y)到(選y)

2. 防空洞(最多一下),就是不能兩個都炸。所以建(選x)到(不選y)、(選y)到(不選x)

3. 軍營(至少一下),就是不能兩個都不炸。所以建(不選x)到(選y)、(不選y)到(選x)


依照以上方法來構圖,接著作一次SCC即可結束


所以這題其實可以出到H, W <= 2,000左右。


這題的測試範圍讓很多爆搜聽說會過(?)


以上。

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


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

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

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

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


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

要直接忽略此降落位置。


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

需要注意的是 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.");
}
}


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

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


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



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




16
NPSC2010高中組初賽 / 回覆: NPSC 2010 高中組 初賽 C.
« 於: 十一月 27, 2010, 04:14:49 pm »
這題平方會過應該是測資太弱...


最佳解是線性,有一隊有寫。


17
引用
第四題一點初步的想法:
可以想像成平面,假如隕石會從天空經過或者撞到大樓,那麼彗星的參數式與方格必定相交。
而這條直線必定與方格的四個邊至少有一個邊相交。
枚舉所有大樓的前後左右界,再做一點處理,可得解。


事實上不用枚舉所有的左右界,可以先把參數式弄出來,

然後帶入所有x=10k求出所有隕石會經過而且是x方向大樓邊界的高度

帶入y=10w同樣求出所有y邊界,

這樣只要作(Sx+Sy)次處理,基本上複雜度不錯。


//不過這題讀入就Sx*Sy了,應該差不了多少xD

18
綜合討論區 / 回覆: 台北市資訊學科能力競賽 結束 !
« 於: 十一月 20, 2010, 03:51:50 pm »
pE是一類很標準的線性規劃題目。

基本上是屬於大學課程的東西,只是一種防破台而已...


如果有想要瞭解該怎麼去解的可以參考大陸的國家集訓隊論文:

李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》


我自己是還沒開始閱讀啦,而且這類問題在高中競賽應該是屬於這次出現以後就再也不會碰到的題目。


===

97北市p1 cookie也是一類求整數解的線性規劃,

是屬於一類NPC問題,但是該題測試資料給定範圍很小所以可以進行枚舉。


===

我覺得此次比較嚴重的問題是測試資料普遍不強,

前四題前兩筆輸入皆為範例測資、像第四題印象中最大一筆才幾百...題目敘述過度膨脹,

第三題輸出答案相差皆很小,似乎是完全亂數產生之測資,而且第三筆似乎官方輸出有誤。

第五題竟然有兩筆標準答案為-1,讓不少puts("-1");者受惠...



頁: [1]