[比賽紀錄] LeetCode Weekly Contest #86

睡過頭…

同步 post 於 WP

https://colistar905208901.wordpress.com/2018/05/27/leetcode-weekly-contest86/

Q1. Magic Squares In Grid

給定一個 100 x 100 2d-array，
問有多少 3 x 3 sub-array 是魔方陣。
(即 行列對角線都是 15 且數字 1~9 不重複。)

這種範圍超小的拼速度題目重點變成了怎麼寫比較快，
直覺的做法有兩種：

1. 直接靠定義作，每個 sub-array 檢查八條跟數字範圍。
2. 因為 3×3 魔方陣只有一種 (跟他的旋轉鏡射) 先把那種手寫出來後做 pattern matching 。

由於還要做八種旋轉鏡射，這題當然是寫 1. 快很多啦。

Q2. Keys and Rooms

有許多房間，每個房間都有其他房間的鑰匙。
你一開始在房間 0 ，問你能不能進入所有房間。

非常明顯的純 BFS 題，事實上這根本是直接給你 adjacency matrix 的意思。

Q3. Split Array into Fibonacci Sequence

將一個 digit 串 拆成 >=  3塊，
滿足剛好由左而右形成類似費氏數列的關係。
例如 “110111122335588143″ 拆成 [11, 0, 11, 11, 22, 33, 55, 88, 143]

串長度至多 200 ，一看又是純粹考實作。

因為要處理 leading zero 問題，
最簡單的想法當然是把整個數列以整數方式儲存後再轉為字串，作字串比對。
這樣單一次比對的複雜度是  ，顯然很充裕。

那麼就只要枚舉前兩項 F1, F2 即可。

Q4. Guess the Word

給你一個 100 words 的字典，單字長度都是 6。
對方已經想了一個字典內的單字，你要在 10 次 guess 中猜到它。
你每次 guess 可以猜一個單字，他會告訴你有多少個字元位置正確 (match)。
例如 答案為 “abcdef" 你 guess(“abccfe") 會得到 3

又是 100 看到就知道複雜度不是重點。

考量我們有一個 wordlist 的情況，有什麼做法能比亂猜更好？
因為字典在我們這邊，我們可以每個都 guess 看看，看 match 的分布哪個最好。
怎麼判斷 match 的分布哪個最好 最單純的想法就是 minimize max value。

照著這樣做就可以過了。

(第一次寫的時候根本沒有minimize max value，固定 guess index 0 當然的錯了)

時間分配

Q1 (+26min)
Q2 (+11min)
Q3 (+15min)
Q4 (+16min) (+1bug)

賴床太久 寫太慢 好像就這樣
Q2 發現對 python 語法不太熟 (有內建的好用 queue 嗎)
馬上轉寫 c++

Q3 還是跟 python 語法不太熟 array of chars / string 搞好久

[比賽紀錄] Meteor Coding Cup Round #4

臨時被抓去打的，給高中生的競賽程式用的比賽。
題目我覺得給高中競賽現役玩挺好的，不過我太久沒碰競賽程式了打得很爛。
(搞不好對高中現役來說過簡單，我就不知道了)


https://colistar905208901.wordpress.com/2018/05/27/mcc-4/

以後搬到 WP 好了 支援 latex / markdown 還是滿舒服的

hihocoder 1517 模拟降水

有夠難寫的
先放草稿，有空或心情好再修

簡單將作法分為三個部分

第一步是要把可以接受雨量的區域橫向切成許多矩形，這邊用 Stack （堆疊）操作，並且要把實際上不能接水（碰到最左最右的）做標記

第二步是計算降水 我們先處理比較簡單的case：一定只會從最左邊降水，那會發現 會優先選擇從「右界較小」的矩形降水，右界相同時是「左界較大」，依序標上降水順序，一個一個填滿，將填滿後的資料記下來，會是一個個矩形，我們稱做降水矩形

 不過注意這題降水點在中間 這樣就是左右分別標好後 取面積較小的先填滿 不過這邊有個麻煩case是要處理橫跨自己的矩形。
