Codeforces 375－斑的家

C. Circling Round Treasures

題解：看了其他人的code 才知道解法，這題真有意思。

dp[x][y][state] ：表示目前在點(x,y) ，state 是一個 bitmask ，若某位為 1 表示 object 在所圍的框框當中。

要如何知道object 是否在框框當中，這裡使用射線法。若某點在所圍的範圍中，則此點往任意方法產生的線只會和所圍的範圍有奇數個交會。

有些細節要特別注意：

假設射線是 x = (obj 的 x )。

這時要想什麼請況才算有交會？見圖

綠色的點是 object , 往上的綠線是射線。

為了避免 (x,y) , (x+1,y), (x+2,y) , 而object 為 (x+1, y') , y' < y

(x,y) -> (x+1,y) 算是和射線有交會，而 (x+1,y) -> (x+2,y) 也是。

我們只能計算其中一種，因為事實上只有一個交點。

上圖中的咖啡色的線表示我計算交會的時機。

從dp[start.x][start.y][0] 做 bfs ，最後算 dp[start.x][start.y][ mask] , mask = [0, 1<<( treasure_number)-1]

在做一點最後處理就得到答案了。看到解答後，心想真是太神了！

D. Tree and Queries

題解：我一開始就想到先把 tree 變成 segment , 然後用 bucket 的方式算，但是時間複雜度是 O(n*sqrt(n)) ，我覺得 1s 會超時。

後來看了官方的解答後，得知有 O(n*logn*logn) 的做法。

其實，這題算暴力，但是用了一點trick 。因為某個 tree 的答案是從它的 subtree 累積的, 這棵 tree ，可以直接拿最多點的

subtree 的結果去計算。關於答案是要算 (number of node = color ) >= k 有幾個，可以用fenwick tree , 或用 map + vector。

稍微提一下 map + vector 要怎麼算出答案？

每次都會有一個operation : 將某color 的個數 + 1

map<int,int> m ; // first : color , second : 此color 的個數。

vector<int> vec; // index : 此color 的個數， value : 有幾個。

例如：g,b,r,b,b,r,r ,r

令operation 為

void add(int x)
{
int t = (++m[x]);
if(t > vec.size()) vec.push_back(0);
vec[t-1]++; // vec index i 表示某 color 的個數有 i+1 個。
}

所以會有 add(g), add(b),add(r),add(b) ...