2013年2月28日 星期四

Codeforces 198 C. Delivering Carcinogen

Codeforces 的題目還蠻有品質保證的

很不錯的幾何題。不知道怎麼做就,二分搜

假設答案是 t 秒,那麼 > t 秒的都可以(先走到跟他一樣,而且V > Vp),利用這個性質來二分搜。

所以現在那個一直在繞圈圈的行星,被我們固定住

你只要找到所在位置與該行星的最短距,就解決了

直線永遠是最短距離,所以假如你不會穿越中間的圓圈,就直接拿他們的直線距離。

假設有穿越中間的圓圈,可以知道走切線再走圓弧再走切線,會是最短距離,

所以把他們一一算出來之後,就成功了。

=======================================

子問題-

1. 判斷有沒有穿越中間:直線與中心的距離 <= r 且OAB和OBA都是銳角

2. 直線與中心的距離:算外積後(平行四邊形面積),再除掉底 = 高 

3. 判斷兩個向量是否形成銳角:內積後,正的為銳角,負的為鈍角

4. 切線的長度:OA^2 - R^2

5. 圓弧的角度:設切點是C, D,設高是M,
若BOA是銳角: (BOM-BOD-AOC),若BOA是鈍角: (180 - BOM - BOD - AOC)

Codeforces 198E. Gripping Story

線段樹的變形真的很經典

這題要做的就是我們希望可以把 距離 <=  r 的區段

重量都小於等於力量的物質挑出來,放入queue裡

每一個物質都有兩個變量,距離以及重量

要對 <= 某距離內,找出 <= 某重量 的物質

這時,我們要用到一個很基本的概念:區段樹

就是一個線段樹,但是他的每一個節點,不是單單包含一個值

而是包含了這個區段的所有元素!

這麼看的話,感覺還挺崩潰的,但是可以知道每個元素只會被lgn個包含

所以元素數量是 NlgN ,非常的好用

有了這個方向之後,是否就很簡單了呢?答案是:Yes

只要讓那個區段的值都是由小排到大的,之後在query時

就從前面開始取出即可

(我是用Set去讓他由小到大的,整體複雜度nlg^2n,但只要質量小的放到質量大的,就可以用nlgn的時間,解出來了

想要看code,可以直接去codeforces,上面找。

2013年2月8日 星期五

Codeforces 266D BerDonalds

奇怪的題目名字,應該是學 Mcdonalds 的吧

如果他說只能在點上,就好辦了

直接做一次Floyd,就可以得到答案了

但!問題就在於你可以位於其中的無限多個點的其中一個

前面都很無腦,接下來就需要用到好腦袋惹~
(要了解很簡單,但要想到有點難==)

===================================

其實可以這樣想,先想對於一個邊你要到所有人的最短距離

就是,這邊的兩端為 a, b,min( x + dis[ a ][ i ], c - x + dis[ b ][ i ] )對所有 i 的max要最小

直接做枚舉可能答案的動作,是最簡單也是最方便的(比起二分搜或三分搜)

所以就先朝著枚舉答案的方向思考(也就是哪些中間點要試放看看這樣)

假設所有點的集合是這樣(a, b, c, d, e...),將他分成兩個集合A, B

A代表要讓這個邊的 a 去連會是min, B代表要讓這個邊的 b 去連會是min

也就是我們假定對A集合min(剛剛那團) 會是 a 的比較小,B也是同樣的道理

而若是這麼一回事的話,拿A的最大值,B的最大值,就可以組出想要的 x 了。

枚舉A的最大值,然後求B(補集)的最大值,弄出所有可能的X,再取最小的即可。

//By momo
#include
#include
#include
#define N 210
#define INF 999999999
using namespace std;

double ans = INF;
int n, m, dis[N][N];
int a[N*N], b[N*N], c[N*N];
struct pairr{ int a, b; }d[N];
bool comp(pairr x, pairr y){ return x.a > y.a; }

int main (){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) dis[i][j] = INF;
        dis[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        a[i]--, b[i]--;
        dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
    }
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j],
                            dis[i][k] + dis[k][j]);
    for(int i = 0; i < m; i++){
        int C = c[i];
        for(int j = 0; j < n; j++){
            d[j].a = dis[a[i]][j];
            d[j].b = dis[b[i]][j];
        }
        sort(d, d+n, comp);
        int M = d[0].b; ans = min(ans, 1.0*d[0].a);
        for(int j = 1; j < n; j++){
            double val;
            if(d[j].a > M - C && M + C > d[j].a)
                val = (d[j].a+M+C) / 2.0;
            else val = max(d[j].a, M);
            ans = min(ans, val);
            M = max(M, d[j].b);
        }
    }
    printf("%lf\n", ans);
}