事實上 case 是五個，依序是
1. 左右是同一塊，都是跨過降水點的矩形
2. 左邊跨過降水點 右邊是正常，如此水會全部往右流
3. 和2.相反
4. 左右都正常，左邊較小，如此會花 w 將左邊填滿，同時 w 流向右邊
5. 和4.相反

第三步就是 哪些被填滿多少後 計算 T 那點的深度 這點就簡單了。
事實上只需要把經過 T 的降水矩形高度加起來就好。
要求出全部也很簡單，對每個降水矩形用左界+h右界-h 左往右做總和序列就好了

http://ideone.com/vc74vJ

NTUJ 1317 Another Easy but Not That Easy Problem

                                                                                                                                                                                                                       .
                                                                                                                                                                                                                       .





世界奇怪的題目耶，

Def f(a) = 1^x + 2^x + ... + a^x

可以知道f()應該是一個(x+1)次函式，

既然是(x+1)次咩，表示只要給定x+2個數字，就可以決定這個函式

這時候就用拉格朗日長直髮 不對 拉格朗日插值法，


而很巧妙的，如果我們帶的是f(1)~f(x+2)，盯著下面這個式子看

Σ bj * Π(a-ai)/(aj-ai)


會發現他變成


Σbj * [ (a-1)(a-2)...(a-(aj-1)) / (aj-1)! ] * [ (a-(aj+1))(a-(aj+2))...(a-(x+2)) / (x+2-aj)! ] * (-1)^(x+2-aj)


哇烏 這不就


Σbj [C(a-1)取(aj-1)] * [C(a-aj-1)取(x+2-aj)] * (-1)^(x+2-aj)


輕鬆愉快



總複雜度O(x)

NTUJ 1707 k-th number

恩沒錯，就是傳說中的經典的劃分樹。                                                                                                           .




其實超級好寫，只是兒子的區間要算好|||。

還有如果數字相同要處理一下，這個有點麻煩就是，還好這題保證沒有相同

網路上找得到許多教程，其實瞪著notonlysuccess的圖看幾秒就會領悟了

所以只是來備份代碼


#include <cstdio>
#include <cstring>
#include <algorithm>

#define MN 100010

int sorted[MN], val[20][MN], lcnt[20][MN];
int N, Q;

void build(int tl, int tr, int dep) {
    if(tl == tr) return ;
    int mid = (tl+tr)/2, pre = 0;
    int lc = tl, rc = mid+1;
    for(int i=tl; i<=tr; i++) {
        lcnt[dep][i] = pre;
        if(val[dep][i] <= sorted[mid]) {
            lcnt[dep][i] ++;
            val[dep+1][lc ++] = val[dep][i];
        }
        else val[dep+1][rc ++] = val[dep][i];
        pre = lcnt[dep][i];
    }
    build(tl, mid, dep+1);
    build(mid+1, tr, dep+1);
}

int query(int ql, int qr, int tl, int tr, int k, int dep) {
    if(tl == tr) return val[dep][tl];
    int mid = (tl+tr)/2, ql2L, qr2L, qinL;
    ql2L = lcnt[dep][ql] - (val[dep][ql]<=sorted[mid]);
    qr2L = lcnt[dep][qr];
    qinL = qr2L - ql2L;
    int newL, newR, newK;
    if(qinL >= k) {
        newL = tl + ql2L;
        newR = tl + qr2L - 1;
        newK = k;
        return query(newL, newR, tl, mid, newK, dep+1);
    }
    else {
        newL = mid + ql - tl - ql2L + 1;
        newR = mid + qr - tl - qr2L + 1;
        newK = k - qinL;
        return query(newL, newR, mid+1, tr, newK, dep+1);
    }

}

