2013年1月29日 星期二

Codeforces 258B Little Elephant and Election 4/10

非常經典的一個題目

重點在他的第一個部分:

給一個  有N位 的數字 M,問1~M
有1個4 or 7的有幾個
有2個4 or 7的有幾個
有3個4 or 7的有幾個

這樣。

比較好的作法應該是

從最高位開始,從那位以前都一樣
但枚舉那一位的大小(小於原本的值)
再去枚舉剩下的位置有幾個4
最後再用nCm去計算~

這樣編程複雜度低,時間複雜度也很低

scanf("%d", &m), m++, cnt[0]--;
while(m) a[++n] = m % 10, m /= 10;
for (int i = 0; i <= 15; i++)
    for (int j = 0; j <= i; j++)
        C[i][j] = i && j? (C[i-1][j-1]+C[i-1][j]) % M: 1;
for (int i = n; i; i--){
    for (int j = 0; j < a[i]; j++){
        LL now = 1LL << i-1;
        for (int k = i-1; k >= 0; k--){
            cnt[prv+(j == 4 || j == 7)+k] += now * C[i-1][k];
            now *= 8/2;
        }
    }
    prv += (a[i] == 4 || a[i] == 7);
}

2013年1月27日 星期日

小小幾何筆記


先講幾個常用的函數好惹(都在cmath中)

fabs(double) -> 把浮點數取絕對值
fmod(double, double) -> 就是浮點數間的mod
modf(double, double*) -> 將一個浮點數拆成整跟浮
< X的小數部分=modf(X,X的整數部分) >

這些都很簡單,但可以記一記,coding時比較俐落

我們常常都會需要把笛卡爾座標,轉換成極座標

但我每次都沒有什麼好作法,現在發現了不錯的函數

atan2(double y, double x)

得出來的是弧度表示法,而且是從 -180~180 這樣

用的時候要注意!!!

若想轉成度數表示法的話,有一個很棒的常數叫:

M_PI = 3.1415926

極推薦~

2013年1月25日 星期五

SGU 185 Two shortest 5/10

就是隨便弄,但他有卡記憶體

所以你先弄個dijkstra,把邊刪一刪

順便就把題目變成了最大流

流一流,然後再做兩次遍歷就結束了

重點就是不要用vector,容易MLE!

隨便開個陣列就好了。

因為他的N小小的,所以O(N^2)沒差

//By momo
#include
#include
#include
#include

#define N 410
#define INF 9000000
#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, vst[N], dis[N], tbl[N][N], che[N][N];
bool dfs(int p){
    vst[p] = 1; if(p == n) return 1;
    for(int i = 1; i <= n; i++)
        if(!vst[i] && tbl[p][i] && dfs(i))
            return tbl[p][i] = 0, tbl[i][p] = 1, 1;
    return 0;
}

bool print(int p){
    if(p == n) return printf("%d\n", p), 1;
    printf("%d ", p);
    for(int i = 1; i <= n; i++)
        if(!tbl[p][i] && che[p][i] && print(i))
            return che[p][i] = 0, 1;
    return 0;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            tbl[i][j] = INF;
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        tbl[a][b] = tbl[b][a] = c;
    }
    fill(vst, vst+n+1, 0);
    fill(dis, dis+n+1, INF); dis[1] = 0;
    while(1){
        int mn = INF, x = 0;
        for(int i = 1; i <= n; i++)
            if(mn > dis[i] && !vst[i]) mn = dis[i], x = i;
        if(mn == INF) break; vst[x] = 1;
        for(int i = 1; i <= n; i++)
            dis[i] = min(dis[x]+tbl[i][x], dis[i]);
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
        tbl[i][j] = che[i][j] =
        (tbl[i][j] != INF && dis[i]+tbl[i][j] == dis[j]);
    for(int i = 0; i < 2; i++){
        fill(vst, vst+n+1, 0);
        if(dfs(1) == 0) return puts("No solution"), 0;
    }
    print(1); print(1);
}

SGU 198 Get Out! 6/10

