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));
        }
    }
}

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

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一次，找出最小圈輸出