一套本该 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);
}

Posted by xiaodao
Category: 日常