乐清市网站建设哪家性价比高,wordpress设计导航,郴州企业网站建设制作,做网站需要先学什么Educational Codeforces Round 54 (Rated for Div.2) D. Edge Deletion 题意#xff1a;一张n个点的无向图#xff0c;保留其中k条边#xff0c;使得有尽可能多的点与1的最短路长度不变。 做法#xff1a;求出最短路树#xff0c;然后自底向上删边即可。 #include bit… Educational Codeforces Round 54 (Rated for Div.2) D. Edge Deletion 题意一张n个点的无向图保留其中k条边使得有尽可能多的点与1的最短路长度不变。 做法求出最短路树然后自底向上删边即可。 #include bits/stdc.h
#define pb push_back
#define P pairll,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[N1],E2[N1];
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){xa;db;}bool operator (const node a)const {return a.d d;}
};
ll dis[N];
int vis[N], fa[N], fr[N];
void dij() {for(int i1;in;i)dis[i]inf;priority_queuenode 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 utmp.x;if(vis[u])continue;vis[u]1;for(int ih[u];~i;iE[i].nxt) {int vE[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) {ua; v b; w c; id d;}
};
node2 A[N];int dep[N];
void bfs() {queueint 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 题意给定一颗树进行m个操作每次将节点v子树中向下d1层的点全部加x操作完成后询问每个点的值。 做法dfs这棵树的同时树状数组维护对应深度的影响退出递归时还原现场即可类似于树上逆序对因为操作的总和为m所以复杂度有保证。kd-tree和二维树状数组都没卡过去。。。 #include bits/stdc.h
#define pb push_back
#define fr first
#define sc second
#define P pairint,ll
typedef long long ll;
const int N 300100;
using namespace std;
int n, m;
int dep[N],MX;
vectorint G[N];
vector P A[N];
ll B[N], ans[N1];
void add(int x,ll v) {x 10;for(int ix;i;i-(i-i)) B[i] v;
}
ll ask(int x) {ll ans 0;x 10;for(int i x; i MX20; 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\)页纸并起来后不能有连续的\(k\)个\(T\)或\(F\)问是否有解。 做法贪心构造dp。\(dp[i][0/1]\) 表示前\(i\)页纸放完最后几个字符是\(T\)或\(F\)时\(T\)或\(F\)最小的数目。如果\(min(dp[n][0], dp[n][1]) k\) 则满足条件。考虑如何\(dp\)设上一张末尾的\(T\)有\(pa\)张或\(F\)有\(pb\)张当前这一张有\(a\)个\(T\)\(b\)个\(F\)。 先确定\(dp[i][0]\)的转移考虑放满\(T\)然后向其中插入\(F\)用\(pa\)更新答案那么如果\(pak\)时\(num\)即是需要插入的最少的\(F\)的个数如果\(b num\) 那么用最后剩下的\(T\)更新答案同时可以知道\(b\)的上界就是每个\(T\)之间都插入\(k\)个\(F\)如果\(bnum\)且\(b k*a\)就可以在最后一个\(T\)之前插入一个\(F\)使得答案为\(1\)。用\(pb\)更新答案思路类似需要修改一下限制条件。\(dp[i][1]\) 也可以同样的转移。注意过程中会爆\(int\) 这道题在\(dp\)的同时贪心的转移感觉思路十分清奇看懂官方题解感觉自己dp烂的不要不要的。。。 #include bits/stdc.h
typedef long long ll;
const int N 3000005;
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;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9969644.html
