企业官网建设流程全解析

P1352 没有上司的舞会

#include <bits/stdc++.h> using namespace std; int n, r[6010], l, k, root, fa[6010], f[6010][2], ans; //k是l的上司 vector<int> son[6010]; void dp(int x) { f[x][0]=0; //x不参加舞会 f[x][1]=r[x]; //x参加舞会 for(int i=0; i<son[x].size(); ++i){ int y=son[x][i]; dp(y); f[x][0]+=max(f[y][0], f[y][1]); f[x][1]+=f[y][0]; } } int main() { scanf("%d", &n); for(int i=1; i<=n; ++i){ scanf("%d", &r[i]); } for(int i=1; i<=n-1; ++i){ scanf("%d %d", &l, &k); //k是l的上司 fa[l]=k; //k是父亲结点 son[k].push_back(l); //l是儿子结点 } //找根节点 for(int i=1; i<=n; ++i){ if(!fa[i]){ root=i; break; } } dp(root); ans=max(f[root][0], f[root][1]); printf("%d", ans); return 0; }

P2585 [ZJOI2006] 三色二叉树

#include <iostream> #include <algorithm> #include <string.h> using namespace std; string s; int n, tree[500010][3], cnt, dp_max[500010][3], dp_min[500010][3]; void build() { cnt++; int u=cnt; if(s[u-1]=='2'){ tree[u][1]=cnt+1; build(); tree[u][2]=cnt+1; build(); } else if(s[u-1]=='1'){ tree[u][1]=cnt+1; build(); } else if(s[u-1]=='0'){ return; } } void dfs(int u) { //该节点为空，则直接return if(u==0){ return; } //如果是叶子节点 if(tree[u][1]==0){ //节点u染绿色的情况下，以节点u为根的子树中，最多和最少的绿色节点数 dp_max[u][1]=1; dp_min[u][1]=1; //节点u不染绿色的情况下，以节点u为根的子树中，最多和最少的绿色节点数 dp_max[u][0]=0; dp_min[u][0]=0; } else if(tree[u][1]!=0){ int l=tree[u][1]; int r=tree[u][2]; dfs(l); dfs(r); //节点u染绿色的情况下，以节点u为根的子树中，最多和最少的绿色节点数 //u染绿色的情况下，两个子节点都不能染绿色 dp_max[u][1]=1+dp_max[l][0]+dp_max[r][0]; dp_min[u][1]=1+dp_min[l][0]+dp_min[r][0]; //节点u不染绿色的情况下，以节点u为根的子树中，最多和最少的绿色节点数 //u不染绿色，两个字节点就必须有一个染绿色，一个不染绿色 dp_max[u][0]=max(dp_max[l][1]+dp_max[r][0], dp_max[l][0]+dp_max[r][1]); dp_min[u][0]=min(dp_min[l][1]+dp_min[r][0], dp_min[l][0]+dp_min[r][1]); } } int main() { cin >> s; //建树 build(); n=s.size(); // for(int i=1; i<=n; ++i){ // cout << i << " " << tree[i][1] << " " << tree[i][2] << endl; // } dfs(1); //1号根节点不染绿色和染绿色分别求最大值和最小值 cout << max(dp_max[1][0], dp_max[1][1]) << " " << min(dp_min[1][0], dp_min[1][1]) << endl; return 0; }

P2015 二叉苹果树

树上背包

#include <bits/stdc++.h> using namespace std; int n, q, dp[110][110], tot, head[110], x, y, z; bool vis[110]; struct node { int to, dis, nex; }e[210]; void add(int u, int v, int w) { tot++; e[tot].to=v; e[tot].dis=w; e[tot].nex=head[u]; head[u]=tot; } //从u点出发, 求出dp[u][1]~dp[u][q] void dfs(int u){ vis[u]=true; for(int i=head[u]; i; i=e[i].nex){ int v=e[i].to; int w=e[i].dis; if(vis[v]){ //如果已经考虑过点v, 则跳过 continue; } //从v点出发, 求出dp[v][1]~dp[v][q] dfs(v); for(int j=q; j>=1; --j){ //01背包, 背包容量倒序 //v节点往出散的树枝数量, 因为u,v相连, 所以v最多只能往出散j-1条树枝, //如果v带0条树枝, 相当于不选节点v for(int k=j-1; k>=0; --k){ //k表示点v往出散的树枝数量, 当k为0时, v不往出散树枝 //v往出散k条树枝, 则u只能往出散j-k-1条, 留一条给uv dp[u][j]=max(dp[u][j], dp[v][k]+dp[u][j-k-1]+w); } } } } int main() { scanf("%d %d", &n, &q); for(int i=1; i<n; ++i){ scanf("%d %d %d", &x, &y, &z); add(x, y, z); add(y, x, z); } //从根1出发, 求出dp[1][1]~dp[1][q] dfs(1); printf("%d", dp[1][q]); return 0; }

