gdoi2018

1/2ページ

GDOI2018賽前反思及檢查

該來的GDOI還是要來的。 雖然知道自己過不了校1/3限制,可一直還在苦苦掙扎。 時常忘了自己身在廣東(較弱的省)的紀中。 就算進不了隊,也要發揮出自己的水平吧,畢竟才初三,就算今年沒進隊,也還有兩年…… 調整心態,GDKOI雖然考得比較好,但是那只是GDKOI,頂多讓我進個市隊,3個月過去,停課的 […]

【GDOI2018模擬7.6】仰望星空

Description 由於原題看了好多遍才真正理解題意,這裡講一個簡化版本 給出平面上的一個圓和n個點 現在要再這n個點之間兩兩連邊 每個點只能被連一次,只有圓內和圓外之間距離不超過d的點可以互相連邊 且如果存在三個圓內的未被連邊的點x,y,z,與圓外一點w的距離不超過d 現在若想連線w和y,並且 […]

【GDOI2018模擬7.10】C 動態規劃

一套題目考兩道DP有意思?= = 題意略。 一開始其實想的接近正解了,但是後面就歪了,莫名其妙搞到30分= =。。 %%%world_wide_D,AK大佬,瑟瑟發抖。 一開始先把dp[i][j]預處理出來,表示A的前i位和B的前j位的最長公共子序列長度。 然後設f[i][j]表示A的前i位和B的前 […]

【GDOI2018模擬7.12】A 線段樹 樹狀陣列

這題用光了我所有的腦細胞,還沒A,成功導致我今天比賽瞬間爆炸。。 題意略。 首先肯定不能用歸併無腦求。。。否則你怎麼處理後面一問,這裡明顯提示我們第一問的某些東西可以用到第二問中。 先用樹狀陣列求出總逆序對數,同時算出每一位的貢獻。 然後對於第二問我們離線處理,先把所有的處理記錄一下,記錄每一位被更 […]

GDOI2018 涼涼記

Day0 今年GDOI在中山市一中,也就是主場了(從我家走路過去五分鐘) 不知道為什麼,晚上很困,九點半就睡著了?! Day1 早上大概七點起床,所以晚上是睡了多久…… 試機時間有半個鍾,八點半正式開始 試機的時候打了個exgcd,FFT之類的 題目 T1 給定一個陣列,將這個陣列劃分成若干段,每段 […]

【GDOI2018模擬7.10】C

Description Input Output 一行表示答案 Sample Input aa ab Sample Output 2 Solution 這題直接遞迴暴力就行了 設暴力帶3個引數x,y,l表示上面到x,下面到y,匹配長度為l 預處理一些東西,比如上面第x個字元匹配下面第y個字元之後的第 […]

【GDOI2018模擬7.12】B 矩陣乘法 dp

Description 給定一個3*3的網格圖,一開始每個格子上都站著一個機器人。每一步機器人可以走到相鄰格子或留在原地,同一個格子上可以有多個機器人。問走n步後,有多少種走法,滿足每個格子上都有機器人。答案對10^9 7取模。 Input 1 Output 229 這題是個大水但是我由於沉迷第一題 […]

【GDOI2018模擬7.12】B

Description 給定一個3*3的網格圖,一開始每個格子上都站著一個機器人。每一步機器人可以走到相鄰格子或留在原地,同一個格子上可以有多個機器人。問走n步後,有多少種走法,滿足每個格子上都有機器人。答案對10^9 7取模。 Input 一行一個整數n Output 一行一個整數表示答案 Sam […]