NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2011高中組初賽
 pF. 英雄 Fantasy for you

作者 主題: pF. 英雄 Fantasy for you  (閱讀 7929 次)

no306100

  • 新手
  • *
  • 文章數: 4
    • 檢視個人資料
pF. 英雄 Fantasy for you
« 於: 十一月 28, 2011, 09:40:55 am »

題目說明 :
一個N × N的地圖
給K個傳送門的座標
要從(1,1)的位置走到(N,N)的位置
每次只能往上、下、左、右移動一格
在傳送門的位置可以移動到左上、左下、右上、右下和上、下、左、右
每次移動時間加一
求最少的移動時間

測資範圍:
測資資料組數 T (1 ≤ T ≤ 100)
地圖邊長 N (1 ≤ N ≤ 10000000)
傳送門數量 K (0 ≤ K ≤ 50000)
座標範圍Xi Yi (1 ≤ Xi ≤ N , 1 ≤ Yi ≤ N)

題目解法:
LIS(Longest Increasing Subsequence)
沒有傳送門的時候最短時間走法必定是只往右或往下走
繞路的話會增加時間
加上傳送門之後
用傳送門來減少時間就得往右下走才能少一單位的時間
假設當前位置在(X,Y)而且此點有傳送門
往(X+1,Y+1)走了之後求最短時間就不會在考慮x或y座標小於X或Y的傳送門
所以就變成了求(x,y)的最長嚴格遞增子序列
我是先排序x座標之後再用y座標來求LIS
然後可以用二分搜做到O(KlogK)這樣

還有一個小細節要注意
如果傳送門在x座標或y座標等於N的時候
就只能往右或往下移動
所以可以直接去掉
比賽當時rejudge好像就是這個原因
一開始我是有想到而且也把圖上畫了邊界可是後來就忘了
送出去後傳回yes就沒去想
好像是某隊測出來的樣子
我們那隊還是到了暫停時間才發現rejudge後是WrongAnswer
隊友storynp發現那個問題我才恍然大悟忘記寫
後來AC後罰分就超多的

參考程式 :
代碼: [選擇]
#include <cstdio>
#include <algorithm>

struct Node {int x,y;} node[50000];
int stack[50000],top;
bool cmp(Node i,Node j){
    if (i.x<j.x)
        return true;
    if (i.x>j.x)
        return false;
    return i.y>j.y;
}
int main()
{
    int cases,n,k;
    scanf("%d",&cases);
    while (cases--){
        scanf("%d %d",&n,&k);
        for (int i=0;i<k;i++)
            scanf("%d",&node[i].x);
        for (int i=0;i<k;i++)
            scanf("%d",&node[i].y);
        int kk=0;
        for (int i=0;i<k;i++)
            if (node[i].x!=n&&node[i].y!=n)
                node[kk++]=node[i];
        k=kk;
        if (k==0){
            printf("%d\n",2*n-2);
            continue;
        }
        std::stable_sort(node,node+k,cmp);
        top=1;
        stack[0]=node[0].y;
        for (int i=1;i<k;i++){
            int v=node[i].y;
            if (v>stack[top-1])
                stack[top++]=v;
            else{
                int l=0,r=top,mid;
                while (l<=r){
                    mid=(l+r)/2;
                    if (stack[mid]>v)
                        r=mid-1;
                    else if (stack[mid]<v)
                        l=mid+1;
                    else{
                        l=mid;
                        break;
                    }
                }
                stack[l]=v;
            }
        }
        printf("%d\n",2*n-2-top);
    }
    return 0;
}

« 上次編輯: 十一月 28, 2011, 04:16:11 pm 由 sagit »
記錄

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
Re: pF. 英雄 Fantasy for you
« 回覆 #1 於: 十一月 28, 2011, 09:31:03 pm »

這題時限相當寬鬆,離散化後用BIT維護的笨方法也可以過.......

今年的出題團隊真是超級好心。

期待pB的補完
記錄

no306100

  • 新手
  • *
  • 文章數: 4
    • 檢視個人資料
Re: pF. 英雄 Fantasy for you
« 回覆 #2 於: 十一月 29, 2011, 10:40:18 am »

不知道為什麼今年某些題目很寬鬆..

pD我們這組是寫假解就AC了,我只有判括號左右有沒有乘號

本來有考慮裡面有沒有加號減號之類的,結果想說先丟出去看看就回傳Yes

pE聽說我們學弟那組自己生一筆測資就WA了但是送出去回傳Yes..

pA原本我估直接兩點互對判斷整張圖可能會TLE

又多花了一些時間加上分支度的剪枝,沒想到好像連加都不用就能AC了...

pB真的不會...聽說有AC的code都短短的,有15行的也有40xbytes的..
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
Re: pF. 英雄 Fantasy for you
« 回覆 #3 於: 十一月 29, 2011, 08:14:17 pm »

me & daiyang 對這題表示遺憾 . (我是連思考這題的時間都沒有 ...)

我太久沒co題了 ...  平均一題co超過1小時 ... (好多好多bug一直在修修修)


pA
n=8~~~
一開始沒看到先跳過

不用剪 時間也能壓在時限內 (時間複雜度滿明顯得 ..)


這次初賽真的很好康 ...

A~F  都沒有進階的演算法在裡面 ..

可是決賽 ...

有預感會被慘電 ...
記錄

esrever

  • 新手
  • *
  • 文章數: 2
    • 檢視個人資料
Re: pF. 英雄 Fantasy for you
« 回覆 #4 於: 十一月 29, 2011, 08:16:51 pm »

引用
這題時限相當寬鬆,離散化後用BIT維護的笨方法也可以過.......

這樣做的複雜度錯了嗎?
記錄

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
Re: pF. 英雄 Fantasy for you
« 回覆 #5 於: 十一月 30, 2011, 06:42:25 pm »

引用
這題時限相當寬鬆,離散化後用BIT維護的笨方法也可以過.......

這樣做的複雜度錯了嗎?

當然沒錯,但是常數和編程複雜度大錯特錯XDD
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2011高中組初賽
 pF. 英雄 Fantasy for you