第一个点

5 3 1 2 0 1 5 1 5 3 100 5 4 1

第一个点

102

P1273 有线电视网

P1040 [NOIP2003 提高组] 加分二叉树

P1122 最大子树和

#include <bits/stdc++.h> using namespace std; int n, a, b, beauty[17000], dp[17000], tot, head[17000], ans=-2e9; //不能全剪掉 bool vis[17000]; struct node { int to, nex; }e[40000]; void add(int u, int v) { tot++; e[tot].to=v; e[tot].nex=head[u]; head[u]=tot; } //以点u为根节点的树中, 最大的美丽指数 void dfs(int u) { vis[u]=true; //每次在dfs刚开始就标记 dp[u]=beauty[u]; //以u为根, 必须选u //枚举所有的儿子节点 for(int i=head[u]; i; i=e[i].nex){ int v=e[i].to; if(vis[v]){ //如果访问过, 直接跳过 continue; } dfs(v); //在以点v为根节点的树中, 找最大的美丽指数 if(dp[v]>0){ //如果以点v为根节点的树中, 有大于0的美丽指数, 就加上这一分支 dp[u]+=dp[v]; } } } int main() { scanf("%d", &n); for(int i=1; i<=n; ++i){ scanf("%d", &beauty[i]); } for(int i=1; i<n; ++i){ scanf("%d %d", &a, &b); add(a, b); add(b, a); } dfs(1); for(int i=1; i<=n; ++i){ ans=max(ans, dp[i]); } printf("%d", ans); return 0; }

U81904 【模板】树的直径

#include <bits/stdc++.h> #define int long long using namespace std; int n, m, uu, vv, ww, head[500010], tot, ans; bool vis[500010]; struct node { int to, dis, nex; }e[1000010]; void add(int u, int v, int w) { tot++; e[tot].to=v; e[tot].dis=w; e[tot].nex=head[u]; head[u]=tot; } //从u出发找离它最远的点的距离, 和第二远的距离 int dfs(int u) { vis[u]=true; int dist=0, d1=0, d2=0; for(int i=head[u]; i; i=e[i].nex){ int v=e[i].to; if(vis[v]){ //如果已经基于点v dfs过了 continue; } int w=e[i].dis; int d=dfs(v)+w; dist=max(dist, d); //打擂台, 找距离点u最远的点, 并更新最远距离 if(d>=d1){ d2=d1; d1=d; } else if(d>d2){ d2=d; } cout << d1 << " asd " << d2 << endl; } ans=max(ans, d1+d2); return dist; } signed main() { scanf("%lld", &n); for(int i=1; i<n; ++i){ scanf("%lld %lld %lld", &uu, &vv, &ww); add(uu, vv, ww); add(vv, uu, ww); } //找出每个点出发, 离它最远的点的距离加上第二远点的距离就是答案 dfs(1); printf("%lld", ans); return 0; }

T95371 约数变换

nlogn求约数

#include <bits/stdc++.h> using namespace std; int n, ans, tot, head[50010], sum[50010]; bool root[50010]; struct node { int to, nex; }e[50010]; void add(int u, int v) { tot++; e[tot].to=v; e[tot].nex=head[u]; head[u]=tot; } int dfs(int u) { //从u出发的最长路径长度d1, 第二长路径长度d2 int d1=0, d2=0; for(int i=head[u]; i; i=e[i].nex){ int v=e[i].to; int d=dfs(v)+1; if(d>=d1){ d2=d1; d1=d; } else if(d>d2){ d2=d; } } ans=max(ans, d1+d2); return d1; } int main() { scanf("%d", &n); for(int i=1; i<=n; ++i){ for(int j=2; j<=n/i; ++j){ sum[i*j]+=i; } } //i从2开始, 因为1的约数和为0, 题目要求所有的数都是正数 for(int i=2; i<=n; ++i){ if(sum[i]<i){ add(sum[i], i); root[i]=true; } } //树根是可以从1开始枚举的 for(int i=1; i<=n; ++i){ if(!root[i]){ dfs(i); } } printf("%d", ans); return 0; }

nsqrt(n)求约数

