Competitive Programming►Problems

TIOJ 1332 - 名義老爸

Link: http://tioj.ck.tp.edu.tw/problems/1332

用map(也可用set包pair)隨便亂寫AC，插入的時候用map找比它大和比它小的兩數分別是誰，誰比較晚插入誰就是它的爸爸。
複雜度O(nlgn)，據說正解是用笛卡爾樹O(n)，參考:
http://ckhs1328.pixnet.net/blog/post/40525136-tioj-1332-%E5%90%8D%E7%BE%A9%E8%80%81%E7%88%B8
http://cbdcoding.blogspot.tw/2015/03/tioj-1332.html

Read More

Competitive Programming►Problems

1210 - 圖論 之 簡單圖測試

Link: http://tioj.ck.tp.edu.tw/problems/1210
一開始想說隨便亂連，如果發現不能連就不是簡單圖，後來發現是假解，試試以下這筆測資:

1
2
3
3
1 1 2
0

如果一開始前2個點連在一起，就會造成第3個點無法連邊，但事實上可以前2點分別和第3點相連

後來改變作法，每次從度數最大的點開始連就對了，查了一下原來這是Havel定理
這篇好像說明得不錯，有Havel定理的證明
http://blog.csdn.net/shuangde800/article/details/7857246

發現UVA上有一模一樣的題目(僅輸出格式不同): UVa 10720
POJ上的類似題，需要輸出相連關係: POJ 1659

Read More

Algorithm

C++ STL nth_element

std::nth_element保證在O(n)的時間複雜度內求出陣列中第k大的數字
http://www.cplusplus.com/reference/algorithm/nth_element/

用法網路上應該有很多說明，在此就不再解說了，不過關於它的原理網路上的中文文章就有點少了

nth_element使用的演算法是Introselect，Introselect算是優化過後的Quickselect

Quickselect的概念大概是做一半的Quicksort，Quicksort平均來說需要做lg(n)次，每次O(n)，但Quickselect每次只需做和自己相關的那一半就好了，也就是說第1次O(n),第2次O(n/2),第3次O(n/4),第4次O(n/8)…，n+n/2+n/4+n/8+n/16…=2*n，因此總複雜度為O(n)

Read More

Competitive Programming►Problems

Codeforces 280B - Maximum Xor Secondary

Link: http://codeforces.com/problemset/problem/280/B

我的作法頗奇怪的，貼出來分享一下
這題可以用stack單調性O(n)解決，聽起來還滿簡單的，不過我想到的方法不太一樣(反正這題應該有很多種解法)

作法大概是把數字看成二進位，計算它們的有多少位元，要xor的兩個數字的位元數一定不同(除非所有數字位元數相同)，而且其中一個必有最大位元數，暴力弄一弄複雜度還是O(n) (見27行以後)
所有數字位元數相同時，其實可以處理成位元數不同 (見14~25行)

AC submission: http://codeforces.com/contest/280/submission/12995655

Read More