Educational Codeforces Round 54 (Rated for Div.2)

---

D. Edge Deletion

題意：一張n個點(diǎn)的無向圖，保留其中k條邊，使得有盡可能多的點(diǎn)與1的最短路長度不變。

做法：求出最短路樹，然后自底向上刪邊即可。

#include <bits/stdc++.h> #define pb push_back #define P pair<ll,int> typedef long long ll; const ll inf = 1e18; const int N = 3e5 + 7; using namespace std; int n, m , k; struct edge{int e,nxt,id; ll w; }E[N<<1],E2[N<<1]; int h[N], cc, h2[N],cc1; void add(int u,int v,ll w,int d) {E[cc].e = v; E[cc].w = w; E[cc].id = d;E[cc].nxt = h[u]; h[u] = cc; ++cc; } void add2(int u,int v,ll w,int d) {E2[cc1].e = v; E2[cc1].w = w; E2[cc1].id = d;E2[cc1].nxt = h2[u]; h2[u] = cc1; ++cc1; } struct node{int x;ll d;node(){}node(int a,ll b){x=a;d=b;}bool operator < (const node a)const {return a.d < d;} }; ll dis[N]; int vis[N], fa[N], fr[N]; void dij() {for(int i=1;i<=n;++i)dis[i]=inf;priority_queue<node> q;q.push(node(1,0));dis[1]=0; fa[1] = 0; fr[1] = -1;while(!q.empty()) {node tmp = q.top(); q.pop();int u=tmp.x;if(vis[u])continue;vis[u]=1;for(int i=h[u];~i;i=E[i].nxt) {int v=E[i].e;if(dis[v]>dis[u]+E[i].w) {dis[v]=dis[u]+E[i].w;fa[v] = u;fr[v] = E[i].id;q.push(node(v,dis[v]));}}}return; } struct node2{int u,v,id; ll w;node2(){}node2(int a,int b,ll c, int d) {u=a; v = b; w = c; id = d;} }; node2 A[N];int dep[N]; void bfs() {queue<int> q;memset(dep,-1,sizeof(dep));q.push(1); dep[1] = 0;while(!q.empty()) {int u = q.front(); q.pop();for(int i = h2[u]; ~i ; i = E2[i].nxt) {int v = E2[i].e;if(dep[v] == -1) {dep[v] = dep[u] + 1;q.push(v);}}} }vector< P > B; int vis2[N]; int main() {scanf("%d%d%d",&n,&m,&k);memset(h,-1,sizeof(h));memset(h2,-1,sizeof(h2));for(int i = 1; i <= m; ++i) { int u,v; ll w;scanf("%d%d%lld",&u,&v,&w);A[i] = node2(u,v,w,i);add(u,v,w,i); add(v,u,w,i);}dij();for(int i = 2; i <= n; ++i) {int p = fr[i];vis2[p] = 1;add2(A[p].u,A[p].v,A[p].w,A[p].id);add2(A[p].v,A[p].u,A[p].w,A[p].id);}int e = n-1;bfs();for(int i = 2; i <= n; ++i) B.pb(P(dep[i],i));sort(B.begin(),B.end());for(int i = (int)B.size()-1; i >= 0; --i) {if(e > k) {vis2[fr[B[i].second]] = 0;--e;}}printf("%d\n",e);for(int i = 1; i <= m; ++i) if(vis2[i]) printf("%d ",i); puts(""); }

E. Vasya and a Tree

題意：給定一顆樹，進(jìn)行m個操作，每次將節(jié)點(diǎn)v子樹中向下d+1層，的點(diǎn)全部加x，操作完成后詢問每個點(diǎn)的值。

做法：dfs這棵樹的同時(shí)，樹狀數(shù)組維護(hù)對應(yīng)深度的影響，退出遞歸時(shí)，還原現(xiàn)場即可，類似于樹上逆序?qū)?#xff0c;因?yàn)椴僮鞯目偤蜑閙所以復(fù)雜度有保證。kd-tree和二維樹狀數(shù)組，都沒卡過去。。。

