BZOJ掛了....明天就要出發去GDKOI了....不能棄療. 于是在cf水了幾道題, 寫寫詳(jian)細(dan)題解, 攢攢RP, 希望GDKOI能好好發揮.......?

?

620E. New Year Tree

題目大意:

N個結點的樹, 結點1為根, 要支持2種操作(M個操作):

1.將以v為根的子樹所有節點的顏色為c

2.詢問以v為根的子樹中不同顏色個數

N,M<=4*10^5, 1<=c<=60

題解:

處理出dfs序, 線段樹維護.

1,2操作都對應線段樹的一段區間(子樹在dfs序中連續), 線段樹結點壓位記錄當前區間的結點包含哪些顏色.

時間復雜度O(M log N * max(c))

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;typedef long long ll;const int maxn = 400009;int N, Q, c[maxn]; int Id[maxn], Left[maxn], Right[maxn], dfn;struct edge {int t;edge* n; } E[maxn << 1], *Pt = E, *H[maxn];inline void AddEdge(int u, int v) {Pt->t = v, Pt->n = H[u], H[u] = Pt++; }void DFS(int x, int fa = -1) {Id[++dfn] = x;Left[x] = dfn;for(edge* e = H[x]; e; e = e->n)if(e->t != fa) DFS(e->t, x);Right[x] = dfn; }struct Node {Node *lc, *rc;ll v;int mk;inline void pd() {if(~mk) {lc->mk = mk;rc->mk = mk;v = 1LL << mk;mk = -1;}}inline void upd() {if(lc && rc)v = lc->v | rc->v;if(~mk)v = 1LL << mk;} } pool[maxn << 1], *pt = pool, *Root;int L, R, Val;void Build(Node* t, int l, int r) {int m = (l + r) >> 1;t->mk = -1;if(l != r) {Build(t->lc = pt++, l, m);Build(t->rc = pt++, m + 1, r);t->upd();} elset->v = 1LL << c[Id[m]]; }void Modify(Node* t, int l, int r) {if(L <= l && r <= R) {t->mk = Val;} else {int m = (l + r) >> 1;t->pd();L <= m ? Modify(t->lc, l, m) : t->lc->upd();m < R ? Modify(t->rc, m + 1, r) : t->rc->upd();}t->upd(); }ll Query(Node* t, int l, int r) {if(L <= l && r <= R) return t->v;int m = (l + r) >> 1;t->pd();t->lc->upd(), t->rc->upd();return (L <= m ? Query(t->lc, l, m) : 0) | (m < R ? Query(t->rc, m + 1, r) : 0); }int calc(ll n) {int ret = 0;for(; n; n -= n & -n) ret++;return ret; }void Work() {DFS(dfn = 0);Build(Root = pt++, 1, N);int t, x;while(Q--) {scanf("%d%d", &t, &x), x--;L = Left[x], R = Right[x];if(t == 1) {scanf("%d", &Val), Val--; Modify(Root, 1, N);} elseprintf("%d\n", calc(Query(Root, 1, N)));} }void Init() {int u, v;scanf("%d%d", &N, &Q);for(int i = 0; i < N; i++)scanf("%d", c + i), c[i]--;for(int i = 1; i < N; i++) {scanf("%d%d", &u, &v);u--, v--;AddEdge(u, v);AddEdge(v, u);} }int main() { #ifndef ONLINE_JUDGEfreopen("test.in", "r", stdin);freopen("test.out", "w", stdout); #endifInit();Work();return 0; }

?

609E. Minimum spanning tree for each edge

題目大意:

N個結點, M條無向邊, 第i條邊連接ui, vi, 邊權為wi, 依次輸出包含第i條邊的最小生成樹.

1<=N,M<=2*10^5, 1<=wi<=10^9.

題解:

先跑出任意一個MST(設權值和為tot), 然后建樹.

樹鏈剖分, RMQ維護邊權最大值(不需要線段樹).

對于每條邊ui, vi, wi, 求出ui~vi路徑上的最大邊權maxv, 對于這條邊的答案就是tot - maxv + wi.

時間復雜度O(N log N + M log N)

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;typedef long long ll;const int maxn = 200009;int N, M; ll tot, ans[maxn];struct e {int u, v, w, Id;bool operator < (const e &t) const {return w < t.w;} } Edge[maxn];struct edge {int t, w;edge* n; } E[maxn << 1], *pt = E, *H[maxn];inline void AddEdge(int u, int v, int w) {pt->t = v, pt->w = w, pt->n = H[u], H[u] = pt++; }int par[maxn]; int Find(int x) {return x == par[x] ? x : par[x] = Find(par[x]); }int RMQ[20][maxn], w[maxn]; int top[maxn], fa[maxn], Id[maxn], dep[maxn], sz[maxn], ch[maxn]; int Top, dfn;void dfs(int x) {sz[x] = 1, ch[x] = -1;for(edge* e = H[x]; e; e = e->n) if(e->t != fa[x]) {dep[e->t] = dep[x] + 1;fa[e->t] = x;w[e->t] = e->w;dfs(e->t);sz[x] += sz[e->t];if(!~ch[x] || sz[ch[x]] < sz[e->t])ch[x] = e->t;} }void DFS(int x) {top[x] = Top;Id[x] = dfn++;if(~ch[x]) DFS(ch[x]);for(edge* e = H[x]; e; e = e->n)if(e->t != fa[x] && e->t != ch[x]) DFS(Top = e->t); }void Init_Query() {for(int i = 0; i < N; i++)RMQ[0][Id[i]] = w[i];for(int i = 1; (1 << i) <= N; i++)for(int j = 0; j + (1 << i) <= N; j++)RMQ[i][j] = max(RMQ[i - 1][j], RMQ[i - 1][j + (1 << (i - 1))]); }int Qmax(int l, int r) {int Log = log2(r - l + 1);return max(RMQ[Log][l], RMQ[Log][r - (1 << Log) + 1]); }int Query(int x, int y) {int ret = 0;for(; top[x] != top[y]; x = fa[top[x]]) {if(dep[top[x]] < dep[top[y]]) swap(x, y);ret = max(ret, Qmax(Id[top[x]], Id[x]));}if(x == y) return ret;if(dep[x] < dep[y]) swap(x, y);return max(ret, Qmax(Id[y] + 1, Id[x])); }void Work() {tot = 0;sort(Edge, Edge + M);for(int i = 0; i < N; i++) par[i] = i;for(int i = 0; i < M; i++) {int u = Find(Edge[i].u), v = Find(Edge[i].v);if(u != v) {par[u] = v;tot += Edge[i].w;AddEdge(Edge[i].u, Edge[i].v, Edge[i].w);AddEdge(Edge[i].v, Edge[i].u, Edge[i].w);Edge[i].Id += M;}}fa[0] = -1, w[0] = dep[0] = 0;dfs(0);DFS(Top = dfn = 0);Init_Query();for(int i = 0; i < M; i++) if(Edge[i].Id < M) {ans[Edge[i].Id] = tot - Query(Edge[i].u, Edge[i].v) + Edge[i].w;}elseans[Edge[i].Id - M] = tot;for(int i = 0; i < M; i++)cout << ans[i] << "\n"; }void Init() {scanf("%d%d", &N, &M);for(int i = 0; i < M; i++) {scanf("%d%d%d", &Edge[i].u, &Edge[i].v, &Edge[i].w);Edge[i].u--, Edge[i].v--;Edge[i].Id = i;} }int main() {Init();Work();return 0; }

　　

600D. Area of Two Circles' Intersection

題目大意:

給2個圓, 求它們交的面積.

-10^9<=x,y<=10^9, 1<=r<=10^9

題解:

模板題.

先判掉相離和相切的情況, 然后利用余弦定理與扇形和三角形面積公式解決.

時間復雜度O(1)

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm>using namespace std;typedef long double ld;void Work() {int x0, x1, y0, y1, r0, r1;scanf("%d%d%d%d%d%d", &x0, &y0, &r0, &x1, &y1, &r1);ld d = sqrt((ld) (x0 - x1) * (x0 - x1) + (ld) (y0 - y1) * (y0 - y1));if(r0 + r1 <= d) {puts("0");return;}if(abs(r0 - r1) >= d) {printf("%.10lf\n", (double) ld(acos(-1.0)) * min(r0, r1) * min(r0, r1));return;}ld a0 = acos((ld(r0) * r0 + ld(d) * d - ld(r1) * r1) / (d * r0 * 2)); // angle_0ld a1 = acos((ld(r1) * r1 + ld(d) * d - ld(r0) * r0) / (d * r1 * 2)); // angle_1printf("%.10lf\n", (double) (ld(r0) * r0 * (a0 - sin(a0) * cos(a0)) + ld(r1) * r1 * (a1 - sin(a1) * cos(a1)))); }int main() {Work();return 0; }

　

592D. Super M

題目大意:

給棵N個結點的樹, 你需要走到其中的M個點, 起始位置任選. 求M個點全都走過的最短路徑, 多種方案則選擇起始位置的結點字典序小的.

1<=m<=n<=123456

題解:

去掉一些沒用的結點與邊, 使得保留下來的樹的葉子結點全部為需要到達的點.

記留下來的邊總長為x, 起點與終點距離為y, 通過觀察(?)可以發現答案為2*x-y(畫個圖感受一下, 易證).

所以要最大化y.那么就是在新樹中找出1條直徑, 并且某一端點字典序最小(多條直徑時).

對于樹的直徑, 可以使用經典的BFS/DFS做法.

時間復雜度O(N)

#include<cstdio> #include<cstring> #include<algorithm>using namespace std;const int maxn = 123460;int n, m; bool F[maxn];struct edge {int t, f;edge* n; } E[maxn << 1], *pt = E, *H[maxn];inline void AddEdge(int u, int v) {pt->t = v, pt->f = 1, pt->n = H[u], H[u] = pt++; }int X, Y, d[maxn], ans;void dfs(int x, int fa) {d[x] = F[x];for(edge* e = H[x]; e; e = e->n) if(e->t != fa) {dfs(e->t, x);if(!d[e->t]) {e->f = 0;} elsed[x] += d[e->t];} }void dfs(int x, int dist, int fa) {d[x] = dist;for(edge* e = H[x]; e; e = e->n)if(e->f && e->t != fa) dfs(e->t, dist + 1, x); }void calc(int x, int fa = -1) {for(edge* e = H[x]; e; e = e->n)if(e->f && e->t != fa) calc(e->t, x), ans += 2; }void Work() {int mx, Id;for(int i = 0; i < n; i++) if(F[i]) {dfs(i, -1);break;}for(int i = 0; i < n; i++) if(F[i]) {dfs(i, 0, -1);break;}mx = 0;for(int i = 0; i < n; i++) if(F[i]) {mx = max(mx, d[i]);if(mx == d[i]) X = i;}dfs(X, 0, -1);mx = 0;for(int i = 0; i < n; i++) if(F[i]) {mx = max(mx, d[i]);if(mx == d[i]) Y = i;}ans = -d[Y], Id = min(X, Y);for(int i = 0; i < n; i++)if(F[i] && d[i] == mx) Id = min(Id, i);dfs(Y, 0, -1);for(int i = 0; i < n; i++)if(F[i] && d[i] == mx) Id = min(Id, i);calc(Y);printf("%d\n%d\n", ++Id, ans); }void Init() {scanf("%d%d", &n, &m);int u, v;for(int i = 1; i < n; i++) {scanf("%d%d", &u, &v);u--, v--;AddEdge(u, v);AddEdge(v, u);}memset(F, 0, sizeof F);for(int i = 0; i < m; i++) {scanf("%d", &v);F[--v] = true;} }int main() {Init();Work();return 0; }

?

596D. Wilbur and Trees

題目大意:

1條線上有N棵位置為xi,高為H的樹. 要把它們全部砍下來, 每次隨機選擇最左邊或者最右邊的樹砍下來. 每棵樹倒向左邊的概率為p, 假如2棵樹之間的距離嚴格小于H, 那么1棵樹向另一棵樹方向倒會撞倒另1棵樹, 求最后樹覆蓋線的期望長度. 1<=N<=2000, 1<=H<=10^8, -10^8<=xi<=10^8, 0<=p<=1

題解:

期望dp. 先對樹的位置排序.

dp(l, r, ls, rs)表示第l~r棵樹沒倒, ls,rs分別是第l-1棵樹和第r+1棵樹的倒向(0左1右).

枚舉第l棵樹倒下或者第r棵樹倒下(概率均為0.5), 再枚舉倒下的方向(概率:左邊p, 右邊(1-p)), 以此來狀態轉移.

時間復雜度O(N^2)

#include<cstdio> #include<cassert> #include<cstring> #include<algorithm>using namespace std;const int maxn = 2009;bool vis[maxn][maxn][2][2]; double dp[maxn][maxn][2][2], p; int N, H, x[maxn], L[maxn], R[maxn];double Dp(int l, int r, int ls,int rs) {if(l > r) return 0;double &t = dp[l][r][ls][rs];if(vis[l][r][ls][rs]) return t;vis[l][r][ls][rs] = true;int _l = x[l - 1] + (ls ? H : 0), _L = max(l, L[r]);int _r = x[r + 1] - (rs ? 0 : H), _R = min(r, R[l]);t = p * (min(x[l] - _l, H) + Dp(l + 1, r, 0, rs)) // left -> left+ (1 - p) * (min(_r - x[r], H) + Dp(l, r - 1, ls, 1)); // right -> rightt += (1 - p) * (x[_R] - x[l] + min(_r - x[_R], H) + Dp(_R + 1, r, 1, rs)) // left -> right+ p * (x[r] - x[_L] + min(x[_L] - _l, H) + Dp(l, _L - 1, ls, 0)); // right -> leftreturn t *= 0.5; }void Init() {scanf("%d%d%lf", &N, &H, &p);x[0] = -500000000;x[N + 1] = 500000000;for(int i = 1; i <= N; i++) scanf("%d", x + i);sort(x + 1, x + N + 1);memset(vis, 0, sizeof vis);L[0] = 1;for(int i = 1; i <= N; i++)L[i] = (x[i - 1] + H > x[i] ? L[i - 1] : i);R[N + 1] = N;for(int i = N; i >= 1; i--)R[i] = (x[i] + H > x[i + 1] ? R[i + 1] : i); }int main() {Init();printf("%.10lf\n", Dp(1, N, 0, 1));return 0; }

?

寫完啦~~

轉載于:https://www.cnblogs.com/JSZX11556/p/5199528.html

總結

以上是生活随笔為你收集整理的codeforces 几道题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。