好玩的題目

首先,把你的圓形船變成點,其他人膨脹(+sr)

接著如果兩個圓相交,就連一條線

如果你被包在一個封閉多邊形,你就出不去了

這邊有一個很有趣的性質:

線相交所產生的點圍出的環可以由這些島圍出更大的
(你就假設有個點,他可以把別人圍起來,弄一弄就發現可以用那些島的點圍起來)

有了這個特性,你只要判斷島點圍出的還即可(N個)

接下來,你先隨機弄一個射線(判斷是否在內)

看跟誰交在一起,接著你就用dfs走過這些點一遍

如果有back edge,你就判斷有沒有被關起來這樣

可以知道這樣就可以了,不需要去判斷所有的環
(因為要不是會重複,就是可以用已判斷過的環去組出來,所以完全不影響結果)

//By momo
#include
#include
#include
#include
#define N 310
#define EPS 1e-8
#define FOR(it, c) for(typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

vector<int> G[N];
int n, dfn[N], ttl[N], tbl[N][N], fl = 1;

struct cord{
    double x, y, r;
}s, e, t[N];

double tx[N], ty[N], tr[N];
double sq(double d){ return d*d; }
double dis(int a, int b){
    return sqrt(sq(t[a].x-t[b].x)+sq(t[a].y-t[b].y));
}
double crs(cord a, cord b, cord c){
    double vx = a.x-c.x, vy = a.y-c.y;
    double ux = b.x-c.x, uy = b.y-c.y;
    return vx * uy - ux * vy;
}
bool hit(int a, int b){
    if(crs(t[b], s, t[a]) * crs(t[b], e, t[a]) < EPS
    && crs(   s, t[a], e) * crs(   s, t[b], e) < EPS) return 1;
    return 0;
}

void dfs(int p, int f, int l, int sum){
    dfn[p] = l; ttl[p] = sum;
    FOR(it, G[p]){
        if(*it == f) continue;
        if(dfn[*it] == -1) dfs(*it, p, l+1, sum+tbl[p][*it]);
        else if(dfn[*it] < dfn[p]){
            int cnt = sum - ttl[*it] + tbl[*it][p];
            if(cnt % 2) fl = 0;
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%lf%lf%lf", &t[i].x, &t[i].y, &t[i].r);
    scanf("%lf%lf%lf", &s.x, &s.y, &s.r);
    e.x = 214748364.3654427, e.y = -12923.1793283;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(dis(i, j)+EPS < t[i].r + t[j].r + 2*s.r){
                G[i].push_back(j);
                G[j].push_back(i);
                tbl[i][j] = tbl[j][i] = hit(i, j);
            }
        }
    }
    fill(dfn, dfn+n, -1);
    for(int i = 0; i < n; i++)
        if(dfn[i] == -1) dfs(i, -1, 0, 0);
    puts(fl?"YES":"NO");
}

SGU 192 RGB 6/10

只能用兩個字來形容:『麻煩』
但我越來越喜歡計算幾何搭配其他演算法的題目了

所以要想一個簡單的寫法是很重要的
一開始寫了一個很爛的方法,觀看了他人的作法後發現:

其實我們可以對每一條線段,枚舉每個其他線段遮住該線段的位置

『注意!我原本用的是沒被遮住的,但這樣一個線段就會產生多個線段,不好實現』

因為是遮住,你會發現每一個線段只會產生一條,很容易實現
可是這樣的話就會出現遮住的有重疊的情形,這時先sort,然後用很simple的greedy解決即可

而且找重疊的部份實在很簡單,min, max一下即可

O(n^2lgn)

//By momo
#include
#include
#define N 310
#define EPS 1e-7
using namespace std;

double fabs(double x){ return x<0?-x:x; }
bool same(double a, double b){ return a <= b+EPS && a+EPS >= b; }

struct cord{ double x, y; }S[N];
struct segm{ cord s, e; double m, b; int c; }L[N];
bool comp(cord a, cord b){ return a.x < b.x; }

