• “蔚来杯“2022牛客暑期多校训练营2补题记录(DGHJKL)

    把题补了,感觉要自己梳理一下,就写一下题解,

    后续会把其他自己能补的也补了.

    "蔚来杯"2022牛客暑期多校训练营2_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ牛客ACM提高训练营是面向ICPC/CCPC/CSP/NOI比赛备战的选手，由金牌选手命题，提高训练高难度的编程比赛，ACM/NOI拔高训练营。https://ac.nowcoder.com/acm/contest/33187

    目录

    D.Link with Game Glitch(SPFA判断负环,小数转log存储)

    G.Link with Monotonic Subsequence(构造,签到)

    H.Take the Elevator(模拟,贪心)

    J.Link with Arithmetic Progression(数学,线性回归方程)

    K.Link with Bracket Sequence I(括号匹配,dp)

    L.Link with Level Editor I

    D.Link with Game Glitch(SPFA判断负环,小数转log存储)

    思路:我们现在a个b物品转化为c个d物品,可以看成一个b物品可以转化为(c/a)个d物品,题目问c缩小几分之几可以保证不会无限的增长下去.首先明了,如果可以无限生成的话就肯定是形成了一个循环,而且这个循环是成倍增长的,也就是说这个环的增长倍数(c/a)是>1的,这样的话就会无限的增长.此时我们就可以把这个问题抽象成一个图论问题.:

    我们按照题目给的生成关系建立单向边,边权就是每一组的(c/a).当然,如果连续处理多个这种小数相乘的话很容易丢精,那么就可以尝试把边建立为log,就w=log(c/a).这样的话边权就不是一个小时,而是一个带小数点的负数,不那么容易丢精.

    然后我们对着这个图用spfa跑最长路(因为本来按照题意路径就在增长(c/a大于1的话)).然后用spfa判断负环.这里判断负环是根据spfa的性质,如果边权(也就是c/a)>1的话那么spfa的"缩点操作"就会无限伸长.那么这里就可以判断次数即可判断负环.而对于题目所说的要更改的w,(按照题意就是让每个边变为c/a*k,k为我们所求的倍数答案,范围是[0,1]).那么根据之前的log保证精度的写法,这个式子就变成了log(c/a)+log(k).这个k的取值对结果产生单调性,那么我们就可以采用二分k的大小,然后用SPFA判断负环进行check即可求出答案.

    ps:这里向严格鸽学了个小数二分的方法,不用l 

    1. for(int i=0;i<=100;i++)
    2.     {
    3.         double mid=(l+r)/2;
    4.         if(check(mid))
    5.             l=mid;
    6.         else
    7.             r=mid;
    8.     }

    一定可以保证精度了.

    AC code:

    1. #include
    2. using namespace std;
    3. int tot=0,n;
    4. struct node
    5. {
    6.     int to,ne;
    7.     double val;
    8. }edge[2010];
    9. int h[1010];
    10. void add(int x,int y,double val)
    11. {
    12.     edge[++tot].to=y;
    13.     edge[tot].ne=h[x];
    14.     edge[tot].val=val;
    15.     h[x]=tot;
    16.     return ;    
    17. }
    18. int vis[1010],cnt[1010];
    19. double dis[1010];
    20. int check(double mid)
    21. {
    22.     mid=log(mid);
    23.     queue<int>qu;
    24.     for(int i=1;i<=n;i++)
    25.     {
    26.         cnt[i]=vis[i]=0;
    27.         dis[i]=0.0;
    28.         qu.push(i);
    29.     }
    30.     while(qu.size())
    31.     {
    32.         int st=qu.front();
    33.         qu.pop();
    34.         vis[st]=0;
    35.         for(int i=h[st];i!=-1;i=edge[i].ne)
    36.         {
    37.             double len=edge[i].val;
    38.             int en=edge[i].to;
    39.             if(dis[st]+mid+len>dis[en])
    40.             {
    41.                 dis[en]=dis[st]+mid+len;
    42.                 cnt[en]=cnt[st]+1;
    43.                 if(cnt[en]>n)
    44.                     return 0;
    45.                 if(vis[en]==0)
    46.                 {
    47.                     vis[en]=1;
    48.                     qu.push(en);
    49.                 }
    50.             }
    51.         }
    52.     }
    53.     return 1;
    54. }
    55. void solve()
    56. {
    57.     memset(h,-1,sizeof h);
    58.     int m,u,v;
    59.     double c1,c2;
    60.     cin>>n>>m;
    61.     while(m--)
    62.     {
    63.         cin>>c1>>u>>c2>>v;
    64.         add(u,v,log(c2/c1));
    65.     }              
    66.     double l=0.0,r=1.0;
    67.     for(int i=0;i<=100;i++)
    68.     {
    69.         double mid=(l+r)/2;
    70.         if(check(mid))
    71.             l=mid;
    72.         else
    73.             r=mid;
    74.     }
    75.     cout<setprecision(10)<
    76.     return ;
    77. }
    78. signed main()
    79. {
    80.     cin.tie(0);
    81.     cout.tie(0);
    82.     ios::sync_with_stdio(0);
    83.     solve();
    84.     return 0;
    85. }

    G.Link with Monotonic Subsequence(构造,签到)

    思路:把数组分块,每一块内保证递增,然后每一开之间保证递减即可.当两者分块接近于\sqrt{n}的时候对于结果的贡献就会更小.比如(1-9),我们分成三块1,2,3   4,5,6    7,8,9,然后把这三块倒序排列:

    7,8,9,4,5,6,1,2,3.此时答案最小.

    AC code:

    1. #include
    2. using namespace std;
    3. struct node
    4. {
    5.     int l,r;
    6. };
    7. vectorve;
    8. void solve()
    9. {
    10.     ve.clear();
    11.     int n;
    12.     cin>>n;
    13.     for(int i=1;i<=n;i++)
    14.     {
    15.         int k=n/i+(n%i!=0);
    16.         if(i
    17.             continue;
    18.         for(int j=1;j<=n;j+=k)
    19.             ve.push_back({j,min(n,j+k-1)});
    20.         for(int j=ve.size()-1;j>=0;j--)
    21.         {
    22.             for(int k=ve[j].l;k<=ve[j].r;k++)
    23.             {
    24.                 cout<" ";
    25.             }
    26.         }
    27.         cout<
    28.         break;
    29.     }
    30.     return ;
    31. }
    32. signed main()
    33. {
    34.     cin.tie(0);
    35.     cout.tie(0);
    36.     ios::sync_with_stdio(0);
    37.     int t;
    38.     cin>>t;
    39.     while(t--)
    40.        solve();
    41.  
    42.     return 0;
    43. }

    H.Take the Elevator(模拟,贪心)

    思路:n个人,一个电梯,电梯最多容纳m个人,楼高k.

    我们可以把每个人上楼下楼的操作分成两类,然后都看成下楼的操作.然后进行模拟,从最高处向下走.当遇到一个区间的上端点,(把那个上下楼操作看成一个区间)就说明此时需要上来一个人.下端点就看成电梯上要下一个人.我们就记上人为+1,下人为-1.每个点就会存在一个值,再把这些值按照序号进行排序.从最高处往下遍历.当同一个点有上下人多个操作时,先下人在上人.

    当到某个点时,电梯上的人超过了上限,那么就需要在这个高度的点在开一个电梯.那么我们把对于上升下降处理的两种情况.因为我们每次坐电梯都有上升下降两种操作,那么每次我们之前储存的上升下降的电梯楼层进行两两匹配,然后每次取能到的最高点,计算要经过的层数即可.

    1. #include
    2. #define int long long
    3. using namespace std;
    4. struct node
    5. {
    6.     int id,val;
    7. };
    8. bool cmp(node a,node b)
    9. {
    10.     if(a.id!=b.id)
    11.         return a.id>b.id;
    12.     else
    13.         return a.val
    14. }
    15. vectorup,down;
    16. vector<int>ans_up,ans_down;
    17. void solve()
    18. {
    19.     int x,y,n,m,k;
    20.     cin>>n>>m>>k;
    21.     for(int i=1;i<=n;i++)
    22.     {
    23.         cin>>x>>y;
    24.         if(x
    25.         {
    26.             up.push_back({x,-1});
    27.             up.push_back({y,1});
    28.         }
    29.         else if(x>y)
    30.         {
    31.             down.push_back({x,1});
    32.             down.push_back({y,-1});
    33.         }
    34.     }
    35.     sort(up.begin(),up.end(),cmp);
    36.     sort(down.begin(),down.end(),cmp);
    37.  
    38.     int cnt=0;
    39.     for(int i=0;isize();i++)
    40.     {
    41.         cnt+=up[i].val;
    42.         if(cnt>ans_up.size()*m)
    43.             ans_up.push_back(up[i].id);
    44.     }
    45.     cnt=0;
    46.     for(int i=0;isize();i++)
    47.     {
    48.         cnt+=down[i].val;
    49.         if(cnt>ans_down.size()*m)
    50.             ans_down.push_back(down[i].id);
    51.     }
    52.  
    53.     int maxx=max(ans_up.size(),ans_down.size());
    54.     while(ans_up.size()
    55.         ans_up.push_back(0);
    56.     while(ans_down.size()
    57.         ans_down.push_back(0);
    58.     int ans=0;
    59.     for(int i=0;i
    60.     {
    61.         ans+=2*(max(ans_up[i],ans_down[i])-1);
    62.     }
    63.     cout<
    64.     return ;
    65. }
    66. signed main()
    67. {
    68.     cin.tie(0);
    69.     cout.tie(0);
    70.     ios::sync_with_stdio(0);
    71.     solve();
    72.     return 0;
    73. }

    J.Link with Arithmetic Progression(数学,线性回归方程)

    直接高中考点.

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N =5e5+10,mod=998244353;
    5. int read() 
    6. {
    7.     int x=0,f=1;
    8.     char c=getchar();
    9.     while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    10.     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    11.     return x*f;
    12. }
    13. int arr[100005];
    14. void solve()
    15. {
    16.     int n;
    17.     double ans=0,xy=0.0,x2=0.0;
    18.     n=read();
    19.     double avgx=0.0,avgy=0.0;
    20.     for(int i=1;i<=n;i++)
    21.     {
    22.         arr[i]=read();
    23.         avgx=avgx+i;
    24.         avgy=avgy+arr[i];
    25.     }
    26.     avgx/=n;
    27.     avgy/=n;
    28.     for(int i=1;i<=n;i++)
    29.     {
    30.         double ax=i-avgx,ay=arr[i]-avgy;
    31.         xy=xy+ax*ay;
    32.         x2=x2+ax*ax;
    33.     }
    34.     double k=xy/x2;
    35.     double b=avgy-k*avgx;
    36.     for(int i=1;i<=n;i++)
    37.     {
    38.         ans+=(i*k+b-arr[i])*(i*k+b-arr[i]);
    39.     }
    40.     printf("%.8lf\n",ans);
    41.     return ;
    42. }
    43. signed main()
    44. {
    45.     int t;
    46.     t=read();
    47.     while(t--)
    48.         solve();
    49.     return 0;
    50. }

    K.Link with Bracket Sequence I(括号匹配,dp)

    思路:f(i,j,k)的含义是原串长度为j,和子串相匹配的长度为i,此时原串左括号比右括号多k的方案的总数.

    详细思路在注释里:

    1. #include
    2. #define int long long
    3. using namespace std;
    4. const int N =5e5+10,mod=1e9+7;
    5. int f[210][210][210];
    6. /*
    7. 三维状态,第三维表示此时左括号比右括号多k个
    8. 状态转移方程是:
    9. 当当前的字符串遍历到s[j]=='('时
    10. f[i][j][k]由下面两个状态转移过来
    11. (1)f[i-1][j-1][k-1] 和原串匹配成功,j比原来+1,当前原串此处为'(',但是原串之前要比
    12. 此时的原串少一个'(',所以原来k的要小1
    13. (2)f[i-1][j][k+1]   和原串匹配失败,j不变,原串此时是')',同理,之前比现在多一个'(',
    14. 所以k要大1
    15. 同理
    16. 当当前的字符串遍历到s[j]==')'时
    17. f[i][j][k]由下面两个状态转移过来
    18. (1)f[i-1][j][k-1] 和原串匹配失败,j不变,但是此时原串是'(',但是上一层比原串少一个'('
    19. ,所以原来k的要小1
    20. (2)f[i-1][j-1][k+1]   和原串匹配失败,原串此时是')',上一层比这一层多一个')',
    21. 所以k要大1
    22. 当当前的字符串遍历到s[j]==')'时
    23. */
    24. void solve()
    25. {
    26.     string s;
    27.     int n,m;
    28.     cin>>n>>m;
    29.     for(int i=0;i<=m+1;i++)
    30.         for(int j=0;j<=m+1;j++)
    31.             for(int k=0;k<=m+1;k++)
    32.                 f[i][j][k]=0;
    33.     cin>>s;
    34.     s=" "+s;
    35.     f[0][0][0]=1;
    36.     for(int i=1;i<=m;i++)
    37.     {
    38.         for(int j=0;j<=n;j++)
    39.         {
    40.             for(int k=0;k<=i;k++)
    41.             {
    42. //注意边界处理!
    43.                 if(j==0)
    44.                 {   
    45.                     if(k)
    46.                         f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1])%mod;
    47.                     f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
    48.                 }
    49.                 else
    50.                 {   
    51.                     if(s[j]=='(')
    52.                     {    
    53.                         if(k)
    54.                             f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k-1]+f[i-1][j][k+1])%mod;
    55.                         else
    56.                             f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
    57.                     }
    58.                     else
    59.                     {
    60.                         if(k)
    61.                             f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]+f[i-1][j-1][k+1])%mod;
    62.                         else
    63.                             f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;                    
    64.                     }
    65.                     
    66.                 }
    67.             }
    68.         }
    69.     }
    70.     cout<0]<
    71.     return ;
    72. }
    73. signed main()
    74. {
    75.     cin.tie(0);
    76.     cout.tie(0);
    77.     ios::sync_with_stdio(0);
    78.     int t;
    79.     cin>>t;
    80.     while(t--)
    81.        solve();
    82.     return 0;
    83. }

    L.Link with Level Editor I

    思路:用dp写,详细思路见代码(有点抽象):

    1. #include 
    2. using namespace std;
    3. signed main() {
    4.     cin.tie(nullptr)->sync_with_stdio(false);
    5.     int n, m;
    6.     cin >> n >> m;
    7.     vector<int> f(m + 1), p(m + 1);
    8.     //p为上一层的情况,也就是上一层到达下标的位置的最近世界编号
    9.     //f用于转移上一层的情况,(且保证只走一步或者不走,所以还要把f的值赋给p)
    10.     int ans =  0x3f3f3f3f;
    11.     for (int i = 1; i <= n; i++) {
    12.         p[1] = i;
    13.         //如果在第i个世界从1出发
    14.         int k;
    15.         cin >> k;
    16.         for (int j = 1; j <= k; j++) {
    17.             int x, y;
    18.             cin >> x >> y;
    19.             f[y] = max(f[y], p[x]);
    20. //保持不动或者走一步
    21.             if (f[m])ans = min(ans, i - f[m] + 1);     
    22. //f保存的就是从某个世界的1号节点能到达当前节点,存的就是这个出发世界的编号
    23. //所以当f的值存在时,就直接相减求出
    24.         }
    25.         p=f;
    26.         //到达下一层,f作为从p更新而来的下一层,到达下一层循环时就作为了新的上一层
    27.     }
    28.     if (ans >= 0x3f3f3f3f)
    29.         cout << -1 << endl;
    30.     else
    31.         cout << ans << endl;
    32.  
    33.     return (0 ^ 0);
    34. }

  • 相关阅读:
    coverity工具 代码审计
    接口的触发形式类型有哪些？
    极速视觉：揭秘YOLO如何革新目标检测速度
    项目经理如何去拆分复杂项目？
    我的大二web课程设计 使用HTML做一个简单漂亮的页面（纯html代码）
    Java8新特性stream和parallelStream有什么区别
    给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
    Kotlin语言实现单击任意TextVIew切换一个新页面，并且实现颜色变换
    驱动开发day8
    Flink中的时间和窗口操作
  • 原文地址：https://blog.csdn.net/qq_49593247/article/details/126020692