int main() {
    while(~scanf("%d%d", &N, &Q)) {
        for(int i=1; i<=N; i++) {
            scanf("%d", sorted+i);
            val[0][i] = sorted[i];
        }
        std::sort(sorted+1, sorted+1+N);
        build(1, N, 0);
        for(int i=1; i<=Q; i++) {
            int L, R, K;
            scanf("%d%d%d", &L, &R, &K);
            printf("%d\n", query(L, R, 1, N, K, 0));
        }
    }
}

TIOJ 1100 C.畢業演奏 [DP]

我說這題好詭異……O(N*L)會過是毛啦orz
Nice Problem.只是我想了太久XDrz

要先有一個概念：如果最後有合奏的學姐序列依照合奏時間用S1~Sk表示。

那麼對任意i，一定有Si的編號 < S(i+1)的編號。

也就是不會有a區間比b區間前面 但是a學姐比b學姐晚合奏完的情況。

 

怎麼證明呢？假設最佳序列是S'1~S'k而且其中存在一個i，S'i的編號 > S'(i+1)的編號

但經過一點點的小證明可以發現，把這兩個學姐交換順序也一定存在一個合法的合奏方案。

//因為區間有非嚴格遞增性才會合理。

 

所以我們可以用DP[i][j]表示做完前i個學姐，取了j個學姐時最右界的位置。

每個轉移O(1)，總複雜度O(N^2)

 

 

 

UVa 506 System Dependencies

,

,

,

,

,



Link






===簡單的翻譯(不逐字翻了...字好多)



安裝軟體有很多依存關係，例如說你沒有TCPIP你就裝不起來TELNET。



所以如果明確(explicity)要裝TELNET，你會附帶地把TCPIP裝起來。

等你下次裝FTP(也需要TCPIP)時，就不用重裝一遍TCPIP。

但同樣的，在TELNET還裝著的情況下你不能把TCPIP移除。



有時候我們需要移除一些程式。為了省出更多空間，我們在移除某些程式時會把一些

只為了這個程式能正常運行才附帶安裝的檔案一起移除。

例如說如果我們為了裝TELNET而把TCPIP附帶裝起來，之後我們移除TELNET時發現，

TCPIP只是為了讓TELNET能正常運作而附帶安裝，TELNET移除後TCPIP將沒有存在的必要

便會順便將TCPIP解除安裝。



已經裝上的軟體不會再被安裝一遍(因為附帶而安裝的軟體不會因為再被安裝一遍而

變成明確要安裝的軟體)、已經移除的軟體也不能再被移除。



===



寫這題用到一堆C++的技巧xD



#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <sstream>

#include <list>

#include <vector>

#include <string>

#include <map>



#define MAX 2510



//Converter

std::map<std::string, int> conv;

std::string rconv[MAX];

int ccnt;

//Answer List

std::list<int> ans;

std::list<int>::iterator it;

//Graph

std::vector<int> re[MAX], ee[MAX];

//DAG DP

int chneed[MAX], vst[MAX], ins[MAX], im[MAX];

//Parser

std::stringstream sin;

std::string buf;



inline int getno(std::string&b) {

 int rtn = conv[b];

 if(rtn == 0) {

  ccnt ++;

  conv[b] = ccnt;

  rconv[ccnt] = b;

  rtn = ccnt;

 }

 return rtn;

}



inline void insert(int np) {

 ans.push_back(np);

 ins[np] = true;

 std::cout << "   Installing " << rconv[np] << '\n';

}



void dfsI(int now) {

 chneed[now] ++;

 vst[now] ++;

 for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(vst[nxt]) continue;

  dfsI(nxt);

 }

 if(!ins[now]) {

  ins[now] = true;

  insert(now);

 }

}



inline void remove(int np) {

 ans.remove(np);

 ins[np] = im[np] = false;

 std::cout << "   Removing " << rconv[np] << '\n';

}



void dfsR1(int now, int need) {

 vst[now] = true;

 chneed[now] -= need;

 for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(vst[nxt]) continue;

  dfsR1(nxt, need);

 }

}



