某島

… : "…アッカリ~ン . .. . " .. .
May 13, 2014

Codeforces Round #245

一套本該 AK 的大水題。。。做成這樣實在是沒什麼好說的。。。

Problem E. Points and Segments

Brief description:

。。。給定一組 [l, r] 線段,要求對這些線段紅藍染色。
。。使得任意一個點,所覆蓋它的紅藍線段的差不超過 1。

Analysis:

________
  ________
   ________
     ________
       ________ 

。。。大概肯定要對區間離散化。。所以關鍵就是上面這種情況。。。。。一個點被很多個線段覆蓋的情況怎麼處理。。?。
我們把 red 看成 +1.。。blue 看成 -1.。。那麼 red blue 不大於 1 就是。。。那麼一條線段的染色可以看成是兩個相反的前綴操作。
。。。要求任何前綴 abs(S[ ]) 都保證 <= 1。。又因為操作只有 +1 和 -1 兩種。。。 。。。所以 S[even] = 0。。。因此只需要對。。。所以 2i, 2i+1 連邊跑二分圖染色即可。。 。。因為這種結構總是兩兩成對。。一對在向外連一條邊。。因此總是存在解。。。 [cpp] //}/* .................................................................................................................................. */ const int N = int(2e5) + 9; VI adj[N]; int col[N]; int n; void add_edge(int a, int b){ adj[a].PB(b), adj[b].PB(a); } #define v (*it) void dfs(int u, int c = 0){ col[u] = c; ECH(it, adj[u]) if (!~col[v]) dfs(v, c^1); } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif VII I; REP_C(i, RD(n)){ int l, r; RD(l, r); add_edge(i, i+n); I.PB(MP(l, i)), I.PB(MP(r, i+n)); } SRT(I); REP(i, n) add_edge(I[i*2].se, I[i*2+1].se); FLC(col, -1); REP(i, n) if(!~col[i]) dfs(i); REP(i, n) OT(col[i]); } [/cpp]

Problem D. Tricky Function

Brief description:

。。。略。)

Analysis:

。。。可以當成裸最近點對。。。。無奈網上最近點對錯誤代碼太多。(複雜度或者寫法)。。。。。。
。。。。。。。。敢不敢不這麼坑爹。。!!。。。。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
VP P; int n;

bool cmpy(cPo a, cPo b){return a.y < b.y;}

inline DB cp(VP &P, int l, int r){
    if (l >= r) return OO;

    int m = (l + r) >> 1; DB d = min(cp(P, l, m), cp(P, m+1, r)), mx = P[m].x;
    inplace_merge(P.begin()+l, P.begin()+m+1, P.begin()+r+1, cmpy);

    VP t; FOR_1(i, l, r) if (sgn(abs(P[i].x - mx), d)<0) t.PB(P[i]);
    REP(i, SZ(t)) FOR(j, i+1,  min(SZ(t), i+9)) checkMin(d, dist2(t[i], t[j])); //#
    return d;
}

DB cp(VP& P){
    SRT(P); return cp(P, 0, n-1);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    DB pre = 0; REP_C(i, RD(n)) P.PB(Po(i, pre += RDD()));
    printf("%.0f\n" , cp(P)+EPS);
}