2021年暑假ACM集训队模拟赛第4场——题解

妖狐艹你老母 2022-09-04 07:56 142阅读 0赞

### 目录 ###

*  A 山峦叠嶂
 *  B 重叠正方形
 *  C 一群X星人
 *  D X星群岛 （MST，最小生成树模板题）
 *  E X星人的飞行设备（复杂一点的DP）
 *  F X星人的救援
 *  G 最长回文子串
 *  H DNA序列拼接
 *  I 防水板砖（搜索，DFS）
 *  J 黑白树（比较复杂一点的数据结构题，Tree 待补）

# A 山峦叠嶂 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]

> 样例输入 Copy  
> 5  
> 1265 2368 3474 2170 3982

> 样例输出 Copy  
> 1

代码：

#include<bits/stdc++.h>
     
    using namespace std;
    int a[100010];
    int dp[100010];
     
    int main(){ 
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
     
        int ma=0;
        for(int i=1;i<=n;i++){ 
            for(int j=i-1;j>=0;j--){ 
                if(a[j]<a[i]){ 
                    dp[i]=max(dp[j]+1,dp[i]);
                    ma=max(ma,dp[i]);
                    //cout<<dp[i]<<" ";
                    //break;
                }
            }
        }
     
        cout<<n-ma<<endl;
     
     
        return 0;
    }

# B 重叠正方形 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 1]

> 样例输入 Copy  
> 0 0 2  
> 1 1 2

> 样例输出 Copy  
> 1

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
     
    int main(){ 
        int x1,y1,r1;
        int x2,y2,r2;
     
        while(cin>>x1>>y1>>r1){ 
            cin>>x2>>y2>>r2;
            double mi=min(r1,r2);
            double num=min((r1+r2)/2.0-(double)fabs(x1-x2),mi);
            //cout<<"x="<<num<<endl;
            if(num<=0) num=0;
     
     
            num*=min((r1+r2)/2.0-(double)fabs(y1-y2),mi);
            //cout<<"y="<<min((r1+r2)/2.0-(double)fabs(y1-y2),mi)<<endl;
            if(num<=0) num=0;
     
            double nu=(double)min(r1,r2);
            num=min(nu*nu,num);
     
            printf("%.0lf\n",num);
        }
     
        return 0;
    }

# C 一群X星人 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 2]

> 样例输入 Copy  
> 5  
> 10 -5 8 -4 2

> 样例输出 Copy  
> 16

代码：

#include<bits/stdc++.h>
     
    using namespace std;
    int a[100010];
    int dp[1010][1010];
     
    int main(){ 
        int n,ma=0;
        cin>>n;
     
        for(int i=1;i<=n;i++) cin>>a[i];
     
        int num=0;
        for(int i=1;i<=n;i++){ 
            dp[i][i]=a[i];
            for(int j=i+1;j<=n;j++){ 
                dp[i][j]+=dp[i][j-1]+a[j];
                ma=max(ma,dp[i][j]);
                //cout<<dp[i][j]<<" ";
            }
            //cout<<endl;
            num+=a[i];
        }
     
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<i;j++){ 
                ma=max(dp[i][n]+dp[1][j],ma);
            }
        }
     
     
        cout<<ma<<endl;
     
        return 0;
    }

# D X星群岛 （MST，最小生成树模板题） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 3]

> 样例输入 Copy  
> 2  
> 3 3 400  
> 1 2 200  
> 1 3 300  
> 2 3 500  
> 3 3 400  
> 1 2 500  
> 1 3 600  
> 2 3 700

> 样例输出 Copy  
> Yes  
> No

我这道题一直Wa，补题的时候才发现，m条路径，我居然用的n遍历的。。。哭了。。。

代码：

