程式隨筆

Never give up!


  • Home

  • Categories

  • Archives

  • Tags

Codeforces Round 408 Div2 Problem C

Posted on 2017-04-16 | In Competitive Programming , Codeforces

Bank Hacking

Solution sketch

跟 binary search 無關,還有,時間複雜度如果亂估會以為會 TLE 的好題。

這題題解寫得很清楚,我只補充一下我當初有另外想通的地方。

為何只有 $m$, $m+1$, 和 $m+2$ 三種可能答案呢?因為這其實是一個 tree。所以說,如果我們把樹吊起來想,對於每個node來說,他至多就只可能被自己的parent和parent’s parent加到。

實作上,就是先建立一個總數表(我是對於$m+2$建表)。對於所有的點枚舉,只處理自己和他的鄰居這兩層後,求取minimax。

Read more »

POJ2376

Posted on 2017-04-14 | In Competitive Programming , POJ

Cleaning Shifts

Read more »

POJ3484

Posted on 2017-03-30 | In Competitive Programming , POJ

Showstopper

Solution sketch

觀察一下被reference的次數累積和(prefix sum),找出從偶數和變成奇數和的點就是答案了!

注意整除問題QAQ

Read more »

POJ3187

Posted on 2017-03-30 | In Competitive Programming , POJ

Backward Digit Sums

Solution sketch

Notice the $n = 1$ case…

Read more »

POJ2718

Posted on 2017-03-30 | In Competitive Programming , POJ

Smallest Difference

Solution sketch

基本上就是全排列後,中間切一半求差。

小心 leading zero 和 only zero 的 case。

Read more »

POJ3669

Posted on 2017-03-30 | In Competitive Programming , POJ

Meteor Shower

Solution sketch

Simply BFS.

Notice that…… the problem statement only states that the meteor will only strike
within the range [0, 300], but it does not state that the person can not walk beyond that range.

Read more »

POJ3579

Posted on 2017-03-24 | In Competitive Programming , POJ

Median

Solution sketch

超棒的題目!

想想這個數列吧! 2 2 3 9

Read more »

POJ3104

Posted on 2017-03-24 | In Competitive Programming , POJ

Drying

Solution sketch

別懶著推公式呀!QQ 二分搜尋被坑過幾次了還是被繼續坑QQ

設 x 為烘衣服時間:
$k * x + (mid - x) >= a_i$
$x(k - 1) >= a_i - mid$
$x >= \frac{(a_i - mid)}{(k - 1)}$

注意 special case!!

Read more »

HUD5441

Posted on 2017-01-20 | In Competitive Programming , HDU

HDU5441 Travel

Solution sketch

將 邊 和 query 都進行小到大排序後,對於 query 從小而大的處理,將不超過當下query大小的 邊 陸續加入並查集中,並在進行 Union 時維護總組數即可。

Read more »

HUD5443

Posted on 2017-01-20 | In Competitive Programming , HDU

HUD 5443 The Water Problem

Read more »
1234…7
Henry Tseng

Henry Tseng

64 posts
18 categories
57 tags
© 2017 Henry Tseng
Powered by Hexo
Theme - NexT.Pisces