汕头网站设计价格网站界面类型

当前位置： 首页 > news >正文

汕头网站设计价格,网站界面类型,网站常规seo优化步骤,semi认证有效点对https://www.acwing.com/problem/content/description/5472/ 给定一个 n#xfffd; 个节点的无向树#xff0c;节点编号 1∼n1∼#xfffd;。 树上有两个不同的特殊点 x,y#xfffd;,#xfffd;#xff0c;对于树中的每一个点对 (u,v)(u≠v)(#xfffd;,…有效点对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×1051≤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 N3e55; int dp[N],vis[N]; vectorinte[N]; void dfs(int u,int fa){dp[u]1;for (int i0;ie[u].size();i){int ve[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;cinnxy;for (int i0;in-1;i){int a,b;cinab;e[a].push_back(b);e[b].push_back(a);}dfs(y,-1);int resdp[x];for (int i1;in;i) dp[i]0;dfs(x,-1);resdp[y]res;resn(n-1)-res;coutres; }
最有价值字符串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 获胜则输出 AB 获胜则输出 BC 获胜则输出 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 mapchar,intma,mb,mc; signed main(){int n;cinn;string a,b,c;cinabc;int man0,mbn0,mcn0;for (int i0;ia.size();i){ma[a[i]];mb[b[i]];mc[c[i]];manmax(man,ma[a[i]]);mbnmax(mbn,mb[b[i]]);mcnmax(mcn,mc[c[i]]);}//找到可以交换的个数来提高价值int ka0,kb0,kc0;kaa.size()-man;kba.size()-mbn;kca.size()-mcn;//aaaaaaa ma5 ka0 n3if (!ka n1) mana.size()-1;else manmin(ka,n);if (!kb n1) mbna.size()-1;else mbnmin(kb,n);if (!kc n1) mcna.size()-1;else mcnmin(kc,n);if (manmbn manmcn) coutA;else if (mbnman mbnmcn) coutB;else if (mcnman mcnmbn) coutC;else coutD;}
大臣的旅费https://www.luogu.com.cn/problem/P8602 题目描述 很久以前T 王国空前繁荣。为了更好地管理国家王国修建了大量的快速路用于连接首都和王国内的各大城市。 为节省经费T 国的大臣们经过思考制定了一套优秀的修建方案使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时如果不重复经过大城市从首都到达每个大城市的方案都是唯一的。 J 是 T 国重要大臣他巡查于各大城市之间体察民情。所以从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋用于存放往来城市间的路费。 聪明的 J 发现如果不在某个城市停下来修整在连续行进过程中他所花的路费与他已走过的距离有关在走第 x 千米到第 1x1 千米这一千米中x 是整数他花费的路费是 10x10 这么多。也就是说走 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){toa;wb;} }; vectoredgetree[500005]; void dfs(int u){vis[u]1;for (int i0;itree[u].size();i){edge ytree[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; cinn;for (int i0;in-1;i){int u,v,w;cinuvw;tree[u].push_back(edge(v,w));tree[v].push_back(edge(u,w));}dfs(1);int resf[1];for(int i2;in;i){resmax(res,f[i]);} coutres10res(res1)/2; } 树的直径https://www.luogu.com.cn/problem/U81904 题目描述 给定一棵树树中每条边都有一个权值 树中两点之间的距离定义为连接两点的路径边权之和。 树中最远的两个节点之间的距离被称为树的直径连接这两点的路径被称为树的最长链。 现在让你求出树的最长链的距离 输入格式 给定一棵无根树 第一行为一个正整数n,表示这颗树有n个节点 接下来的−1n−1行,每行三个正整数,,u,v,w表示,u,v,u,vn有一条权值为w的边相连 数据保证没有重边或自环 输出格式 输入仅一行表示树的最长链的距离 输入输出样例 输入 #1复制 6 1 2 1 1 3 2 2 4 3 4 5 1 3 6 2 输出 #1复制 9 说明/提示 对于1010的数据 10n10 对于3030的数据 1000n1000 对于5050的数据 10000n10000 对于7070的数据 100000n100000 边权均为正整数 对于100100的数据 500000n500000 边权可能为负 #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){toa;wb;} }; vectoredgetree[500005]; void dfs(int u){vis[u]1;for (int i0;itree[u].size();i){edge ytree[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; cinn;for (int i0;in-1;i){int u,v,w;cinuvw;tree[u].push_back(edge(v,w));tree[v].push_back(edge(u,w));}dfs(1);int resf[1];for (int i2;in;i){resmax(res,f[i]);}coutres; }