#include<bits/stdc++.h> //AC:18%
     
    using namespace std;
    int n,m,k,b;
    int vis[110];
     
    int fin(int x){ 
        if(vis[x]!=x) vis[x]=fin(vis[x]);
        return vis[x];
    }
     
    int main(){ 
        int t;
        cin>>t;
        while(t--){ 
            cin>>n>>m>>k;
            for(int i=0;i<=n;i++) vis[i]=i;
     
            for(int i=0;i<m;i++){ 
                int x,y,h;
                cin>>x>>y>>h;
                if(h<=k){ 
                    if(fin(x)!=fin(y)){        //!
                        vis[fin(x)]=vis[fin(y)];
     
                    }
                }
            }
     
            int num=0;
            for(int i=1;i<=n;i++){ 
                if(vis[i]==i) num++;
            }
            if(num==1)
                //cout<<num<<endl;
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
     
        return 0;
    }

# E X星人的飞行设备（复杂一点的DP） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 4]

> 样例输入 Copy  
> 1 1 1  
> 100 200 300  
> 2  
> 2000 3000

> 样例输出 Copy  
> 8

**思路：**

> 看了大佬的代码，我觉得题意是：每条生产线可以制作A,B,C的零件，但是能制作多少是不确定的，我们得合理利用生产线时长，达到组合的设备数目最多的目的，当然其中每条生产线可能最后会浪费一些时间（剩余时间不足以生产任意一种零件的情况）

大佬的代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 5]

代码：

#include<bits/stdc++.h>
    
    using namespace std;
    int dp[105][105][105],w[105];
    
    int main(){ 
        int x,y,z,a,b,c,m;
        memset(dp,-1,sizeof(dp));     //dp全初始化为-1
        dp[0][0][0]=0;
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,  &a,&b,&c,  &m);
        
        int mi=min(100/x,min(100/y,100/z));       //mi表示最理想（零件都能有100个）情况最多可以做成设备数量
        
        for(int i=1;i<=m;++i)scanf("%d",&w[i]);
        
        for(int i=1;i<=m;++i){             //创建dp 用到前 i 台设备
          for(int j=0;j<=mi*x;++j){              //做 j 个A零件
             for(int k=0;k<=mi*y;++k){           //做 k 个B零件
                    
                for(int jj=0;jj<=j;++jj){     //少做 jj个A零件
                   for(int kk=0;kk<=k;++kk){     //少做 kk个B零件
                        
                      if(dp[i-1][j-jj][k-kk]!=-1&&w[i]>=jj*a+kk*b){       //判断第 i个机器工作时长是不是多于预留给A,B零件的时长
                         if(dp[i][j][k]>=mi*z){    //如果当前dp的数量大于预测的C零件最大数量，就可以直接结束本次遍历了
                            jj=j+1;   //连跳两个for循环
                            break;
                         }
                         
                         //dp的含义：在前 i个机器情况下，制作 j个A零件和 k个B零件之后，还能做多少个C零件。
                         dp[i][j][k]=max(dp[i][j][k], dp[i-1][j-jj][k-kk]+(w[i]-a*jj-b*kk)/c);
                         //前i-1个机器，少做jj个A零件和kk个B零件时可以生产出的C零件个数，加上节约下来的时间全做C零件的个数。
                      
                      }
                   
                   }
                }
             
             }
          }
       }
       
       int ans=0;
       for(int i=0;i<=mi*x;++i){ 
          for(int j=0;j<=mi*y;++j){ 
             ans=max(ans,min(i/x,min(j/y,dp[m][i][j]/z)));
          }
       }
       
       printf("%d\n",ans);
    }

# F X星人的救援 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 6]

> 样例输入 Copy  
> 2  
> 3 33 450  
> 5 7 8  
> 1 2 4  
> 4 5 7  
> 3 50 3  
> 0 60 -1  
> 60 0 100  
> \-1 100 0

> 样例输出 Copy  
> Yes  
> No

代码：

