本文主要是介绍2.11学习总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有效点对https://www.acwing.com/problem/content/description/5472/
给定一个 n� 个节点的无向树，节点编号 1∼n1∼�。
树上有两个不同的特殊点 x,y�,�，对于树中的每一个点对 (u,v)(u≠v)(�,�)(�≠�)，如果从 u� 到 v� 的最短路径需要经过点 x� 和点 y�（路径的两个端点也算经过），且相对顺序上先经过点 x�，后经过点 y�，那么就称 (u,v)(�,�) 是一个无效点对，否则就称 (u,v)(�,�) 是一个有效点对。
请你计算树中有效点对的数量。
注意：
- (u,v)(�,�) 和 (v,u)(�,�) 是两个不同的点对。
- 有效点对必须满足 u≠v�≠�。
输入格式
第一行包含三个整数 n,x,y�,�,�。
接下来 n−1�−1 行，每行包含两个整数 a,b�,�，表示点 a� 和点 b� 之间存在一条无向边。
输出格式
一个整数，表示有效点对的数量。
数据范围
前 33 个测试点满足 1≤n≤101≤�≤10。
所有测试点满足 1≤n≤3×1051≤�≤3×105，1≤x,y≤n1≤�,�≤�，x≠y�≠�，1≤a,b≤n1≤�,�≤�，a≠b�≠�。
输入样例1：
3 1 3
1 2
2 3
输出样例1：
5
输入样例2：
3 1 3
1 2
1 3
输出样例2：
4思路：用DFS，只要计算出无效点，就可以得到有效点的数量，由于是树状结构，所以x点y的路径总和等于以x为根的子树大小*以y为根的子树大小
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
const int N=3e5+5;
int dp[N],vis[N];
vector<int>e[N];
void dfs(int u,int fa){dp[u]=1;for (int i=0;i<e[u].size();++i){int v=e[u][i];//if (vis[v]) continue;if (v!=fa){//vis[v]=1;dfs(v,u);dp[u]+=dp[v];//vis[v]=0;}}
}
signed main(){int n,x,y;cin>>n>>x>>y;for (int i=0;i<n-1;++i){int a,b;cin>>a>>b;e[a].push_back(b);e[b].push_back(a);}dfs(y,-1);int res=dp[x];for (int i=1;i<=n;++i) dp[i]=0;dfs(x,-1);res=dp[y]*res;res=n*(n-1)-res;cout<<res;
} 最有价值字符串https://www.acwing.com/problem/content/description/5471/
A,B,C�,�,� 三人在玩一个有关字符串的游戏。
给定三人每人一个由大小写字母构成的字符串。
三人的字符串的长度相同。
规定，一个字符串的价值等于该字符串中出现次数最多的子串的出现次数。
例如，aaaaaa 的价值为 66，因为出现次数最多的子串 a 一共出现了 66 次；abab 的价值为 22，因为出现次数最多的子串 ab 一共出现了 22 次。
游戏开始后，每人都需要对自己的字符串进行恰好 n� 次修改，每次修改需要将字符串中的某个字符修改为另一个不同的字符，例如将 aaab 修改为 acab。
所有修改完毕后，最有价值字符串的拥有者将获得游戏胜利。
请你计算，如果所有人都采取最优策略，那么谁将最终获胜。
输入格式
第一行包含整数 n�。
第二行，包含一个由大小写字母构成的字符串，表示给 A� 的字符串。
第三行，包含一个由大小写字母构成的字符串，表示给 B� 的字符串。
第四行，包含一个由大小写字母构成的字符串，表示给 C� 的字符串。
保证这三个人获得的字符串的长度均相同。
输出格式
共一行，A� 获胜则输出 A，B� 获胜则输出 B，C� 获胜则输出 C，不止一人获胜则输出 D。
数据范围
前 66 个测试点满足 0≤n≤200≤�≤20，每个输入字符串的长度范围 [1,20][1,20]。
所有测试点满足 0≤n≤1090≤�≤109，每个输入字符串的长度范围 [1,105][1,105]。
输入样例1：
3
abcdd
efgcd
hijgk
输出样例1：
A
输入样例2：
7
abcdefbcgfhi
igbccjbkchle
gkmnlcjnboce
输出样例2：
B
输入样例3：
1
abcabc
cbabac
ababca
输出样例3：
C
输入样例4：
15
abcdefghi
jkdlbmnop
jqrstduve
输出样例4：
D思路：先算出单个字符的最大价值，然后找到可更换的数量，和需要更换的次数，如果可更换的次数为0且需要更换次数为1，那么总数减1，否则，就是加上min（可更换次数，需要更换次数），如果可更换次数更大，那么所有需要更换次数都用在更换字符上，反之就是把可更换的字符都更换了
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
map<char,int>ma,mb,mc;
signed main(){int n;cin>>n;string a,b,c;cin>>a>>b>>c;int man=0,mbn=0,mcn=0;for (int i=0;i<a.size();++i){ma[a[i]]++;mb[b[i]]++;mc[c[i]]++;man=max(man,ma[a[i]]);mbn=max(mbn,mb[b[i]]);mcn=max(mcn,mc[c[i]]);}//找到可以交换的个数来提高价值int ka=0,kb=0,kc=0;ka=a.size()-man;kb=a.size()-mbn;kc=a.size()-mcn;//aaaaaaa ma=5 ka=0 n=3if (!ka && n==1) man=a.size()-1;else man+=min(ka,n);if (!kb && n==1) mbn=a.size()-1;else mbn+=min(kb,n);if (!kc&& n==1) mcn=a.size()-1;else mcn+=min(kc,n);if (man>mbn && man>mcn) cout<<"A";else if (mbn>man && mbn>mcn) cout<<"B";else if (mcn>man && mcn>mbn) cout<<"C";else cout<<"D";} 大臣的旅费https://www.luogu.com.cn/problem/P8602
题目描述
很久以前，T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的 J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 �x 千米到第 �+1x+1 千米这一千米中（�x 是整数），他花费的路费是 �+10x+10 这么多。也就是说走 11 千米花费 1111，走 22 千米要花费 2323。
J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式
输入的第一行包含一个整数 �(�≤105)n(n≤105)，表示包括首都在内的 �T 王国的城市数。
城市从 11 开始依次编号，11 号城市为首都。
接下来 �−1n−1 行，描述 �T 国的高速路（�T 国的高速路一定是 �−1n−1 条）。
每行三个整数 ��,�,��Pi,Q,Di，表示城市 ��Pi 和城市 ��Qi 之间有一条高速路，长度为 ��(��≤1000)Di(Di≤1000) 米。
输出格式
输出一个整数，表示大臣J最多花费的路费是多少。
输入输出样例
输入 #1复制
5 1 2 2 1 3 1 2 4 5 2 5 4
输出 #1复制
135
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
int f[500005],vis[500005],dp[500005];
struct edge{int to;int w;edge(int a,int b){to=a;w=b;}
};
vector<edge>tree[500005];
void dfs(int u){vis[u]=1;for (int i=0;i<tree[u].size();++i){edge y=tree[u][i];if (vis[y.to])continue;dfs(y.to);f[u]=max(f[u],dp[u]+dp[y.to]+y.w);dp[u]=max(dp[u],dp[y.to]+y.w);}return ;
}
signed main(){int n; cin>>n;for (int i=0;i<n-1;++i){int u,v,w;cin>>u>>v>>w;tree[u].push_back(edge(v,w));tree[v].push_back(edge(u,w));}dfs(1);int res=f[1];for(int i=2;i<=n;++i){res=max(res,f[i]);} cout<<res*10+res*(res+1)/2;
}树的直径https://www.luogu.com.cn/problem/U81904
题目描述
给定一棵树，树中每条边都有一个权值，
树中两点之间的距离定义为连接两点的路径边权之和。
树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。
现在让你求出树的最长链的距离
输入格式
给定一棵无根树
第一行为一个正整数�n,表示这颗树有�n个节点
接下来的�−1n−1行,每行三个正整数�,�,�u,v,w，表示�,�u,v（�,�<=�u,v<=n）有一条权值为�w的边相连
数据保证没有重边或自环
输出格式
输入仅一行，表示树的最长链的距离
输入输出样例
输入 #1复制
6 1 2 1 1 3 2 2 4 3 4 5 1 3 6 2
输出 #1复制
9
说明/提示
对于1010的数据 �<=10n<=10
对于3030的数据 �<=1000n<=1000
对于5050的数据 �<=10000n<=10000
对于7070的数据 �<=100000n<=100000 边权均为正整数
对于100100的数据 �<=500000n<=500000 边权可能为负
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
int f[500005],vis[500005],dp[500005];
struct edge{int to;int w;edge(int a,int b){to=a;w=b;}
};
vector<edge>tree[500005];
void dfs(int u){vis[u]=1;for (int i=0;i<tree[u].size();++i){edge y=tree[u][i];if (vis[y.to])continue;dfs(y.to);f[u]=max(f[u],dp[u]+dp[y.to]+y.w);dp[u]=max(dp[u],dp[y.to]+y.w);}return ;
}
signed main(){int n; cin>>n;for (int i=0;i<n-1;++i){int u,v,w;cin>>u>>v>>w;tree[u].push_back(edge(v,w));tree[v].push_back(edge(u,w));}dfs(1);int res=f[1];for (int i=2;i<=n;++i){res=max(res,f[i]);}cout<<res;
}这篇关于2.11学习总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