void dfsR2(int now) {

 if(chneed[now]) return;

 int can = true;

 for(int i=ee[now].size()-1,nxt; i>=0; i--) {

  nxt = ee[now][i];

  if(ins[nxt]) {

   can = false;

   break;

  }

 }

 if(!can) return;

 remove(now);

 for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(!ins[nxt]) continue;

  dfsR2(nxt);

 }

}



int main() {

 while(true) {

  getline(std::cin, buf);

  std::cout << buf << '\n';

  sin.clear();

  sin.str(buf);

  sin >> buf;

  std::string ch, fa;

  int nch, nfa;

  switch(buf[0]) {

   case 'D':

    sin >> ch;

    nch = getno(ch);

    while(sin >> fa) {

     nfa = getno(fa);

     re[nch].push_back(nfa);

     ee[nfa].push_back(nch);

    }

   break;

   case 'I':

    sin >> ch;

    nch = getno(ch);

    if(ins[nch]) {

     std::cout << "   " << ch <<  " is already installed.\n";

    }

    else {

     memset(vst, 0, sizeof(vst));

     im[nch] = true;

     dfsI(nch);

    }

   break;

   case 'R':

    sin >> ch;

    nch = getno(ch);

    if(!ins[nch]) {

     std::cout << "   " << ch << " is not installed.\n";

    }

    else {

     if(chneed[nch]>1 || (chneed[nch]==1 && !im[nch])) {

      std::cout << "   " << ch << " is still needed.\n";

     }

     else {

      memset(vst, 0, sizeof(vst));

      dfsR1(nch, im[nch]);

      dfsR2(nch);

     }

    }

   break;

   case 'L':

    for(it=ans.begin(); it!=ans.end(); it++) {

     std::cout << "   " << rconv[*it] << '\n';

    }

   break;

   case 'E':

    exit(0);

   break;

  }

 }

}

//8966453  506  System Dependencies  Accepted  C++  0.024  2011-06-19 06:57:53

NTUJ 0906 Power Grid

43059 0906 - Power Grid poao899 Accepted C++ 0.600 2011-03-23 14:12:06 .

.















要仔細看清楚題目啊orz...





1. 每個邊都要走過至少一遍

2. 不能繞路

3. 城市只會出現在葉子

4. 點心數目範圍















考量某個節點：



每個子樹邊權和依序為A1 A2 A3 A4...An

每個子樹有點心的點數依序為B1 B2 B3 B4...Bn



那假設他走訪順序是s1 s2 s3 s4 ... sn



那麼浪費掉的點心是2 * [ As1 * ( Bs2+...+Bsn ) + As2 * ( Bs3+...+Bsn ) + ... + As(n-1) * ( 0 ) ]





先不要看這個式子，我們先把題目特殊化，假設所有的B都=1



那麼很逗趣的，浪費點心的式子變成：



2 * [ As1 * (n-1) + As2 * (n-2) + ... + As(n-1) * (0) ]



很明顯可以用排序不等式證明，A越小的要越先走。那麼我們回到一般化的問題：





如何使之極小化呢？想像把一個邊權和Ak 點數Bk的子樹拆成Bk個子樹 每個的A=(Ak/Bk)、這樣每個新子樹的B都會是1了



那麼利用上述結論會發現，Ak/Bk越小的子樹應該先走。顯然是一個正確的貪心策略





值得一提的是假設沒有上述性質2. 就可能出現先走一棵走一半之類的，就不知道怎做了orz

94全國賽 6. 下棋問題

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
數據範圍N到5000，但是記憶體卻只給到約略N^2/2。







首先因為我想不到在線(Inline)的作法，故從離線(Offline)開始想起。



當沒有任何阻隔時，任兩個棋子A, B都可以形成一個矩形。



這個矩形出現的時間是max(A, B)，也就是兩個棋子都被下下去始，直到他們中間有其他棋子出現。



也就是如果我們可以枚舉每對棋子，並且快速地算出這個矩形被破壞的時間，這題便可以做了！



而他被破壞的時間就是這個矩形區間中最早放下去的棋子。



