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

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

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