01-08 23:10 河南科技学院 C++ 发布于河南

关注

题解 | #选拔赛题解#

ACM?acm？

https://ac.nowcoder.com/acm/contest/73229/A

在此特别感谢牛客技术和各大高校对本次比赛的大力支持~🤩🤩🤩🥰🥰🥰

本次比赛整体难度符合预期通过率，没有很明显的锅，所以还是比较成功的比赛。

题目的难度是按照升序排列，所以也算是降低了一层难度。

祝贺各位通过选拔的同学进入寒假集训！！！

以下是出题人写的题解，不会的题可以参考一下，由于个人代码风格习惯，并未格式化~

赛题链接：(0条未读通知) 河南科技学院寒假集训选拔赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

查看密码：20240108

A.ACM？acm？⭐

由于可以重新排列字母，并且不区分大小写，所以只需要统计a和A，c和C，m和M的数量，分别计为a_cnt,c_cnt,m_cnt。然后3个的数的最小值即可，最为签到题，也是很友善。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int a=0,c=0,m=0;
    for(int i=0;i<s.size();i++){
       if(s[i]=='a'||s[i]=='A') a++;
       else if(s[i]=='c'||s[i]=='C') c++;
       else if(s[i]=='m'||s[i]=='M') m++;
    }
    cout<<min({a,c,m});
    return 0;
}

B：Happy or unhappy？难度：⭐⭐

关键词：快速幂，快速幂运用或__int128_t

我们可以看到数据的范围很大，n最大到了10^18^,而且还有取模，所以让人很容易想到使用快速幂。这道题的思路其实比较简单:总共有m^n^种方案(每个格子都可以从m种颜色中任意取一种)，让B神喜欢的方案有C(m,1)(m-1)^(n-1)^种(因为第一个格子选了一种后，第二个格子有m-1种选法，第三个格子有m-1种选法……第n个格子有m-1种选法，所以是(m-1)^(n-1)^,而第一个格子有m种选法，所以根据乘法原理，答案是m^n^-m(m-1)^(n-1)^（得到的答案再取模即可）,由于此题取模数特意设置较大，所以可能爆longlong，所以所有相乘的地方需要使用快速幂的加法变换才可以通过.

总时间复杂度

O(nlog(n)log(n))

或者也可以直接使用__int128_t ,时间复杂度，这里由于篇幅限制，不做展示。

O(nlog(n))

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define i64 long long 
#define endl "\n"
const i64 mod=100000000003;
i64 ksm_add(i64 a,i64 b){
    i64 res=0;
    while(b){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b=b>>1;
    }
    return res;
}
i64  ksm_mul(i64 a,i64 b){
    i64 res=1;
    while(b){
        if(b&1) res=ksm_add(res,a)%mod; 
        a=ksm_add(a,a)%mod; 
        b=b>>1;} 
    return res;
}
void solve(){
    i64 n,m;
    cin>>n>>m;
    i64 ans=ksm_mul(m,n)%mod-ksm_add(m,ksm_mul(m-1,n-1))%mod+mod;
    ans=ans%mod;
    cout<<ans<<endl;
}
int main(){
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int t=1;cin>>t;
     while(t--){
        solve();
     }
    return 0;
}

C:TieTie! 难度：⭐⭐

关键词：单调栈

我们可以假设每个位置都需要贴壁画，那么最多需要n张。对于任意两个位置，如果高度不一样，那么必然需要两张壁画，而对于两个相同高度的位置则只需要同一张。故需要找出第i张前面的前i-1张中是否存在a[j]==a[i]（j∈[1,i-1])即可，前提是[j,i）中的山比第i座山都要高才可以，否则必然需要另外一张，因为中途高度降低，无法左右连续。对于存储前i-1个高度，我们可以使用单调栈或者队列，或者数组都可以解决。这样便可以找出重复高度的壁画cnt，最后n-cnt就是答案。

每个山的高度最多被数组和单调栈各遍历一次,所以时间复杂度为

O(n)

参考代码：

#include<bits/stdc++.h> 

using namespace std;
#define i64 long long 
int main( )
{

    int n;
    cin>>n;
    vector<i64>w(n+1),h(n+1);
    for(int i=1;i<=n;i++){
         cin>>w[i]>>h[i];
    }
    i64 ans=0;
    stack<i64>q;
    for(int i=1;i<=n;i++){
        while(q.size()&&q.top()>=h[i]){
              if(q.top()==h[i]) ans++;
              q.pop();
        }
        q.push(h[i]);
    }
    cout<<n-ans;
   return 0;
}

D：Pass the difficulty! 难度：⭐⭐⭐

关键词：BFS,状态更新，最短路

不难看出这是一个BFS的题。只需要从坐标（1，1）开始，然后把（1，1）的初始状态入队列，依次判断其上下左右的状态和当前队首的状态，相同的时候判断+2，不同的时候判断+1，然后进行更新到达（nx，ny）的最短时间，如果下一个位置的最短时间可以更新，则入下一个点的可到达状态(和当前队首相反的状态，因为相反状态才可以到达）。最后终点的最短时间就是终点状态0和1的最小值。

时间复杂度

O(n*m)

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define i64 long long 
i64 d[1001][1001][2];
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<char>>a(n+1,vector<char>(m+1));
    for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++) 
            cin>>a[i][j];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<2;k++) d[i][j][k]=1e18;

    auto bfs=[&](int x,int y)->void{
        queue<array<int,3>>q;
        q.push({x,y,a[x][y]-'0'});
        d[x][y][a[x][y]-'0']=0;
        int z;
        while(!q.empty()){
              auto t=q.front();
              q.pop();
              int nx,ny;
              x=t[0],y=t[1],z=t[2];
              //上
              nx=x-1,ny=y;
              if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
               int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
               if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
               q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
               d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
               }  
              }
              //下
              nx=x+1,ny=y;
              if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
               int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
               if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
               q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
               d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
               }  
              }
              //左
              nx=x,ny=y-1;
              if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
               int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
               if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
               q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
               d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
               }  
              }
              //右
              nx=x,ny=y+1;
              if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
               int D=d[x][y][z]+1+(a[nx][ny]-'0'==z?1:0);
               if(D<d[nx][ny][(a[nx][ny]-'0'==z)?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]){
               q.push({nx,ny,a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')});
               d[nx][ny][a[nx][ny]-'0'==z?(1^(a[nx][ny]-'0')):(a[nx][ny]-'0')]=D;
               }  
              } 
        }
    };
    bfs(1,1);
    cout<<min(d[n][m][0],d[n][m][1])<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--){
        solve();
    }

    return 0;
}