#include<bits/stdc++.h>
     
    using namespace std;
    int n,m,k,fl;
    int a[110][110],ma[110];
     
    void dfs(int x,int nu){ 
        if(nu>m) return ;
        if(x==n){ 
            fl=1;
            return ;
        }
     
        for(int i=2;i<=n;i++){ 
            if(ma[i]==0){ 
                ma[i]=1;
                dfs(i,nu+a[x][i]);
                ma[i]=0;
                if(fl==1) return;
            }
        }
    }
     
    int main(){ 
        int t;
        cin>>t;
        while(t--){ 
            cin>>n>>m>>k;
            m=m*k;
            fl=0;
            for(int i=1;i<=n;i++){ 
                ma[i]=0;
                for(int j=1;j<=n;j++){ 
                    cin>>a[i][j];
                    if(a[i][j]==-1) a[i][j]=0x3f3f3f;
                }
            }
     
            if(a[1][n]<=m) cout<<"Yes"<<endl;
     
            else{ 
                ma[1]=1;
                dfs(1,0);
                if(fl==1) cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
     
        }
     
        return 0;
    }

# G 最长回文子串 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 7]

> 样例输入 Copy  
> DAB*B*ACD

> 样例输出 Copy  
> 6

代码：

#include<bits/stdc++.h>
     
    using namespace std;
     
    int main(){ 
        string a;
        cin>>a;
        int n=a.size();
        int ma=1;
     
        int fl=0;
        for(int i=0;i<n;i++){ 
            int nu=1;
            for(int j=1;j<=i&&j<n-i;j++){ 
                if(a[i-j]==a[i+j]||a[i-j]=='*'||a[i+j]=='*'){ 
                    nu+=2;
                }
                else break;
            }
            ma=max(nu,ma);
     
            nu=0;
            for(int j=1;j<=i+1&&j<n-i;j++){ 
                if(a[i-j+1]==a[i+j]||a[i-j+1]=='*'||a[i+j]=='*'){ 
                    nu+=2;
                }
                else break;
            }
            ma=max(nu,ma);
        }
     
        cout<<ma<<endl;
     
        return 0;
    }

# H DNA序列拼接 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 8]

> 样例输入 Copy  
> 4  
> AGCT  
> GCTAA  
> TAACG  
> CTAACGGCG

> 样例输出 Copy  
> 11

> 提示  
> 在样例中，“AGCT”和“GCTAA”可拼接为“AGCTAA”；“AGCTAA”和“CTAACGGCG”可拼接为“AGCTAACGGCG”，长度为11。

代码：

#include<bits/stdc++.h>
     
    using namespace std;
    int n;
    string a[15];
    int dp[15][15];
    int mi,m[15],len;
     
    void bfs(int x,int num){ 
        if(num>mi){ 
            mi=num;
        }
     
        for(int i=0;i<n;i++){ 
            if(m[i]==0&&dp[x][i]!=0){ 
                m[i]=1;
                bfs(i,num+a[i].size()-dp[x][i]);
                m[i]=0;
            }
        }
     
    }
     
    int main(){ 
        cin>>n;
        getchar();
        for(int i=0;i<n;i++) cin>>a[i];
     
        for(int i=0;i<n;i++){ 
            len+=a[i].size();
            string b=a[i].substr(0,3);
            for(int j=0;j<n;j++){ 
                if(i==j){ 
                    //cout<<dp[i][j]<<" ";
                    continue;
                }
                int nu=3;
                //cout<<a[j].find(b)<<"+"<<a[j].size()<<" ";
                if(a[j].find(b)<a[j].size()){ 
                    int le=a[j].find(b),k=2;
                    //cout<<"le="<<le;
                    for(k=k+1;k+le<a[j].size()&&k<a[i].size();k++){ 
                        if(a[j][le+k]!=a[i][k]) break;
                    }
                    //cout<<a[i]<<" "<<a[j]<<endl;
     
                    if(k+le==a[j].size()){ 
                        dp[i][j]=k;
                        //cout<<" k="<<k<<endl;
                    }
                }
                //cout<<dp[i][j]<<" ";
            }
            //cout<<endl;
        }
     
        mi=0;
        for(int i=0;i<n;i++){ 
            m[i]=1;
            bfs(i,a[i].size());
            m[i]=0;
        }
     
        cout<<mi<<endl;
     
        return 0;
    }

# I 防水板砖（搜索，DFS） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 9]

> 样例输入 Copy  
> 4 4  
> 2 3 5 1  
> 4 1 2 3  
> 1 5 4 2  
> 1 2 2 2

> 样例输出 Copy  
> 1

思路：

> 这一题我觉得最难的是读懂题意，虽然我说服了自己这个题的意思是这个，但是感觉还可以理解成其他意思  
> 题目的意思就是找到有多少个水坑，但在寻找过程中，相邻（上下/左右相邻）的小水坑才能合并。这道题的思路就是先找到第一个小水坑，条件是上下左右的数量都大于它。再根据找到的小水坑去找可以合并的其他小水坑，这个时候其他小水坑的条件就是上下左右的数量有三边是大于它就可以了（因为第一个找到的小水坑是相邻并且小于第二个的），依次类推dfs

这个时候就发现有个测试数据是这样的：

> 4 5  
> 0 5 6 5 0  
> 5 2 2 3 5  
> 5 2 2 4 5  
> 0 6 6 5 0

> 输出是：0

是的，这个代码判断（2，2）（2，2）是不算水坑的。。我也不知道题目要求是算还是不算  
但题目过了呀！那就不深究了

代码：

#include<bits/stdc++.h>
    
    using namespace std;
    int n,m,num;
    int vis[110][110];
    int a[110][110];
    int dx[5]={ 0,1,-1,0};
    int dy[5]={ 1,0,0,-1};
    
    int check(int x,int y){ 
        int nu=0;
        for(int i=0;i<4;i++){ 
            int xx=x+dx[i],yy=y+dy[i];
            if((xx>0&&xx<=n&&yy>0&&yy<=m)&& !vis[xx][yy] &&a[xx][yy]>a[x][y])
                nu++;
        }
        return nu;
    }
    
    void dfs(int x,int y){ 
    
        for(int i=0;i<4;i++){ 
            int xx=x+dx[i],yy=y+dy[i];
            if((xx>0&&xx<=n&&yy>0&&yy<=m)&& !vis[xx][yy] && check(xx,yy)>=3){ 
                vis[xx][yy]=1;
                dfs(xx,yy);
            }
        }
    
    }
    
    int main(){ 
        scanf("%d%d",&n,&m);
        num=0;
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<=m;j++){ 
                scanf("%d",&a[i][j]);
            }
        }
    
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<=m;j++){ 
                if(check(i,j)==4){ 
                    vis[i][j]=1;
                    dfs(i,j);
                    num++;
                }
            }
        }
    
        cout<<num<<endl;
    
        return 0;
    }

