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.