#include <bits/stdc++.h> using namespace std; int n, ans, tot, head[50010], sum[50010]; bool root[50010]; struct node { int to, nex; }e[50010]; void add(int u, int v) { tot++; e[tot].to=v; e[tot].nex=head[u]; head[u]=tot; } int dfs(int u) { //从u出发的最长路径长度d1, 第二长路径长度d2 int d1=0, d2=0; for(int i=head[u]; i; i=e[i].nex){ int v=e[i].to; int d=dfs(v)+1; if(d>=d1){ d2=d1; d1=d; } else if(d>d2){ d2=d; } } ans=max(ans, d1+d2); return d1; } int main() { scanf("%d", &n); for(int i=1; i<=n; ++i){ for(int j=1; j<=sqrt(i); ++j){ if(i%j==0){ sum[i]+=j+i/j; if(j*j==i){ sum[i]-=j; } } } sum[i]-=i; } //i从2开始, 因为1的约数和为0, 题目要求所有的数都是正数 for(int i=2; i<=n; ++i){ if(sum[i]<i){ add(sum[i], i); root[i]=true; } } //树根是可以从1开始枚举的 for(int i=1; i<=n; ++i){ if(!root[i]){ dfs(i); } } printf("%d", ans); return 0; }

P2014 [CTSC1997] 选课

#include <bits/stdc++.h> using namespace std; int n, m, dp[310][310], tot, head[310], kk, ss; bool vis[310]; struct node { int to, dis, nex; }e[310]; void add(int u, int v) { tot++; e[tot].to=v; e[tot].nex=head[u]; head[u]=tot; } //从u点出发, 求出dp[u][1]~dp[u][q] void dfs(int u){ vis[u]=true; for(int i=head[u]; i; i=e[i].nex){ int v=e[i].to; if(vis[v]){ //如果已经考虑过点v, 则跳过 continue; } //从v点出发, 求出dp[v][1]~dp[v][m] dfs(v); for(int j=m; j>=1; --j){ //01背包, 背包容量倒序 //k表示以v节点为根的选课数量, 因为u必须选, 所以以v为根最多只能选j-1门课, //如果以v为根选0门课, 相当于不选v这门课 for(int k=0; k<=j-1; ++k){ //k表示以v为根的选课数量, 当k为0时, 不选v这门课 //以v为根选k门课, 则以u为根到截止到v时(没有选v)只能选j-k门课 dp[u][j]=max(dp[u][j], dp[v][k]+dp[u][j-k]); } } } } int main() { scanf("%d %d", &n, &m); for(int i=1; i<=n; ++i){ scanf("%d %d", &kk, &ss); dp[i][1]=ss; add(kk, i); //0作为超级根, 将森林变为树 } m++; //因为多选了一门0号虚拟课程 //从根0出发, 求出dp[0][1]~dp[0][m] dfs(0); printf("%d", dp[0][m]); return 0; }

P3174 [HAOI2009] 毛毛虫

#include <iostream> #include <algorithm> #include <vector> using namespace std; //dp[u]表示以u为起点，在它的子树中找一条链, 所能形成的毛毛虫的最大值 int n, m, a, b, dp[300010], id, cnt, mx; vector<int> asd[300010]; void dfs(int u, int fa) { int mx1=0, mx2=0; for(int i=0; i<asd[u].size(); ++i){ int v=asd[u][i]; if(v!=fa){ dfs(v, u); dp[u]=max(dp[u], dp[v]); //如果比最大儿子还要大 if(dp[v]>=mx1){ mx2=mx1; //原来的最大儿子退居二线 mx1=dp[v]; //dp[v]变成最大的 } else if(dp[v]>mx2){ //如果比二儿子大 mx2=dp[v]; } } } if(asd[u].size()<=1){ dp[u]+=1; mx=max(mx, dp[u]); } else{ dp[u]+=asd[u].size()-1; mx=max(mx, int(mx1+mx2+asd[u].size()-1)); } } int main() { scanf("%d %d", &n, &m); for(int i=1; i<=m; ++i){ scanf("%d %d", &a, &b); asd[a].push_back(b); asd[b].push_back(a); } dfs(1, 0); // for(int i=1; i<=n; ++i){ // cout << i << " " << dp[i] << endl; // } printf("%d\n", mx); return 0; }

P3047 [USACO12FEB]Nearby Cows G

P3698 [CQOI2017]小Q的棋盘

P5658 [CSP-S2019] 括号树

P2607 [ZJOI2008] 骑士

P3177 [HAOI2015] 树上染色

P4395 [BOI2003]Gem 气垫车

P4516 [JSOI2018] 潜入行动

P2700 逐个击破