2014 ACM/ICPC Asia Beijing Regional Contest Onsite


http://acmicpc.info/archives/1850

Problem D. Dire Wolf

Brief description:

略)

Analysis:

正難則反。)
http://acm.hust.edu.cn/vjudge/contest/viewSource.action?id=3048048

Problem E. Everlasting L

Brief description:

略)

Analysis:

注意到坐標範圍較小。。可以掃描線 + 枚舉。

預處理:
D[d][n]: <= n 且與 d 互質的數有多少個。。。 up,rt:向上和向右最遠可以延伸的距離。。 從左向右掃描線。。。O(n3) 大枚舉。。。分三類討論。 (1. 再左邊且不可能與之相交。。 (2. 再左邊且與之相交。。 (3. 同一列。。 其中 2 和 3 可以放在一起處理。。。總複雜度 $$O(n3)$$ [cpp] //}/* .................................................................................................................................. */ const int N = int(2e2) + 9; int A[N][N], up[N][N], rt[N][N]; int D[N][N]; VII E[N]; int C[N]; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // <= 2 ... 1 FOR(i, 1, N){ FOR(j, 1, N){ D[i][j] = D[i][j-1] + (gcd(i, j) == 1); } } Rush{ RST(A); FLC(up, rt, -1); Rush{int x, y; RD(x, y); A[x][y] = 1;} DWN(i, N-1, 0){ DWN(j, N-1, 0){ rt[i][j] = A[i][j] ? rt[i][j+1] + 1 : -1; up[i][j] = A[i][j] ? up[i+1][j] + 1 : -1; } } RST(C); REP(j, N) E[j].clear(); LL z = 0, pre = 0; REP(j, N){ ECH(it, E[j]) C[it->fi] -= it->se; DWN(i, N, 0){ LL ex = C[i]; REP_1(uu, up[i][j]){ ex += C[i+uu]; int d = D[uu][rt[i][j]]; z += (pre-ex)*d; C[i] += d, pre += d; ex += d; } REP_1(rr, rt[i][j]) E[j+rr+1].PB(MP(i, D[rr][up[i][j]])); } } OT(z*2); } } [/cpp]