所以變成每次查詢一個矩形，問矩形內最早放下的棋子。



這很明顯就是二維的RMQ問題！而二維RMQ可以用Sparse Table作到每次查詢O(lg^2 N)







所以我們就得到一個算法了：



**枚舉每個矩形，查詢那個區間最早被放下的棋子。



**之後我們會得到N(N-1)/2個區間 每個區間代表這個該個矩形的生命週期。



**之後對這些區間進行排序，線性掃過後可以求出每一個時間點場上"存活"的矩形有幾個。



這樣總複雜度會是O(N^2 lg^2 N)，但是記憶體非常不理想地是(N^2 lg^2 N)，



除了執行速度太慢之外，記憶體空間也不足。











以此，需要更優化此算法。



也就是要在O(N^2)以內的複雜度內求出每個矩形的生命週期。



我們想到了分而治之法。(Divide & Conquer)





首先沿中線將棋盤分為左右兩塊，左塊內的矩形及右塊內的矩形可以透過遞歸做出。



現在我們要處理的就是跨越中間線的矩形。







如上圖所示，該矩形會被中線切割為藍色塊跟紅色塊。



該矩形的死期(?)理當為Min(藍色塊內最早被放下的點, 紅色塊內最早被放下的點)



而該怎麼求出每一個點對的每個色塊呢？



我們繼續觀察下去，觀察P對B這個矩形。



我們會發現他在中間線左邊那個紫色塊完全把上圖藍色塊包含了。







也就是其實我們可以用O(點數)求出左邊每個以P為左下角的色塊 內最早被放下的點，



就只要沿著Y軸遞增掃下去即可。





如此每個矩形只會被中線切一次，故總計算量實際上是O(N^2)，也就是矩形數量。







至於記憶體(內存)不夠的問題呢，會發現只要改一下計算順序，記憶體總共只需要N的常數倍，顯然夠用。

















以上。





=====題外話：=====



這題是在94年全國賽的難題之一，



最近幾年全國賽無論是測試數據強度或是題目難度感覺都有點比不上以往...





當年賽後，有選手提出了這題的在線作法



也就是每次加入一個點，算出這個點增加了幾個、破壞了幾個

OIBH 2006 模擬試題3 prob 3 情书抄写员

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

http://mail.bashu.cn:8080/BSoiOnline/showproblem?problem_id=1629





顯而易見可以得到第n天的情書數量有F(n) = F(n-1) + k * F(n-2)









先講結論，gcd(F(a), F(b)) = F(gcd(a, b))

以下證明 by willyliu

Lemma 1 : gcd(F(n), k) = 1

proof :

gcd(F(n), k)

= gcd(F(n-1) +F(n-2)k, k)

= gcd(F(n-1), k)

= ... = 1



Lemma 2 : gcd(F(n), F(n+1)) = 1

proof :

gcd(F(n), F(n+1))

= gcd(F(n), F(n) + F(n-1)k)

= gcd(F(n), F(n-1)) ∵Lemma 1

= ... = 1



Lemma 3 : F(a+b) = F(a)F(b+1) + F(a-1)F(b)k

proof :

F(a+b)

= F(a+b-1) + F(a+b-2)k

Induction on b,

= ( F(a)F(b) + F(a-1)F(b-1)k ) + ( F(a)F(b-1) + F(a-1)F(b-2)k )k

= F(a) * ( F(b) + F(b-1)k ) + F(a-1) * ( F(b-1) + F(b-2)k )k

= F(a)F(b+1) + F(a-1)F(b)k



Theorem : gcd(F(a), F(b)) = F(gcd(a, b))

proof :

WLDG a ≧ b,

gcd( F(a), F(b) )

= gcd( F(a-b + b), F(b) )

= gcd( F(a-b)F(b+1) + F(a-b-1)F(b), F(b) ) ∵Lemma 3

= gcd( F(a-b)F(b+1), F(b) )

= gcd( F(a-b), F(b) ) ∵Lemma 2