2013年2月5日 星期二

SGU 219 Synchrograph 6/10

想了一想,一個有>0值的環,或一個沒有入度的都可以不斷不斷的燃燒

環是可以循環燃燒,沒有入度的則可以無限燃燒

唯一會燒不起來的好像就是全部都是0的環所以就用0邊做出新的圖,用SCC判斷一下誰不能燒

而且如果有一個人的上游是無法亂燒的,那他就也不能亂燒(也就是所謂的alive)所以要再DFS一下,他的下游是誰

我想到一個比較好的解釋方式:
1. 對零的邊的SCC縮點,縮起來的那個點代表他無法燃燒
2. 因為他沒辦法燃燒,所以他下游的點也都不能燃燒
3. 但假設你把1,2,所說的點去除掉之後,剩下的點再做縮點,(因為環可以不斷的循環,所以可以視為是一個點)
4. 最後變成了DAG,一定存在一個無入度點,他可以無限燃燒,所以剩下的那些點,都是alive的。

//By momo
#include
#include
#include
#define N 1010
#define PB push_back
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

int n, m, hit[N], cnt, vst[N];
vector<int> G[N], rG[N], tG[N], scc[N];
void dfs(int p){
    vst[p] = 1;
    FOR(it, G[p])
        if(!vst[*it]) dfs(*it);
    hit[cnt++] = p;
}
void rdfs(int p){
    vst[p] = 1;
    FOR(it, rG[p])
        if(!vst[*it]) rdfs(*it);
    scc[cnt].PB(p);
}
void kosaraju(){
    cnt = 0; fill(vst, vst + n, 0);
    for(int i = 0; i < n; i++)
        if(!vst[i]) dfs(i);
    cnt = 0; fill(vst, vst + n, 0);
    for(int i = n-1; i >= 0; i--)
        if(!vst[hit[i]]) rdfs(hit[i]), cnt++;
}

int dead[N];
void ddfs(int p){
    vst[p] = 1;
    FOR(it, tG[p])
        if(!vst[*it]) ddfs(*it);
    dead[p] = 1;
}

int main (){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++){
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        a--, b--; if(c == 0) G[a].PB(b), rG[b].PB(a);
        if(a == b && c == 0) dead[a] = 1; tG[a].PB(b);
    }
    kosaraju();
    for(int i = 0; i < cnt; i++){
        if(SZ(scc[i]) == 1) continue;
        FOR(it, scc[i]) dead[*it] = 1;
    }
    fill(vst, vst+n, 0);
    for(int i = 0; i < n; i++)
        if(!vst[i] && dead[i]) ddfs(i);
    for(int i = 0; i < n; i++)
        printf("%d\n", 1 - dead[i]);
}

2013年2月4日 星期一

SGU 213 Strong Defence 6/10

還不錯的題目

先發現:
答案小於等於S-T的最短路長度L
(證明很簡單)

把從最短距X到X-1的設為一組邊集合

這樣總共有L個集合

因為X只能走到X或X-1,所以

這樣是一組合理解!

科科,證完了~

SGU 217 Two Cylinders 5/10


先做出積分式


接下來對其做數值模擬

因為精度的關係,這邊要使用一個稱為

『辛普森公式』的數值模擬方法

選三個點,用二次函數去fit他

接著就去算這曲線的面積,最後把這些東東全部加起來

寫的漂亮一點,可以弄成公式:

dx/3*(y0+4y1+2y2+…+2yn-2+4yn-1+yn)

//By momo
#include
#include
#include
#include
#define N 1000000
using namespace std;

double r1, r2, ans = 0;
double f(double x){
    return 8*sqrt((r1*r1-x*x)*(r2*r2-x*x));
}

int main (){
    scanf("%lf%lf", &r1, &r2);
    if(r1 > r2) swap(r1, r2);
    double dx = r1/N;
    for(int i = 0; i <= N; i++){
        double coe;
        if(i == 0 || i == N) coe = 1;
        else coe = (i&1)?4:2;
        ans += coe*dx*f(dx*i)/3;
    }
    printf("%.4lf\n", ans);
}