int n;
void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i){
        char s[3];
        scanf("%lf%lf%lf%lf%s", &L[i].s.x, &L[i].s.y, &L[i].e.x, &L[i].e.y, s);
        if(same(L[i].s.x, L[i].e.x)){ --i, --n; continue; }
        L[i].c = (s[0] == 'R'? 0: (s[0] == 'G'? 1: 2));
        if(L[i].s.x > L[i].e.x) swap(L[i].s, L[i].e);
        L[i].m = (L[i].e.y - L[i].s.y) / (L[i].e.x - L[i].s.x);
        L[i].b = L[i].s.y - (L[i].m * L[i].s.x);
    }
}

void solve(){
    static double ans[4];
    for(int i = 0; i < n; i++){
        cord s, e; double sy2, ey2, tot = L[i].e.x-L[i].s.x; int cnt = 0;
        for(int j = 0; j < n; j++) if(i != j){
            s.x = max(L[i].s.x, L[j].s.x), e.x = min(L[i].e.x, L[j].e.x);
            s.y = s.x * L[i].m + L[i].b, sy2 = s.x * L[j].m + L[j].b;
            e.y = e.x * L[i].m + L[i].b, ey2 = e.x * L[j].m + L[j].b;
            if(s.x+EPS >= e.x || same(s.x, e.x)) continue;
            if(sy2+EPS >= s.y && ey2+EPS >= e.y) continue;
            if(s.y+EPS >= sy2 && e.y+EPS >= ey2) S[cnt].x = s.x, S[cnt++].y = e.x;
            else{
                bool v = (s.y+EPS >= sy2);
                double mid = (L[j].b-L[i].b) / (L[i].m-L[j].m);
                S[cnt].x = v?s.x:mid, S[cnt++].y = v?mid:e.x;
            }
        }
        sort(S, S+cnt, comp);
        if(cnt == 0){ ans[L[i].c] += tot; continue; }
        double stt = S[0].x, end = S[0].y;
        for(int j = 1; j < cnt; j++){
            if(end < S[j].x+EPS){
                tot -= end-stt;
                stt = S[j].x;
            }
            end = max(end, S[j].y);
        }ans[L[i].c] += tot-end+stt;
    }
    printf("R %.2lf\nG %.2lf\nB %.2lf\n", ans[0], ans[1], ans[2]);
}

int main(){ input(); solve(); }

SGU 190 Dominoes 4/10

先看看這個題目:

試證明想要在一個N*N但是對角的兩格不見了的棋盤
用2*1的塊體完整覆蓋是不可能的。

像這樣
OOX
OOO
XOO

首先N是奇數很簡單,但N是偶數怎麼辦呢?
其實你知道一個2*1的塊體一定會覆蓋到黑色跟白色(想想棋盤)
而黑色跟白色數目不等,所以當然不可能囉!

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

根據上題的概念,就可以發現這題很簡單

但仍然是一題有趣的題目

很明顯就是要做配對,而且要是完全配對

因為他是二分圖,所以弄一弄就解決囉~

//By momo
#include
#include
#include
#include

#define N 45
#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;

vector<int> G[N*N], ans1, ans2;
int n, m, tbl[N][N], mch[N*N], vst[N*N];
void add_edge(int a, int b){ G[a].PB(b), G[b].PB(a); }

void Input(){
    scanf("%d%d", &n, &m);
    for(int i = 0, x, y; i < m; i++){
        scanf("%d%d", &x, &y);
        tbl[x-1][y-1] = 1;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0, x, y; j < n; j++){
            if(tbl[i][j]) continue;
            x = i+0, y = j+1;
            if(x < n && y < n && !tbl[x][y]) add_edge(i*n+j, x*n+y);
            x = i+1, y = j+0;
            if(x < n && y < n && !tbl[x][y]) add_edge(i*n+j, x*n+y);
        }
    }
}

bool Bi(int p){
    vst[p] = 1;
    FOR(it, G[p]){
        int w = mch[*it];
        if(w == -1 || !vst[w] && Bi(w)){
            mch[*it] = p;
            return 1;
        }
    }
    return 0;
}

