• 补坑简单图论题


    链接:登录—专业IT笔试面试备考平台_牛客网
    来源:牛客网
     

    凯丽王国有 nnn 座城市,每个城市都有一个能量值 viv_ivi​,mmm 条单向道路连接着这些城市,但这些路不会构成环,即从任意一个城市出发,都无法回到这个城市

    而大马猴和机智羊要组队参加的下一个项目就是能量收集赛。能量收集赛的规则是:每位参赛者拿着一个能量值为 000 的水晶球,从他所在的城市出发,每经过一个他从未到达的城市,就可以收集这个城市的能量值并加入自己的能量球中,直到走到无法再走为止。

    所以每个参赛者都会收集尽可能多的能量。大马猴和机智羊都很聪明,他们在研究了地图之后,各自都能找到能量最多的路线。

    然而当他们完成比赛之后,他们才被告知,他们是作为小组参赛,必须交上去两个能量值一样的能量球才行。他们研究发现,只要花费 x×(x+1)x\times(x+1)x×(x+1) 的钱,就能将能量球的能量值从 xxx 提升为 x+1x+1x+1。

    鲨鱼博士想知道,如果大马猴一开始在城市 qqq,机智羊一开始在城市 ppp,那么:

    • 大马猴和机智羊的成绩(刚完成比赛时)分别是多少?

    • 为了使得他们的成绩有效,他们需要花费多少钱?

    输入描述:

     
     

    第一行包含 333 个正整数 nnn,mmm,ttt,分别表示城市的数量,单向道路的数量,询问次数。

    第二行 nnn 个正整数 viv_ivi​ ,依次表示每个城市的能量值。

    接下来 mmm 行,每行两个正整数 xix_ixi​ ,yi y_iyi​ ,表示存在一条单向道路,可以从城市 xix_ixi​ 出发到达城市 yiy_iyi​ 。

    接下来 ttt 行,每行两个正整数 qqq , ppp ,表示大马猴和机智羊一开始所在的城市。

    输出描述:

     
     

    对于每次询问,输出一行,三个整数,以空格作为分割,分别表示大马猴和机智羊刚完成比赛时的成绩,以及想要使得成绩有效,需要花费的钱

    由于答案太大,请对 109+710^9+7109+7 取模。

    链接:登录—专业IT笔试面试备考平台_牛客网
    来源:牛客网
     

    输入

    复制5 6 1 1 1 1 1 1 1 2 1 3 2 5 3 4 3 5 4 5 1 2

    5 6 1
    1 1 1 1 1
    1 2
    1 3
    2 5
    3 4
    3 5
    4 5
    1 2

    输出

    复制4 2 18

    4 2 18

    说明

     
     

    大马猴的路线为 1⇒3⇒4⇒51\Rightarrow3\Rightarrow4\Rightarrow51⇒3⇒4⇒5,收集到的能量为 1+1+1+1=41+1+1+1=41+1+1+1=4;

    机智羊的路线为 2⇒52\Rightarrow52⇒5,收集到的能量为 1+1=21+1=21+1=2;

    想要让两个人的能量值一样,先将机智羊的能量从 222 变为 333,即花费 2×32\times32×3 的钱;再从 333 变为 444,即花费 3×43\times43×4 的钱,共 2×3+3×4=182\times 3+3\times4=182×3+3×4=18。

    示例2

    输入

    复制8 9 2 2 2 1 2 1 3 5 2 1 2 1 3 2 4 3 4 4 5 4 7 5 8 6 3 6 4 1 6 5 5

    8 9 2
    2 2 1 2 1 3 5 2
    1 2
    1 3
    2 4
    3 4
    4 5
    4 7
    5 8
    6 3
    6 4
    1 6
    5 5

    输出

    复制11 11 0 3 3 0

    11 11 0
    3 3 0

    说明

     
     

    对于第一次询问:

    大马猴的路线为 1⇒2⇒4⇒71\Rightarrow2\Rightarrow4\Rightarrow71⇒2⇒4⇒7,收集到的能量为 2+2+2+5=112+2+2+5=112+2+2+5=11;

    机智羊的路线为 6⇒3⇒4⇒76\Rightarrow3\Rightarrow4\Rightarrow76⇒3⇒4⇒7,收集到的能量为 3+1+2+5=113+1+2+5=113+1+2+5=11;

    两个人的能量值一样,成绩有效。

    对于第二次询问:

    两个人的路线都为 5⇒85\Rightarrow85⇒8,收集到的能量都为 1+2=31+2=31+2=3,显然成绩有效。

    备注:

     
     

    1. #include
    2. typedef long long ll;
    3. typedef double db;
    4. using namespace std;
    5. const int mod=1e9+7;
    6. ll n,m,t;
    7. const int N=5e4+5;
    8. const int M=5e5+5;
    9. vectorG[M];
    10. ll f[M];
    11. ll a[N];
    12. ll dfs(ll x,ll fa)
    13. {
    14. if(f[x])
    15. return f[x];
    16. for(int i=0; isize(); i++)
    17. {
    18. if(G[x][i]!=fa)
    19. f[x]=max(f[x],dfs(G[x][i],x));
    20. }
    21. f[x]+=a[x];
    22. return f[x];
    23. }
    24. int main()
    25. {
    26. cin>>n>>m>>t;
    27. for(int i=1; i<=n; i++)
    28. {
    29. cin>>a[i];
    30. }
    31. for(int i=1; i<=m; i++)
    32. {
    33. ll x,y;
    34. cin>>x>>y;
    35. G[x].push_back(y);
    36. }
    37. for(int i=1;i<=t;i++)
    38. {
    39. ll p,q;
    40. cin>>p>>q;
    41. p=dfs(p,0);
    42. q=dfs(q,0);
    43. cout<" "<" ";
    44. if(p>q)
    45. swap(p,q);
    46. p--;
    47. q--;
    48. ll p1=p+1;
    49. ll p2=p+2;
    50. ll q1=q+1;
    51. ll q2=q+2;
    52. if(p%3==0)p/=3;
    53. else if(p1%3==0)p1/=3;
    54. else p2/=3;
    55. if(q%3==0)q/=3;
    56. else if(q1%3==0)q1/=3;
    57. else q2/=3;
    58. ll sum=(q2%mod*q1%mod*q%mod-p2%mod*p1%mod*p%mod+mod)%mod;
    59. cout<
    60. }
    61. return 0;
    62. }

     

    1. #include
    2. using namespace std;
    3. const int N = 200010;
    4. int n, m, mod = 1e9+7;
    5. long long dp[N], cnt = 0, t, a[N], ans;
    6. vector<int> G[N];
    7. long long quick(long long a,long long b,long long p){
    8. long long ans=1;
    9. while(b){
    10. if(b&1) ans=(long long)ans*a%p;
    11. a=(long long)a*a%p;
    12. b>>=1;
    13. }
    14. return ans;
    15. }
    16. long long Dfs(int x){
    17. if(dp[x] != -1) return dp[x];
    18. dp[x] = a[x];
    19. for (int j = 0; j < G[x].size(); j++){
    20. // if(In[G[x][j]] > 1 && out[x] > 1){
    21. dp[x] = max(dp[x], Dfs(G[x][j]) + a[x]);
    22. // }
    23. }
    24. return dp[x];
    25. }
    26. int main(){
    27. scanf("%d%d%d", &n, &m, &t);
    28. for (int i = 1; i <= n; i++){
    29. scanf("%lld", &a[i]);
    30. }
    31. memset(dp, -1, sizeof(dp));
    32. for (int i = 1; i <= m; i++){
    33. int x, y;
    34. scanf("%d%d", &x, &y);
    35. G[x].push_back(y);
    36. }
    37. for (int i = 1; i <= n; i++){
    38. ans = max(ans, Dfs(i));
    39. }
    40. while(t--){
    41. int q, p;
    42. scanf("%d%d", &q, &p);
    43. printf("%lld %lld ", dp[q], dp[p]);
    44. long long minn = min(dp[q], dp[p]);
    45. long long maxn = max(dp[q], dp[p]);
    46. long long ans1 = ((maxn-1) %mod*(maxn)%mod)%mod *(maxn +1)%mod *quick(3,mod-2,mod)%mod;
    47. long long ans2 = ((minn-1) %mod*(minn)%mod)%mod *(minn +1)%mod *quick(3,mod-2,mod)%mod;
    48. if(ans1 < ans2) ans1 += mod;
    49. long long ans = ans1 - ans2;
    50. // ans = ans * quick(3,mod-2,mod);
    51. printf("%lld\n", ans);
    52. }
    53. // int ans = 0;
    54. // cout << ans << endl;
    55. return 0;
    56. }

    1. #include
    2. using namespace std;
    3. #define int long long
    4. #define N 500001
    5. #define mod 1000000007
    6. int a[N];
    7. vector<int>ne[N];
    8. int ans[N],v[N];
    9. int dfs(int x){
    10. if(v[x]){
    11. return ans[x];
    12. }
    13. v[x]=1;
    14. int maxx=0;
    15. vector<int>ne1=ne[x];
    16. for(int i=0;isize();i++){
    17. maxx=max(maxx,dfs(ne1[i]));
    18. }
    19. return ans[x]=maxx+a[x];
    20. }
    21. signed main(){
    22. ios::sync_with_stdio(false);
    23. cin.tie(0);
    24. int n,m,t;
    25. cin>>n>>m>>t;
    26. for(int i=1;i<=n;i++){
    27. cin>>a[i];
    28. }
    29. for(int i=1;i<=m;i++){
    30. int x,y;
    31. cin>>x>>y;
    32. ne[x].push_back(y);
    33. }
    34. for(int i=1;i<=n;i++){
    35. if(!v[i]){
    36. dfs(i);
    37. }
    38. }
    39. while(t--){
    40. int p,q;
    41. cin>>p>>q;
    42. int x=ans[p],y=ans[q];
    43. cout<" "<" ";
    44. if(x>y){
    45. int t=x;
    46. x=y;
    47. y=t;
    48. }
    49. x--;y--;
    50. int sum=0;
    51. int y1=y+1,y2=y+2,x1=x+1,x2=x+2;
    52. if(y%3==0)y/=3;
    53. else if(y1%3==0)y1/=3;
    54. else y2/=3;
    55. if(x%3==0)x/=3;
    56. else if(x1%3==0)x1/=3;
    57. else x2/=3;
    58. sum=y%mod*y1%mod*y2%mod+mod-x%mod*x1%mod*x2%mod;
    59. cout<"\n";
    60. }
    61. return 0;
    62. }

     

  • 相关阅读:
    2022.09.19 学习笔记
    基于Matlab实现多个数字水印案例(附上源码+数据集)
    SpringCloud全系列知识(2)—— Nacos配置和集群
    docker容器镜像管理+compose容器编排(持续更新中)
    SP2-1503|0152:CMD窗口的SQLPLUS命令无法登录Oracle
    Vue学习:组件化
    Pytorch:tensor.mean()和tensor.sum()
    储能:储能大会“共建储能生态链,共创储能新发展”
    创建react脚手架项目——demo(react18 + react-router 6)
    [附源码]计算机毕业设计SpringBoot蛋糕购物商城
  • 原文地址:https://blog.csdn.net/m0_61949623/article/details/126246977