查看: 639|回復: 9

[其他] [編輯][高一排名賽-2015] 賽前測試題解

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2015-5-17 19:30:33 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 jd3 於 2015-5-20 13:06 編輯

    前情提要

    隨著賽前測試開放
    編輯完成前先發了
    (這兩天應該會趕完)重整看新內容時請清除chrome的快取


    這回賽前測試有三題每題都有部分給分
    正式比賽也會有部分給分
    儘管撈分數吧~ XD


    第1題為基本題
    熟悉judge基本操作用的

    第2題是互動題
    因為正式比賽中也有互動題
    想拿好成績要先弄懂喔~OwO
    (好像有人偷偷摻了奇怪的時間限制進去)

    第3題是「時間複雜度」題
    一些題目中需要更快的做法才能拿到全部的分數
    大多數時候「快」指的就是比較低的時間複雜度



    Judge的使用
    各位可對這個系統很陌生
    首先登入後左邊有一排標籤
    內容大概就字面上的意思

    對於每個題目
    先到題敘述下載檔案(如果沒裝PDF檢視器,可以用網頁的瀏覽器開)
    寫完到評測頁面選擇你的程式碼檔案上傳
    之後judge會告訴你結果
    不需要一直F5也會顯示
    詳細資料中可以看每一筆測資的結果
    點開子問題可以看到是為什麼沒拿到分 ( 如果是答案錯誤不會告訴你錯了什麼 )
    右側的下載可以載自己的CODE (應該沒必要吧, 除非你手殘刪了)

    最後得分是以所有上傳中最高分的


    請不要使用system("pause");
    你會開心地得到TLE
    輸出解答後請確定程式能正常結束



    第一題 : [ 畢氏定理 ] [ 迴圈 ] [ 浮點數 ]
    嘛~這和距離平方成反比是從萬有引力獲得靈感的
    總之就是先算出距離
    距離 R^2 = (H^2 + △X^2 + △Y^2)
    溫度 D = E/(R^2)
    也就是 溫度 D=(H^2 + △X^2 + △Y^2)


    所以我們發現根本不需要開根號什麼的 >w<

    然後開開心心的
    對每個點加總被每個暖氣加熱的量
    迴圈掃過去找到全部最低的就行了

    這題很好心的就算你真的開了個2維陣列應該還是能過關
    因為我測資產不出太大的拉QAQ





    第二題[ 互動題 ] [ counting ]
    題目有點長
    耐心看完其實沒有很難
    麻煩的是互動題到底是三小

    下載給定的code之後
    註解前有一串奇怪的程式碼
    不要動它

    那是可以幫助你debug的東西

    需要小心的是
    記得引入標頭檔 ( iostream也是 )
    還有千萬不要把include寫在前面那段裡面
    最安全的做法就是都寫在註解以下


    另外

    你不需要也不應該再寫一個main函式
    只要完成指定的函式內容就行了

    嗯...希望你知道函式 ( Function ) 是什麼 >w<

    進入題目部分
    init 函式裡傳入的工作表看起來很詭異
    型態是 const char*總之就是個字元陣列
    如果直接宣告一個 const char* 設成str
    會發現任何修改內容都會造成編譯錯誤

    所以我們有兩種做法


    第一種想法是:「作者應該沒有吃飽太閒去改它吧」
    直接把 const char* 強制轉型成轉成 char*
    要是作者看到我這樣寫而把它改了不要打我>w<

    此作法已失效


    第二種比較中規中矩
    把整個 array 複製出來再實作

    題目內容就...不用多說了吧
    如果沒有通過第2,3筆測資請點開來看看
    上面可能寫著「超過時間限制」
    沒錯!你的做法太慢了!

    如果不會或不想學時間複雜度的話就精神感受一下速度差異吧
    關於時間複雜度請見篇末

    Change是O(1)毫無疑問
    Ask時如果迴圈掃過去是O(N)  (( N為字串長度
    整體為O(N)

    因為char只有0~255
    所以可以輕鬆做個記數
    開個記數用的 array, 大小256就很夠用了 (記得初始化成0)
    Init時先掃過str一次,紀錄每個字出現幾次
    每次Change時把舊的數量--,新的數量++
    Change依然O(1)
    return指定字元的數量只要O(1)





    第三題[ 時間複雜度 ]
    因為不想太快講出解法所以中括號先放個時間複雜度

    題目敘述中
    前綴和後綴的定義翻成白話文就是
    前綴第 i 項:從前面加總到第 i 個
    後綴第 i 項:從後面加總到倒數第 i 個

    Q: 有沒有 某個前綴+某個後綴=T


    先講Input吧
    EOF是三小?
    所有檔案結尾都有個表示「人家只有長到這裡啦><」的符號
    那個符號就叫做EOF (End Of File)
    judge在輸入的時候會餵一個Input檔案給你的程式
    所以最後會跟著一個EOF符號
    那我要怎麼判斷EOF符號呢?

    cin本身遇到 EOF 會return特殊的東西放在迴圈的條件裡就會結束
    所以可以寫
    [C++] 純文本查看 復制代碼
            int N;
            while(cin >> N)
            {
                    // ...
            }
            

    其中cin>>N改成cin>>A>>B>>C
    這樣連用也是可以的
    而輸入A,B,C遇到任一個為EOF就會直接return

    這樣就是輸入N後執行迴圈內容
    如果輸入了EOF就離開迴圈

    如果你用scanf
    scanf本身遇到EOF會return EOF
    所以可以這樣寫
    [C++] 純文本查看 復制代碼
    int N;
    while(scanf("%d",&N) != EOF)
    {
            // ...
    }
    


    EOF有很高的機會是-1
    通常都是負數
    所以有另一個比較不安全的寫法
    [C++] 純文本查看 復制代碼
    int N;
    while(~scanf("%d",&N))
    {
            // ...
    }

    本次比賽應該可以用
    但還是建議學第一個做法

    那要怎麼Debug呢?

    在 Windows 裡按 Ctrl+Z 就能輸入EOF
    如果不行的話...試試Ctrl+D (好像是某企鵝作業系統的設定?)


    暴力法
    迴圈掃啊掃~
    一個枚舉前綴、一個算出前綴;一個枚舉後綴、一個算出後綴。
    4個for輕鬆搞定~
    對於一次詢問的時間複雜度:
         枚舉 O( N^2 )     x     加總 O(N)
    =  O(N^3)

    乘上詢問次數整個複雜度是
    O(N^3 * Q)

    輕鬆得到TLE (Time Limit Exceeeeeeeeeeeeeeeeeeeeeed)


    預處理前綴後綴:
    先把前綴和後綴算出來就不用每次詢問都要加總了~
    預處理是O(N)
    枚舉還是N^2

    算出某個前綴(後綴)的時間變成O(1)

    總複雜度 O(N) + O(N^2*Q)    =     O(N^2 * Q)

    恭喜通過小測資~



    預處理總和:

    看到那些Input的範圍了嗎?
    來把前面的作法算一下看看
    N^2 * Q   =   10^14
    好可怕的數字

    如果我們預處理所有可能出現的前後綴之和
    那麼就會變成:
        預處理前後綴     O(N^2)
        初始化總和buff   O(T)
        預處理總和         O(N^2)
        詢問一次            O(1)
        全部詢問            O(Q)
    再算一次看看

    因為時間複雜度常數可忽略
    所以 O(N^2 + T +  N^2 + Q) = O(N^2 + Q)
    所以最後是 O(N^2)
    估計一下
    N^2   =   10^10
    這好多了

    所以預處理完所有可能狀態後
    依然TLE了~


    二分搜尋:

    仔細觀察會發現奇怪的東西
    ...
    ...
    ...
    為什麼Q要比N小
    當然一切都是為了讓你TLE
    裡面一定有玄機


    因為Q比較小
    如果能把預處理的時間分到某種跟Q成正比的操作就最好了
    前後綴的預處理當然還是少不了


    我們希望不用預處理所有可能 ( 討厭的 N^2
    在每次查詢的時候又盡可能的快 ( 不然乘上Q就太大

    今天已經預處理前後綴
    且知道前後綴都是遞增

    知道2分搜的人或許能想的到
    不需要2層for枚舉
    枚舉前綴 Si
    對於每個Si , 都到後綴裡2分搜 T-Si
    找得到就成功了!
    而2分搜的複雜度 O ( log(N) )
    ( log 以2為底 )
    所以整體變 O(N + N*log(N) ) = O( N*log(N) )

    估算一下
    N * log(N) * Q   =   5*10^9

    看起來似乎砍半了?
    但就這樣傳上去會發現依然TLE甚至執行時間更長了

    問題就出在於
    二分搜常數太大了


    沒關係
    以下有更好的方法



    單調優化:
    說真的這名詞滿有深度
    但是在這題裡作法很簡單

    所謂的單調就是...ㄜ...很單調(?
    簡單來說就是很有規律
    例如說遞增遞減
    還記得剛剛說前後綴怎麼了嗎?

    我們枚舉前綴 (( 巴拉巴拉的for迴全掃過去
    看到後綴是遞增的很開心的2分搜
    或是很暴力的for又巴拉巴拉的掃了一次

    OK停在這裡
    我們少了個東西
    前綴也是遞增的
    前綴的單調性我們沒有用到啊

    再仔細想想
    2分搜(或暴力搜)的時候,因為前綴遞增,所以搜到的後綴和遞減
    所以我們蒐的答案就是從右邊往左邊跑

    經過一翻觀察
    我們完全可以排除重複搜尋到的部分(也就是不可能出現答案的部分)
    原本可能這樣寫
    [C++] 純文本查看 復制代碼
    for(int i = 0 ; i < n ; i++)
                    if(binary_search(sp, sp+n, T-s[ i ]))
                            //...


    或是這樣

    [C++] 純文本查看 復制代碼
            for(int i = 0 ; i < n ; i++)
                    for(int j = 0 ; j < n ; j++)
                            if(s[ i ]+sp[j] == T)
                                    //...


    改造一下變類似這樣

    [C++] 純文本查看 復制代碼
    int j = n;
            for(int i = 0 ; i < n ; i++)
            {
                    while(s[ i ] + sp[j] < T)
                            j--;
                    if(s[ i ]+sp[j] == T)
                            //...
            }



    這樣看起來還是2個迴圈
    有差嗎?

    事實上,因為第2層迴圈執行的總次數最多就是N次 (因為 j 只會往左移動)
    所以詢問的整體複雜度是O ( N*Q )

    再估算一下
    N * Q  =  10^9

    而且從頭到尾都只有簡單的迴圈掃過來掃過去所以常數很小

    終於 AC 囉~



    CODE:
    還是希望各位可以自己寫
    這裡的code參考就好
    賽前測試參考解答.rar (1.71 KB, 下載次數: 4)
    <這是個人簽名欄位>
    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-6-17 11:50
  • 簽到天數: 177 天

    [LV.7]常住居民III

    15

    主題

    315

    帖子

    1437

    積分

    金牌會員

    Rank: 6Rank: 6

    積分
    1437

    新手達陣台南一中資訊社

    發表於 2015-5-20 20:59:31 | 顯示全部樓層
    本帖最後由 visitorIKC 於 2015-5-20 21:48 編輯

    第三題另解

    直接hash所有後綴
    就可以O(1) 得知某個後綴有無出現

    對每個Query
    枚舉前綴
    直接查詢後綴存不存在
    複雜度 O(TcNQ)

    實作直接用lookup Table
    MLE - 10/100

    若改用std::map(複雜度退化)
    TLE - 10/100

    用Array,再快樂的作一些優化
    AC - 100/100

    成功AC ^_^
    到目前為止還沒有被Challenge掉 : )
    XXXXXXD




    點評

    TLE Likely  發表於 2015-5-29 16:56
    有try過unordered_map嗎?  發表於 2015-5-29 11:53
    jd3
    快樂優化也說明得太簡短了吧OAO  發表於 2015-5-21 22:14
    目標:Taiwan Oranges-Integraled 2016 (TOI'16)台灣積分橘子。
    回復 支持 反對

    使用道具 檢舉

  • TA的每日心情
    開心
    2014-9-28 12:10
  • 簽到天數: 21 天

    [LV.4]偶爾看看III

    34

    主題

    181

    帖子

    776

    積分

    高級會員

    Rank: 4

    積分
    776

    程式設計達人 - 2014新手達陣

    發表於 2015-5-29 10:40:48 | 顯示全部樓層
    [C++] 純文本查看 復制代碼
    int j = n;
            for(int i = 0 ; i < n ; i++)
            {
                    while(s[ i ] + sp[j] < T)
                            j--;
                    if(s[ i ]+sp[j] == T)
                            //...
            }

    這有點問題!
    這樣做的話,後綴得由大到小排列才行吧?

    點評

    話說有點好奇~~你有沒有報名高一排名賽??(純粹好奇~~  發表於 2015-5-29 21:21
    沒問題的~~jd3或許並沒有說清楚,但是預處理suffix完之後確實是單調排列的~~  發表於 2015-5-29 21:20
    林宇翔
    回復 支持 反對

    使用道具 檢舉

  • TA的每日心情
    開心
    2014-9-28 12:10
  • 簽到天數: 21 天

    [LV.4]偶爾看看III

    34

    主題

    181

    帖子

    776

    積分

    高級會員

    Rank: 4

    積分
    776

    程式設計達人 - 2014新手達陣

    發表於 2015-5-29 22:00:19 | 顯示全部樓層
    我有報阿!

    點評

    以後直接用點評就好~~  發表於 2015-5-29 22:25
    林宇翔
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表