# J 黑白树（比较复杂一点的数据结构题，Tree 待补） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 10]

> 样例输入 Copy  
> 7  
> 1 2 0  
> 3 1 1  
> 2 4 0  
> 5 2 0  
> 6 3 1  
> 5 7 1

> 样例输出 Copy  
> 1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70]: /images/20220829/a7a3c0b269544bb29d7f7d368ca5fe86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 1]: /images/20220829/142e890425c0489c801d75e81da39f3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 2]: /images/20220829/a1a5ba278c714a93b83f6a114c0f1fcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 3]: /images/20220829/4e1e7cf62e8e453d8a3ecc3b4b76fb78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 4]: /images/20220829/b79eb1da3be04e9db114d6cfcdb8ab08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 5]: /images/20220829/7bfd3c95b0bf4c24bd7f0cef17abc130.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 6]: /images/20220829/58722e84d1ba4d828bf9d223e86d70e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 7]: /images/20220829/0469cb367a094859ab9deacd75b90bf4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 8]: /images/20220829/0eabe9481f3e4d7fbf1d8dca5d0f66e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 9]: /images/20220829/f830f69d4c7d45ff9ce84615244e9eb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyM18yMw_size_16_color_FFFFFF_t_70 10]: /images/20220829/0c96d0f162e54caa98ead0e534ee84bc.png