void make(int i, int j){
    int x  = i/n, y  = i%n;
    int xx = j/n, yy = j%n;
    if(x+y > xx+yy) swap(x, xx), swap(y, yy);
    if(x < xx) ans1.PB(x*n+y);
    else ans2.PB(x*n+y);
}

void Solve(){
    int cnt = 0;
    memset(mch, -1, sizeof(mch));
    if((n*n - m) % 2){ puts("No"); return; }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        if(tbl[i][j] || (i+j) % 2 == 0) continue;
        memset(vst, 0, sizeof(vst)); if(Bi(i*n+j)) cnt++;
    }
    if(cnt != (n*n - m) / 2){ puts("No"); return; }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        if(tbl[i][j] || (i+j) % 2 == 1) continue;
        int x = mch[i*n+j]; make(i*n+j, x);
    }
    puts("Yes");
    printf("%d\n", SZ(ans1));
    for(int i = 0; i < SZ(ans1); i++)
        printf("%d %d\n", ans1[i]/n+1, ans1[i]%n+1);
    printf("%d\n", SZ(ans2));
    for(int i = 0; i < SZ(ans2); i++)
        printf("%d %d\n", ans2[i]/n+1, ans2[i]%n+1);
}

int main(){
    Input();
    Solve();
}

SGU 187 Twist and whirl -- want to cheat 6/10

這題挺特別的

因為網路上都說要用Splay Tree

但是其實可以用奇怪的離散化

就是他有很多段都是連續的
(因為相較於 n,m 實在很小)

所以可以直接用這個特性,把他拆成一段一段

一次操作頂多拆出兩段,最多O(m)個

且每次操作是掃過所有的塊體O(m)

所以可以在O(m^2)的時間內完成

但若 m 太大就G掉了

//By momo
#include
#include
#include
#define N 4010
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

int n, m, ans[130010];
struct segm{
    int s, e, c;
    segm(){}
    segm(int _s, int _e, int _c){
        s = _s, e = _e, c = _c;
    }
};
list<segm> ls, tp;

void Cut(int x){
    list<segm>::iterator p = ls.begin();
    for(int st = 1; p != ls.end(); p++){
        int en = st + p->e - p->s;
        if(st <= x && x <= en){
            if(p->c){
                int md = p->s + x-st;
                ls.insert(p, segm(p->s, md, 1));
                if(x < en) ls.insert(p, segm(md+1, p->e, 1));
                ls.erase(p);
            }
            else{
                int md = p->e - x+st;
                ls.insert(p, segm(md, p->e, 0));
                if(x < en) ls.insert(p, segm(p->s, md-1, 0));
                ls.erase(p);
            }
            break;
        }
        st = en+1;
    }
}

void Output(){
    list<segm>::iterator p = ls.begin();
    for(int st = 1; p != ls.end(); p++){
        int en = st + p->e - p->s;
        for(int i = st; i <= en; i++){
            if(p->c) ans[i] = p->s + (i-st);
            else ans[i] = p->e - (i-st);
        }
        st = en+1;
    }
    for(int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n?'\n':' ');
}

int main(){
    scanf("%d%d", &n, &m);
    ls.push_back(segm(1, n, 1));
    for(int i = 0; i < m; i++){
        int rl, rr;
        scanf("%d%d", &rl, &rr);
        list<segm>::iterator p, x, y, t;

        Cut(rl-1);
        Cut(rr);

        p = ls.begin();
        for(int st = 1, fir = 1; p != ls.end(); p++){
            int en = st + p->e - p->s;
            if(rl <= st && en <= rr){
                if(fir) x = p, fir = 0;
                y = p;
            }
            st = en+1;
        }

        t = x; t--; y++;
        tp.splice(tp.begin(), ls, x, y);
        t++;

        tp.reverse();
        FOR(it, tp) it->c ^= 1;
        ls.splice(t, tp); tp.clear();
    }
    Output();
}