牛客周赛 Round 18

A.游游的整数翻转

考察暴力模拟

我们直接按照题目意思，考虑数位很小直接用string然后转化即可

void solve()
{
    string s; cin>>s>>n;
    s=' '+s;
    int ans=0;
    for(int i=n;i>=1;i--) ans=ans*10+(s[i]-'0');
    for(int i=n+1;s[i];i++) ans=ans*10+(s[i]-'0');
    cout<<ans<<endl;
    return ;
}

B.游游的排列统计

考察暴力素数定义

我们可以发现数据范围特别小直接模拟全部结果即可，然后判断素数

int p[N];

bool check(int x){
    if(x==1) return 0;
    if(x==2) return 1;
    if(x%2==0) return 0;
    for(int i=3;i<=x/i;i+=2)
        if(x%i==0) return 0;
    return 1;
}

void solve()
{
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++) p[i]=i;
    
    do{
        int ok=1;
        for(int i=1;i<n;i++) if(check(p[i]+p[i+1])) ok=0;
        ans+=ok;
    }while(next_permutation(p+1,p+1+n));
    cout<<ans<<endl;
    return ;
}

C.游游刷题

考察简单%数知识

依照题目意思摸鱼并且有效的就一定是k的倍数才可以，我们优先把数变到k里面来对每一个数%k

之后相同的数带来的影响是一样的，接着除了0之外其他需要带来贡献一定是两个数之和==k这里需要注意如果恰好是一半的情况，考虑数据范围直接用mp然后考虑<=k/2的即可

map<int,int> mp;
int t,n,m;
int a[N];
void solve()
{
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        mp[x%m]++;
    }
    
    int ans=0;
    
    for(auto&[v,w]:mp){
        if(v==0){
            ans+=w;
            continue;
        }
        if(2*v==m){
            ans+=w/2;
        }    
        else{
            ans+=min(w,mp[m-v]);
            mp[m-v]=0;
        }
    }
    cout<<ans<<endl; 
    return ;
}

D.游游买商品

考察01背包简单变形

我们舍去半价这个操作得到的就是01背包，但是我们要考虑一个位置买了和没有买对它下一个位置是有影响的，所以我们不能使用优化了空间的01背包因为它丢失了很多信息，不妨定义这样定义状态dp[M][M][2][2];// 我这个位置买了没有 如果买了是不是半价的，这样如果是半价一定是上一个买了，我这个没买就是从上一个没买，全价买了，半价买了转移过来，符合所有的情况，注意我们开始的时候全部赋值为负数，然后从出发的位置为0即可

int a[N],b[N];
int dp[M][M][2][2];// 我这个位置买了没有 如果买了是不是半价的

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    
    
    int ans=0;
    
    memset(dp,-0x3f,sizeof dp);
    
    for(int i=0;i<=m;i++)
        dp[0][i][0][0]=0;
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j][0][0]=max({dp[i-1][j][0][0],dp[i-1][j][1][0],dp[i-1][j][1][1]});
            // 我这个没有买那就是从上一次没有买以及是半价买的
            if(j>=a[i]) dp[i][j][1][0]=max({dp[i-1][j-a[i]][0][0],dp[i-1][j-a[i]][1][0],dp[i-1][j-a[i]][1][1]})+b[i];
            if(j>=a[i]/2) dp[i][j][1][1]=dp[i-1][j-a[i]/2][1][0]+b[i];
        }
    }
    cout<<max({dp[n][m][1][1],dp[n][m][1][0],dp[n][m][0][0]})<<endl;
    return ;
}