= gcd( F(a mod b), F(b) )

= F( gcd(a, b) ) Q.E.D.

NOI2010 航空管制

　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　


　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　



先附個題目連結，

http://hi.baidu.com/%D2%DD%C3%F7%BE%A8%C8%CB/blog/item/4bb3383d07f175cf7d1e71d5.html





第一部分很簡單，就把所有限制建構成一個DAG，



把頂點依照"最遲起飛時間"排序，由小到大儘量滿足即可。



由於保證有解，所以這部分相信不是大問題。複雜度O(N+M)









第二部分先講一下我首先想到的想法：



如果該架飛機的起飛時間在[1, K]之間，然後我們二分搜K顯然可以得到答案。



二分搜之後我們可以變成把該節點的最遲起飛時間變成K，然後做一次第一題檢查是否有解



對每個的複雜度是O((N+M)lgN)，總複雜度約O(NMlgN)



而且其實二分搜的範圍很小，應該運行速度不會太慢。





如果有把第一題弄成一個function實作難度會降低很多。





另外附一個剛才在網路上找到的不錯思路：



http://yzm-blog.appspot.com/2010/08/8/NOI-2010.html



用Heap實作，複雜度差不多。

TIOJ 題目分類

亂做的 不要太相信裡面的難度(?)


http://poao.infor.org/TIOJ.xls