E：How much time？难度：⭐⭐⭐

关键词：前缀和，树状数组，离散化，二分

对于区间和

\sum_{i=l}^{r}a[i]≥X

可以转化为sum[r]-sum[l-1]≥x，如果要快速查询以r为结尾的区间有多少满足条件的区间，那么公式可以转化为sum[r]-x≥sum[l-1],这时只需要找出在r的左边小于等于sum[r]-x的区间前缀和数量即可。由于有负数，所以前缀和不单调，故使用树状数组来维护r左边小于等于sum[r]-x的前缀和数量，统计r左边小于等于sum[r]-x的前缀和出现的次数，同时，前缀和的值可能很大，所以要使用离散化，把数组降为数组可容纳的范围.

总时间复杂度

O(nlog(n)log(n))

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define i64 long long 
#define endl "\n"
int n;
i64 tree[N];
vector<i64>all;
i64 lowbit(i64 x){
    return x&-x;
}
void add(int x){
    for(int i=x;i<all.size();i+=lowbit(i)) tree[i]++;
}
i64 sum(int x){
     i64 ans=0;
    for(int i=x;i;i-=lowbit(i)) ans=ans+tree[i];
    return ans;
}
i64 find(i64 x){
     int l=0,r=all.size()-1;
    while(l<r){
         int mid=l+r>>1;
        if(all[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l+1;
}
void solve(){
     i64 x;
     cin>>n>>x;
     vector<i64>a(n+1),s(n+5);
     for(int i=1;i<=n;i++){
         cin>>a[i];
         s[i]=s[i-1]+a[i];
     }
    for(int i=0;i<=n;i++){ 
        all.push_back(s[i]-x);
        all.push_back(s[i]);
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    
    i64 ans=0;
    add(find(0));
    for(int i=1;i<=n;i++){
          ans=ans+sum(find(s[i]-x));
          add(find(s[i]));
    }
    cout<<ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--){
        solve();
    }
 
    return 0;
}

F：Attribute M 难度：⭐⭐⭐

关键词：线性DP

考虑DP。

用数组f[i] [j]表示到第i个数取模之后余数为j的情况。

首先预处理for(int i=1;i<=n;i++) f[i] [a[i]%m]=a[i];

对于每个数只有两种情况，要么不要，要么要。

对于不要的情况可直接f[i] [j]=max(f[i] [j],f[i-1] [j]);

要的情况：分类讨论1.a[i]%m≤j和2.a[i]%m>j的情况。

可由上一层的j-a[i]%m最大值转移而来，举例当m=5,a[i]=2,j=4,由上一层的2转移过来，因为（2+2）%5==4，

if(f[i-1] [j-a[i]%m]!=0) f[i] [j]=max({f[i] [j],f[i-1] [j],f[i-1] [j-a[i]%m]+a[i]});

如果f[i-1] [j-a[i]%m]==0，说明上一层的取模数等于j-a[i]%m并没有情况，所以不能更新，只能选择不要此数。

2.可以上一层m+j-a[i]%m转移而来，举例当m=5,a[i]=4,j=2,由上一层的3转移过来，因为（4+3）%5==2，

if(f[i-1] [m+j-a[i]%m]!=0) f[i] [j]=max({f[i] [j],f[i-1] [j],f[i-1] [m+j-a[i]%m]+a[i]});

如果f[i-1] [m+j-a[i]%m]==0，说明上一层的取模数等于m+j-a[i]%m并没有情况，所以不能更新，只能选择不要此数。

时间复杂度

O(n*m)

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define i64 long long 
#define endl "\n"
void solve(){
     int n,m;
     cin>>n>>m;
     vector<i64>a(n+1);
     vector<vector<i64>>f(n+1,vector<i64>(m+1,0));
     for(int i=1;i<=n;i++){
         cin>>a[i];
     }
     f[0][0]=0;
     for(int i=1;i<=n;i++) f[i][a[i]%m]=a[i];
     for(int i=1;i<=n;i++){
          for(int j=0;j<m;j++){
             if(j>=a[i]%m){
                if(f[i-1][j-a[i]%m]!=0)
                   f[i][j]=max({f[i][j],f[i-1][j],f[i-1][j-a[i]%m]+a[i]});
                else
                    f[i][j]=max(f[i][j],f[i-1][j]);
             }
             else{
                 if(f[i-1][m+j-a[i]%m]!=0)
                   f[i][j]=max({f[i][j],f[i-1][j],f[i-1][m+j-a[i]%m]+a[i]});
                 else
                    f[i][j]=max(f[i][j],f[i-1][j]);
             }
          }
     }
     cout<<f[n][0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

G：Transporting watermelons 难度：⭐⭐⭐⭐

关键词：凸多边形，外接圆，抽屉原理，FFT

由切线性质可得，一个凸四边形是圆外切四边形当且仅当该四边形的对边之和相等。故问题转化为所给数列中是否存在四个不同的数 a，b，c，d使得a+b=c+d。这是抽屉原理经典模型，暴力枚举即可。作为选拔赛的中等题，为了让大家有一个友好的参赛体验，FFT也可以通过。

时间复杂度

O(max(ai))

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define i64 long long 
void solve(){
     int n;
     cin>>n;
     vector<i64>a(n+1);
     for(int i=1;i<=n;i++){
         cin>>a[i];
     }
     map<i64,i64>H;
     for(int i=1;i<=n;i++){
          for(int j=i+1;j<=n;j++){
               if(H[a[i]+a[j]]){
                    cout<<"YES";
                   return ;
               }
              H[a[i]+a[j]]=1;
          }
     }
     cout<<"NO";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--){
        solve();
    }
 
    return 0;
}

H：Set 难度：⭐⭐⭐⭐⭐

关键词：GCD，动态规划

此题难度较大，作为挑战题给出思路，代码

图片上传失败，请重新上传

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int mod=998244353;
int datas[maxn];
int a[maxn][101],n;
int f[maxn][101][101],C[101][101];
int g[maxn][101][101];
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=1ll*res*a%mod;
        }
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>datas[i];
    }
    sort(datas+1,datas+1+n);
    for(int i=1;i<=n;i++){
        a[i][0]=1;
        for(int j=1;j<=100;j++){
            a[i][j]=1ll*a[i][j-1]*datas[i]%mod;
        }
    }
    C[0][0]=1;
    for(int i=1;i<=100;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int x=0;x<=100;x++){
            for(int y=0;y<=100;y++){
                f[i][x][y]=f[i-1][x][y];
            }
        }
        for(int x=0;x<=100;x++){
            int d=gcd(x,a[i][1]);
            for(int j=0;j<=100;j++){
                for(int p=0;p<=j;p++){
                    f[i][d][j]+=1ll*C[j][p]*f[i-1][x][p]%mod*a[i][j-p]%mod;
                    f[i][d][j]%=mod;
                }
            }
        }
    }
    g[n+1][0][0]=1;
    for(int i=n;i>=1;i--){
        for(int x=0;x<=100;x++){
            for(int y=0;y<=100;y++){
                g[i][x][y]=g[i+1][x][y];
            }
        }
        for(int x=0;x<=100;x++){
            int d=gcd(x,a[i][1]);
            for(int j=0;j<=100;j++){
                for(int p=0;p<=j;p++){
                    g[i][d][j]+=1ll*C[j][p]*g[i+1][x][p]%mod*a[i][j-p]%mod;
                    g[i][d][j]%=mod;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<n;i++){
        int res1=0;
        for(int x=0;x<=100;x++){
            int d=gcd(x,a[i][1]);
            for(int p=0;p<=d;p++){
                res1+=1ll*C[d][p]*f[i-1][x][p]%mod*a[i][d-p]%mod;
                res1%=mod;
            }
        }
        int res2=0;
        for(int j=1;j<=100;j++){
            res2=(res2+g[i+1][j][j])%mod;
        }
        ans=(ans+1ll*res1*res2%mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}