SubaRyaのcode and 廢日常

 [NCPC 初賽 2020心得] FB連結 難得這次我有賽中把題目看完 ============以下題敘============ PA : r=qx+py，給正整數r,p,q，求|x|+|y|最小 (r<pq & r<10^9 assume that 1<p,q<10^9) PB : 奇數魔方陣。給定第一列數字，把整個大小n^2的魔方陣求出。(魔方陣：每行、列、主副對角線個別和相等) (n<=5 & n is odd) PC : 給一棵帶邊權的樹，n個節點，修改q次邊權Wij，求出每次修改後最遠的兩點。(n<=1500 & q<=20 && <=10筆測資 && W<=10000) PD : 有一個以大寫字母組成長度<10^4的字串，以星號(*)結尾。總共有兩次的變動，第一次為「將最後一個字母丟到第一個，重複n-1次」，第二次為「將原字串與n-1個字串以字典序排序」，然後依序取每個字串的最後一個字母。      現在給定一字串為「每個字串的最後一個字母」，請推出原字串為何。 PE : 給定一個大小為n^2陣列L，n<1000，L[i][j]表示i與j相鄰的距離(L[1][2]=1 L[1][3]=2 L[2][3]雖然可以間接走到，但沒有相鄰因此為無限大)，題序為全點對最短情況下modify一邊權後響多少點對被變更(變更使得維持全點對最短)(0<邊權<2^32) PF : 給m,n表示1~m中任意數量數字和=n，有全部列出，無則輸出-1 (m<=n & 8<=n<=30 & 共10筆測資) PG : 給定d[0][0]，用下面圖片那串建一個(N-1)*(M-1)的table，給A,B,L取max(左上d[A][B]與右下d[A+L-1][B+L-1]的矩形範圍內相鄰差) ============今日總過程============ 江文吉 昨天半夜來我家吃宵夜、改Codebook，還有互相打氣(? 隔天10點快半跟原齊、文元會合吃早(午)餐，然後買了電瓶->(茶) 進考場後說甚麼不能動電腦跟鍵盤，欸欸，都已經12:43了，剩17分鐘就要考了，說好的30分鐘測...

來寫個心得～ （不算長文（？而且很流水帳喔>< 2019資奧TOI初選前熱身營隊（？ ==============Day1(1/21)============== 因為是第一天報到，所以試著早起（5 點喔 來到了板中，開始上課時發現我沒吃早餐.....可悲 第一天只教DP但也是顛覆我人生的第 一次聽到如此動人又詳盡的DP，才開 始發現我以前原來跟DP很不熟。 然後很順利的跟坐附近的同學們聊得很來（？ 還有一個保送科大，電m(_ _)m 大部分都寫ZJ 的題目，而且很多是蝸牛老師出的，感到有一種循序漸進～>< 回家坐在椅子上直接睡著，耶～習題沒寫完 ==============進入Day2(1/22)============== 早上四點起床發現沒寫習題，開拼～ 不知不覺5:30了，差一點錯過第一班公車 然後，到了板橋車站附近我居然記得吃早餐ww 小抱怨，快上課了警衛才記得把樓下鐵捲門打開QAQ 第二天教的是簡單的資料結構、前中後序轉換、DFS、BFS，也是邊刷題邊上課 然後神奇的鄰座學長是樹大神，解惑了些許對於樹的疑惑~(聽說高職專學樹(?羨慕) 回家亦然倒頭就睡 ==============差點遲到的Day3(1/23)============== 居然睡過頭了QQ但趕上了第三班6:00的公車，因此來不及用電腦裡的頭貼為昨天要選拔賽的我送上祝福(? 據說這選拔賽的全名是2019新北市國際資訊奧林匹亞研習營初選資格選拔(? 差10分鐘遲到，匆匆忙忙得趕上後聽說今天教圖論&二分 再來驚喜的是親眼遇見大神們陳威翰和蘇柏瑄(架CMS辛苦了><) 題目有5題 PA:單純的stack&queue(100%) PB:題目包裝得很漂亮，拆開來是我曾經精神AC卻沒實做過的LCS(100%) PC:想了想，原本想說跟TIOJ 的Comiket一樣左加1，(右+1)減1 直接掃過去，但紙張上畫一畫發現會爛掉(? 所以突發奇想想起今天教了binary search，所以我就開了pair反過來二分搜，結過記憶體爛掉(27%) PD:給一張格子圖，求某位置通過一些點到達目的的最短總長。(0%) PE:並查集(精神100%) 過程: 前14分鐘寫完PA，由於精神不濟刻出來的code，...

 早上實作......嘛~  分四題:       PA:(100%) 單純的運算水題(分次利息-原本利息)       PB:(100%) 陣列轉個方向印出，空的印'*'即可       PC:(0%)  二維平面只有第0層安全，一個格子等價於一個房間，頂多容納1人。從第一層以上有倆倆之間的房間(不一定相鄰)可以互相穿梭，(以上佔分80%)，第0層也可以互相穿梭，佔分20%，請問最多有幾個人可以逃脫?嘛......圖論題，我想過爆搜(不大優)、DFS......之類的，but in vain. I have no idea!!!       PD:(40%) 將輸入sort後再從原字串的 '$'開始向sort的字串倒推源字串(這是一 個一個將最尾端的字元往排頭放，接著將全部的過程一字典續排序後再挑最後一欄的回朔結論)但我這個作法只拿了40%(?       Total:240/400  然後下午的筆試40題(20單選20填空)，除了考的資訊史之外，整體上沒什麼太大的問題。  接著，等成績打FGO、LoveLive。好開心又好興奮  拿了佳作......  嘛......明年再加油!!!(我還是好垃圾......) PC: https://drive.google.com/file/d/1SrgWh6eaDuxsv9b2KqNtjk0FgWqlA5kT/view PD:  https://drive.google.com/file/d/1u61Je3Ms25ZItPJlysk2uXNz4mLKPwsJ/view

  (300題45分鐘)   這次跟去年一樣在華僑高中，聽英選中100題，看英選中100題，看中選英100題，但是小抱怨一下，聽應選中時41~50、70~80、90~100有些題號沒唸，有些跳題，甚至不唸題......嘛......這樣就算了，但當我聽英選中回過神來時，我居然畫到看英選中的卡了!!!而且已經唸到第70多題了，算了，至少在唸到100題之前順利的copy到了正確的答案卡上，並且充分的利用25分鐘(實際上是18分鐘)寫完了另外200題，檢查了2次。Fortunately,最後還是有用光碟機重放沒播到的部分，感覺還算可以。   其實去年我也有比，但第一次沒跟上時間的腳步，因此到最後還有30多題沒寫完就交卷了，(實在不堪設想啊啊啊啊)

  人生一敗塗地，我直到考試前兩天才把所有課、作業、小考、線上期末考全部掃過(嘛......13周的課程濃縮成兩天還挺刺激的~XD)，但大部分時間都是花在看昕威電神介紹給我的新頁出版的微積分書。   這兩天學會了如何在分部積分下用表列法、三角反三角代換法、瑕積分、基礎的Shell & Disk method、重積分。   人生充實???   不，實際上在我人生第一次看完後在沒實戰過的情況下我垃圾到翻開了線上期末考出來寫，然後很華麗地拿了高中以來數學科第一個不及格---53.xx分   此時拿起手錶，星期六1:05am ，距離實考還有大約9個小時......算了，睡覺~   至考前有4小時，再次拿起書本開始狂複習、拿出錯過的題目訂正......總之，還算有精神讀得下去吧。   到了交大，考卷發下來了，共12題，2小時作答時間，大約掃個題......我鬆了一口氣，呼~認知範疇之內~爽!!!   考完試後身心果真舒暢~然後在教室外巧遇在校化學培根電神，他是來考化學筆試的，接著與電神聊了聊他的讀書方式與技巧......哈哈~他也跟我一樣是臨陣磨槍(吧?)~但聽說課程網上的所有考試他都滿分(?(我果然還是不能跟他混為一談 QAQ)   總之，這次的培訓計畫讓我深可體會時間的管理好重要(?

8/13~8/17我在清大程式解題營的基礎班裡進修，收益不少，也挫折不少。   首先今年是ION CAMP第二屆，除了營長&副營長之外其他講師貌似都跟第一屆不一樣，然後今年的我覺得講得讓我比較懂(?   我基礎班的課都是跟 李昕威 電神與 王均倍 大神坐在教室最後面耍費(因為有插座)，但在邊刻CF的同時我也順便學會了懶惰標記、BIT、離散化、SPFA、MST(Kruskal&Prim)、KMP,複習了dsu的union by rank，也同時被王均倍指點了可以改成union by size(開心)   這次進階班是在晚上基礎班打模擬賽同時開班，因此我第一天時猶豫要聽課還是練習早上&下午所學，但聽說比賽後的題目會放到SOJ上當Problem題，我便毫不猶豫地踏向進階班......   在進ION CAMP前才被一階電神醍醐灌頂過學會&精熟的差別，因此第一天的目標即是 學會 進階班的課程即可   我在進階班裡學會了Treap、SCC、2-SAT、LCA、持久化線段樹，持久化隨機二叉樹，然後完全聽不懂莫隊、樹練剖分(QAQ)   大約晚上10點半回到宿舍，不是打CF就是學刻模板，還記得第三天晚上卦長來我們宿舍看到我在打CF，他問說我是甚麼顏色，我回說可愛綠人，他回我他也是淺綠，雖然我只打兩次，哈哈，(嗚......我聽了快崩淚了，感到莫名帶刺的安慰TAT)   最後一天有基礎&進階班混和上機考，我莫名的發現編譯器無法執行我的程式，de了一小時的bug才發現我用的那台電腦的編譯器不支援C++11 QQ，這時我才拿出我的筆電(我學乖了)   結業後一階電神告訴了我我這次來學經驗，而他是環境適合專心打code，但我怎麼貌似在進階班時瞄到他在看天才麻將少女(?   然後早上上課時我也瞄到了鄰座的王均倍在打賽爾號，頓時也讓我重新回想起了童年的那份回憶，感動感動~~   還有吃飯時營長放Fate Zero給我們看，可惜我前面沒看到，要記得補~