說真的發現好多經典題目都沒寫過(zz

USACO Jan. 2011 Gold

不愉悅orz                                   



一直有人在問我數學XD


這次pB pC可解 不過pC稍微難寫一點


pA猜個N lg N + K lg^2 N 好了

感覺就是輕重鏈剖分orz

Practice : Asia Beijing 2008 / 2009

北京賽區。據說當年五題+不錯的Penalty就可以拿到金獎  雖然不知道金獎怎麼定義XDD                             .

Beijing (China)

 

ID Problem Title Download Hint Ranking 4322 Destroying the bus stations YES 4323 A simple stone game YES 4324 Ugly Windows YES 4325 Tornado YES 4326 Minimal Ratio Tree YES 4327 Parade YES 4328 Priest John's Busiest Day YES 4329 Ping pong YES 4330 Timer YES 4331 Elevator YES

pA 給你一張有向圖(V=50 E=4000)和K，問至少要拔幾個點才使得1->N的最短路大於等於K
(邊權皆為1、1->N沒有直接連邊)

用最大流想法：增廣到該次最短路長度>=K就結束，輸出目前源點流量   不過依然WA

pB給你N和K，兩人輪流取石頭，第一個人第一次只能拿1~N-1顆、
以後每個人每次拿的數量不能超過上衣個人K倍，問先手必勝的第一步？

沒想法，不過應該是經典題

pC給你一張NxM圖片，問你有幾個矩形框在最上層？

模擬，但是注意回字型。

pD有一個龍捲風路徑是一條射線，給你他的速度，還有一個人在兩點之間等速往復運動，問龍捲風到人的最近距離？

沒想法

pE給一張無向有權完全圖，你要輸出一組M個點的生成樹且邊權和/點權和最小，且點排好後的字典序最小。

爆搜，注意一下精度問題。

pF給一張NxM網格(N=100,M=10000)，橫向(M方向)每條路徑都有兩個權重，v跟k。
從最底下任意一點開始，到最上面任意一點。只能往上或左右走，且走過路徑不能再走，
且每層(依照N分層)走過的路徑sum k要小於給定的K，求出整條路徑sum v的最大值。

DP，每層轉移需要Deque，不過我還在WAorz

pG給你很多區間(N=100000)代表婚禮，牧師必須選擇一段連續段來進行證婚。
這段必須要大於區間大小的一半，且牧師只有一個人不能分身，問有沒有可能替所有婚禮證婚？

Greedy (by worm)，還不會

pH給你一個序列ar(長度=100000)，問有幾個三數對A,B,C符合位置A<B<C且ar[B]介於ar[A]和ar[C]之間。

頗裸的Binary Indexed Tree

pI, pJ沒看題目


總體而言打得很失敗orz

不過要感謝suhorng, jurrasickill

TIOJ 1516 Problem F. HALLO ☆ GAME [Binary Tree]

3    91671    poao899    18388K    2197MS    G++     3.18K     2010-12-07 01:07:12                                            .


                                              


因為要正名(?)所以就不用Segment Tree這個名詞了XD

其實我覺得叫做Segment Tree也沒什麼不好，這種東西這麼常用總該有個名字吧XD

而且為什麼歪果仁講的就是正確的大陸人講就是亂講(?)


或許我跟這些都不熟上面只是我一廂情願罷了XD


反正以後這種東西在我的部落格上都會紀錄為Binary Tree?



這題操作很多，不過不難寫。

只需要有三個操作：

區間覆蓋、區間詢問、單點求值就好了。



不過這題還是值得推薦的?

因為它有用到存左邊右邊中間再meld的概念還有大陸學生口中的延遲標記(或sb標記?)

還有有些操作不能純用樹來作XD




仔細想了一下，似乎一棵純粹的Splay Tree可以支援所有操作？

因為那個旋轉說實話我搞了一個禮拜xD

[文件] about Miller-Rabin & Pollard-ρ

※前言

關於質數，台灣競賽方面似乎比較少提及，頂多學學篩法、根號檢驗法而已。

草提一下這兩個算法：



>>埃氏篩法：




//什麼毛啦顏色傳上來變得醜死了


O(N ln N)時間複雜度、O(N)記憶體，求出1~N所有的質數。

    一些優化：

        1. 僅 型如 6n ± 1 者有可能是質數（2 | 6n+2、3 | 6n+3、2 | 6n+4）

        其實這個優化加下去已經可以達到一定速度了。


        2. 用位元壓縮，記憶體僅需要(N/32)個int（排掉偶數可以剩下N/64，但個人認為沒必要）

    一些應用：

        1. 求出質因數個數：

            值得注意的是I = i*i要改成I = i+i才行。

        2. 求Φ(n)：

            即找出1~n-1中有幾個跟n互質的數。

            因為有Φ(n) = n * Π(1 - (1/p))     對每個質數p | n，所以可以用篩法作到。



// 另外，線性篩法我不會，所以省略...

相關題目：
    TIOJ：1036、1260、1353、1514、1535
    ACM：294




>>根號檢驗法：




O(√n)檢驗一個數是否為質數。

    一些應用：

        1. 質因數分解：

            每次除到不能除，若<= √p都試完了剩下的那個一定是質數。


相關題目：
    ACM：583



反正目前為止的台灣競賽幾乎都只注重以上兩者，相關題目也十分罕見（目前為止沒見過）

但是對於密碼學而言，以上算法都還不能讓人滿意。




>>Miller-Rabin：

一個能期望極快的判斷質數作法。

算法核心：

引理一：若p是質數，則a^(p-1) mod p = 1 （費瑪小定理）

引理二：若x² mod p = 1（其中x<p、p是質數）那x = p-1或x = 1 （證明就是用(x+1)(x-1) = kp）

然後若我們要測定n是否能通過以a為底的米勒拉賓測試
先把n-1 = 2^r * d ， 其中d是奇數   也就是求出n-1最高含2的幾次方



那麼   如果 a ^{(2r * d)} mod n 不是1  就一定是合數 （引理一）
       就繼續下去a ^{(2(r-1) * d)} mod n 得是n-1 或1（引理二）
       如果是n-1即是通過檢測，如果是1就繼續遞迴直到 a^d mod n


對int範圍的數字，只需要測 a = 2, 7, 61
對10^16內的數字，只需要測 a = 2, 3, 5, 7, 11, 13, 17, 61, 24251



所以只需要寫一個大數次方 + 主程序大概 20~30 行很OK。


虛擬碼就不附了，上次寫得爛爛的。

進一步可以參照Matrix67的相關文章。




>>Pollard-ρ：

還在學...

PKU 1286 Necklace of Beads [Pólya]

poao899    1286    Accepted    404K    0MS    G++    416B    2010-09-10 23:20:57                                          .



Pólya超經典題。

長為n<24的項鍊，三種顏色定義不同構為旋轉 翻轉<b>擇一</b>後不一樣者。


就套Pólya：

( Σ(i=1...n)(3^gcd(i, n)) + 翻轉 ) / 2n



反正學過真的就水過。

NTUJ 1021 Highway Patrol

36916    1021 - Highway Patrol    poao899    Accepted    C++    0.030    2010-09-05 19:41:21                            .



好題欸@@



題意：

一個大都會內有N座城市(<=100)，有M條單行道(<=1,000)

每個單行道可以用一個數組(u, v, p, s, x)表示，表示有一條道路從u往v，

如果要派軍隊巡邏要花費p的代價、裝監視器要s的代價 (0 <= p,s <= 1,000,000)

x代表這條道路的重要性，1表示極為重要，不可以用監視器。


因為這個大都會治安很差，每條道路都必須選擇上述兩種方式之一維持治安品質。

但是，每個軍隊巡邏完了要能回到自己的城市休息，所以我們希望每個城市出分枝度 == 入分枝度。

而且，市民們也不希望看到一個全部僅由監視器戍守的城市，所以至少得有一條路是巡邏。


問最少需要花多少錢滿足以上要求。





Input:

第一行有一個數字T表示測資筆數(T <= 70)

每筆測資第一行是N, M，接下來M行每行有五個數字u, v, p, s, x。


Output:

第i筆測資輸出Case [i]: [cost]

[i]表示測資筆數，[cost]表示你所花的錢，無解請用"impossible取代"。



Sample input:

3
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 0
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 1
2 1
1 2 10 25 1

Sample output:
Case 1: 40
Case 2: 65
Case 3: impossible























=================Solution================





簡單的先捏一下，flow。





因為把這個問題轉化一下可以想到，你可以假設一開始全部監視，那這樣總cost是Σ(si)。

然後每把一個邊變成巡邏的cost會是(pi-si)。

而且最後答案一定巡邏的邊會形成好幾個環。

所以就一直找全局最小環加上去，加到那個環是正的為止。

進一步會發現，變成有負圈的圖形每次尋找全局最小簡單環。不過很可惜這個題目沒多項式作法。



所以要換一個想法。


可以先把p便宜的邊先巡邏、s便宜的邊先監視。

然後建起來可替換邊以及他的替換代價，容量都是1

然後對每個點，檢查有幾個巡邏出發/幾個巡邏回來   其中的相差就建到S/E，cost=0，容量是差。

作一次帶權flow，算出答案...



然後還要檢查答案是否合法：如果==Σ(si)那就表示你一個邊都沒取

所以Warshall一次，找出最小圈輸出

PKU 2540 Hotter Colder [CG]

7564334    poao899    2540    Accepted    424K    0MS    G++    3998B    2010-09-02 22:09:01                         .



CG題好硬QQ不過應該是打定了XD寫起來頗有成就感(?)

看那精美的code length(望

不過   看到這題還是會想到IOI那個吧XD





題目大意：

有個房間，大小10*10

你一開始站在(0,0)，某個位置有一個熱源。

接下來每次你會移動到任意一個座標，然後會告訴你感覺Hotter還是Colder還是Same

每次移動輸出一個數字表示  "熱源可能位置"  的面積。

保證不會移動超過50次。





Sample Input：

10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter

Sample Output：

50.00
37.50
12.50
0.00



















===============解題報告===============


等於每次對多邊形切一條線，問面積。

測資很小所以可以每次把所有點掃過一遍。


幾個要注意的地方：

1.  判斷交點要注意等於0的狀況= =
2. 把兩個交點去修正多邊形時要注意加入的順序。
3. 注意如果重複點加入多邊形，會爆炸。




大概差不多這樣吧xD

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)