POI - PA 2010 Round 2 Coins

翻譯:

給你n, k還有一個由R, O組成的長度n的序列。

找出區間[i, j]使得這個區間內O的個數是R的k倍，這個區間最長能多長

n, k <= 1,000,000


Sample Input:
15 3
RORROOROOROOORO



Sample Output:
8





solution:

這題跟之前USACO一題有異曲同工之感。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3274

定義f(i) = 1~i出現多少個R - (i/(k+1))

那麼會發現，若f(a) == f(b)則 [a+1, b]必為合法區間

排序 O(n lg n)或Hash O(n)就結束了。

蝴蝶作法雖然核心一樣不過細節完全不同，雖然一樣O(n lg n)

POI 11th Spies

題外話：

這題是POI XI Stage I當年第二多人寫出來的題目


最多那題沒有放在main上面QQ


當年這題 190/334 個滿分，不過我覺得這題明明沒有簡單到這種程度= =


// 好罩電波一定覺得是秒殺題


噢然後，Example裡面有一個1打成小寫L，我在想怎麼一直RE





翻譯：

BIA僱用了很多間諜，每個間諜都被下令要監視其他另一個間諜。

KB想要選一些間諜去進行絕密任務，而且他希望能委任越多間諜越好。

然而這個任務太重要了，所以他希望每個被委任的間諜都至少被一個沒有參與任務的間諜
監視。（而且目前的跟監關係不能變動。）


輸入第一行含一個數字n <= 1,000,000，表示共有n個間諜，接下來會有n行

第i+1行會有一個數字Ai，表示間諜i的跟監對象是Ai。

輸出包涵一個數字K，表示最多可以委任K個間諜並符合題目要求。



Example:
6
2
3
1
3
6
5

the correct result is:
3

===================================題解========================





保證每個點都只會有一條連出去的邊，所以每個連通塊一定是一些鍊，

然後有可能在末尾出現一個環。


對於那些鍊，有一個很明顯而且好證的貪心法就是：


1. 如果那個點入分枝度為零，不能取
2. 如果進入那個點的所有點中有任何一個沒有被取的，那麼他就可以取

然後再來處理每個環：

1. 如果那個環所有點入分枝度都是1 -> 可以取  環長/2 取高斯個點
2. 如果那個環有些點入分枝度 > 1 且有至少一個進入他的點沒被取  那他也可以取
   然後剩下的點依照跟鍊一樣的邏輯取完。


總複雜度 O(V)

COCI 2009/2010 #3 p5

標題好長XD


簡單的說

第一行有兩個數字N, C

接下來給你一條數列S  ，長度是N(<=300,000)，裡面的數字範圍是1~C(<=10,000)

第三行是一個數字M(<=10,000)表示有幾組詢問

接下來M組詢問，每組有L, R(1<=L<=R<=N)

問你閉區間[L, R]中有沒有哪個數字出現超過一半？有的話問是哪個數字？

Sample input:
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10

Sample output:
no
yes 1
no
yes 1
no
yes 2
no
yes 3


全國賽那天晚上戰的COCI的題目(轉

小鬼當時說他會做了不知道跟官方solution一不一樣(欸

shik表示：蒙地卡羅應該會過


不過官方solution好好玩(打滾











========================solution===================


先不要考慮原題目，來想另一個遊戲：

給你一個序列S，每次可以把S裡面相異兩個數字抹掉。

直到全部都剩下同一個數字時遊戲結束

例如 12312323->312323->1323->33m 時結束。

這時紀錄兩個數 candi表示剩下的數字是什麼  count表示結束狀態多長

例如上述例子   candi=3 count=2




引理：如果有個數字出現超過length/2次，那他一定會是candi，無論過程

那麼，我們只要維護一棵seg tree就可以作到區間查詢candi了ˇ

就是分L.candi==R.candi以及L.candi!=R.candi時比兩個count大小

然後求出這個區間的candi，再去用另一棵seg tree計算他出現幾次

如果出現>length/2次就是yes  否則則是no