Codeforces Round #284 (Div. 2)

雖然#281 - #283都有做...
但看了一下好像很麻煩, 所以還是直接跳過
反正最想寫的還是這場 #284
因為它令我跑去學新東西了
話說這場只做了4題, 雖然其中也包括了Problem E啦...

Codeforces Round #280 (Div. 2)

題目: http://codeforces.com/contest/499/problems

A: (頹題)

頹題...只要沒看錯題目就是考你寫for loop而已=.=

B: (頹題)

也沒什麼算法可言的...就直接做吧, 一題關於STRING PROCESS的頹題

C: (Math)

這題開始有趣了,  簡化一下題意吧

Given n 條線, 它們把空間劃成很多不同region. 然後問你由point A 到point B, 最少要經過多少個region 

應該說, 只要把題目理解成上面的意思, 就變成很單純的數學題了...
由於題目所有point都以(x,y) 輸入,  感覺也不太需要變成vector 來做了

首先發現, 把AB 連成一條直線肯定是經過最少region的其中一個方法 (用Greedy的想法就知道不可能比它更好了) 

然後問題變成, 有多少條線橫跨AB之間?

利用一下簡單的數學特性:  把A點跟B點各自代入 n 條線之內

如果一個是正數一個是負數, 就代表他們被隔開了...

(不會等於0...因為題目說明A跟B都不在任何一條線上)

所以就是O(N) 算一下究竟A跟B是否處在第 i 條線的兩邊

話說實作時, 不能以一句 

  if((sx*a+sy*b+c)*(gx*a+gy*b+c) < 0) ans++;

來算答案...因為.....兩個數相乘會比long long更大...我的兩個WA啊...

D: (???)

沒看題目...而且就AC人數來說, 也沒什麼心情看...

E: (Math, Bipartite Matching)

重點來了! 正正是因為這一題, 我跑去學以前都沒心情學的matching了=.=

發現如果是bipartite graph的matching還是很好理解, 很好code的...

因此還繞了個道跑去做數題bipartite matching的題目....下一篇再詳談吧...

要說這題的話, 絕對不是馬後炮, 一開頭想的算法就已經是答案了...

無奈發現算法中要用到bipartite matching, 所以就跑去學了..

題意大約是這樣的:
有 n 個正整數 n, 再有 m pair 數字(mx ,my), 你可以把位於第mx 個的數字和位於第my 個的數字除任何一個大於1的數字 (要能整除),  同一pair 位置的數字可以選擇多次, 問最多可以執行多少次相除?  Given mx + my 一定是單數, n, m <= 100

是咁的, 由於mx + my 一定是單數, 所以可以選擇的位置一定是 單數跟雙數, 

自然把單數位置的數字跟雙數位置的 分開兩組...

然後由於是問最多可以相除多少次....自然會想到不論選擇那一pair 都會選擇除最小的公因數

最來就是如果一個數字同時可以跟另外數個數字相除,  那不論選擇那一pair 都沒所謂...

反正他也就只有限定數量的"因數" 而已...因數A 跟那一個數字的因數A相除都沒關係, 反正相除數都是加一, 又不影響以後的結果 (1999 MODE)

想到這兒, 不難想像Prime Factorization了吧...?
每個數字都有unique的prime factorization, 那麼把100個數字, 每個數字各自化為自身prime factorization 所有質因數的一堆vertex可行嗎? 

每一個數字 a <= 10^9,  最小的質因數可以是2, 那a 最多可以有 lg (a) 個質因數吧, 大約30個

所以也就共3000個vertex...

算法就出來了, 單數位置一組, 雙數位置一組, 有共同質因數的就連線, 組成一個bipartite graph

找這graph的maximum matching cardinality 就是答案了

好吧, 分兩步來說, 其實主要圖論的題目, 最煩人的都是建圖的部分...

後者的部分基本都是直plug 相關算法而已...

這題的建圖部分, 重點就是prime factorization, 我印象中不懂很快的算法

還是先找所有需要用到的質數吧...我這次用的是新學的改良後的質數篩法

很聰明的一邊打表, 一邊篩, 實際每個合成數只會access一次, 達至O(N)

感覺要一段時間才能理解並記下, 所以先留一個名

實際只要找 sqrt(10^9)內的質數, 就可以做到 10^9 的prime factorization了...

void make(){
    memset(f,false,sizeof(f));
    f[0] = f[1] = true;
    ps = p;

    for(int i=2; i*i < N; i++){
        if(!f[i]){*ps = i; ps++;}
        for(int j=0; i*p[j] < 31630; j++){
            f[i*p[j]] = true;
            if(i % p[j] == 0) break;
        }
    }
}

void fac(int in, int x){
    for(short *pi = p; pi < ps && x > 1; pi++){
        while(x % *pi == 0){
            x /= *pi;
            group[in].push_back(*pi);
        }
    }
    if(x > 1) group[in].push_back(x);
}

然後就是直接用bipartite graph的算法了...

我是用最簡單的augmenting path algorithm, 用adjancency list的話是O(VE)
這個分析有點難...editorial的分析也有人提出了...其實應該也是超時的...不知怎的還是過了..

關於augmenting path 或bipartite matching的算法以及題目, 下篇再說吧...

總之這題做到是很開心吧....學到東西又不算太易...至少對我來說不算很易=.=