#include <bits/stdc++.h> #define pb push_back #define fr first #define sc second #define P pair<int,ll> typedef long long ll; const int N = 300100; using namespace std; int n, m; int dep[N],MX; vector<int> G[N]; vector< P > A[N]; ll B[N], ans[N<<1]; void add(int x,ll v) {x += 10;for(int i=x;i;i-=(i&-i)) B[i] += v; } ll ask(int x) {ll ans = 0;x += 10;for(int i = x; i <= MX+20; i+=(i&(-i))) ans += B[i];return ans; } void dfs(int u,int fa) {dep[u] = dep[fa] + 1;MX = max(dep[u],MX);for(int i = 0; i < G[u].size(); ++i) {int v = G[u][i];if(v != fa) dfs(v,u);} } void dfs2(int u,int fa) {for(int i = 0; i < A[u].size(); ++i) add(A[u][i].fr,A[u][i].sc);ans[u] = ask(dep[u]);for(int i = 0; i < G[u].size(); ++i) {int v = G[u][i];if(v != fa) {dfs2(v,u);}}for(int i = 0; i < A[u].size(); ++i) add(A[u][i].fr,-A[u][i].sc); } int main() {scanf("%d",&n);for(int i = 1; i <= n-1; ++i) { int u,v;scanf("%d%d",&u,&v);G[u].pb(v); G[v].pb(u);}dep[0] = -1;dfs(1,0);scanf("%d",&m);for(int i = 1; i <= m; ++i) { int v,d; ll x;scanf("%d%d%lld",&v,&d,&x);A[v].pb(P(min(dep[v]+d,MX),x));}dfs2(1,0);for(int i = 1; i <= n; ++i)printf("%lld ",ans[i]);puts("");return 0; }

F. Summer Practice Report

題意：有\(n\)頁紙，第\(i\)頁包含\(a[i]\)個\(T\), \(b[i]\)個\(F\)，要求將所有的\(n\)頁紙并起來后，不能有連續(xù)的\(k\)個\(T\)或\(F\)，問是否有解。

做法：貪心構(gòu)造dp。\(dp[i][0/1]\) 表示前\(i\)頁紙放完，最后幾個字符是\(T\)或\(F\)時(shí)，\(T\)或\(F\)最小的數(shù)目。如果\(min(dp[n][0], dp[n][1]) <= k\) 則滿足條件。考慮如何\(dp\)，設(shè)上一張末尾的\(T\)有\(pa\)張或\(F\)有\(pb\)張，當(dāng)前這一張有\(a\)個\(T\)，\(b\)個\(F\)。
先確定\(dp[i][0]\)的轉(zhuǎn)移，考慮放滿\(T\)然后向其中插入\(F\)，用\(pa\)更新答案，那么如果\(pa<=k\)時(shí)，\(num\)即是需要插入的最少的\(F\)的個數(shù)，如果\(b == num\)， 那么用最后剩下的\(T\)更新答案，同時(shí)可以知道\(b\)的上界就是每個\(T\)之間都插入\(k\)個\(F\)，如果\(b>num\)且\(b <= k*a\)，就可以在最后一個\(T\)之前插入一個\(F\)，使得答案為\(1\)。用\(pb\)更新答案，思路類似，需要修改一下限制條件。\(dp[i][1]\) 也可以同樣的轉(zhuǎn)移。注意過程中會爆\(int\)

這道題在\(dp\)的同時(shí)貪心的轉(zhuǎn)移，感覺思路十分清奇，看懂官方題解感覺自己dp爛的不要不要的。。。

#include <bits/stdc++.h> typedef long long ll; const int N = 300000+5; const ll inf = 0x3f3f3f3f3f3f3f3f3f3f; using namespace std; int n, k, a[N], b[N]; int dp[N][2]; int cal(int pa, int pb, int a, int b) {ll ans = inf;if(pa <= k) {int num = (a + pa) / k + !!((a + pa) % k) - 1;if(b == num)ans = min(ans, pa + a - (ll)num*k);else if(b > num && (ll)b <= (ll)a*k)ans = min(ans, 1ll);}if(pb <= k) {int num = a / k + !!(a % k) - 1;if(b == num)ans = min(ans, a - (ll)num*k);else if(b > num && (ll)b <= (ll)(a-1)*k + (k-pb))ans = min(ans, 1ll);}return (int)ans; } int main() {scanf("%d %d", &n, &k);for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);for(int i = 1; i <= n; ++i) scanf("%d", &b[i]);for(int i = 1; i <= n; ++i) dp[i][0] = dp[i][1] = inf;for(int i = 1; i <= n; ++i) {dp[i][0] = cal(dp[i-1][0], dp[i-1][1], a[i], b[i]);dp[i][1] = cal(dp[i-1][1], dp[i-1][0], b[i], a[i]);}if(dp[n][0] <= k || dp[n][1] <= k) puts("YES");else puts("NO");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9969644.html

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 54 (Rated for Div.2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。