牛客周赛 Round 19全部题解

A.小红的字符串大小写变换

本题考察简单模拟 我们只需要按照题目意思执行即可,可以使用toupper和tolower函数来帮助我们

void solve()
{
    cin>>n>>m;
    string s; cin>>s;
    for(int i=0;s[i];i++){
        if(i<m) s[i]=toupper(s[i]);
        else s[i]=tolower(s[i]);
    }
    cout<<s<<endl;
    return ;
}

B.小红杀怪

本题考察暴力枚举 我们可以发现题目有两种操作,同时范围很小考虑暴力枚举,对于选择两个选择我们可以固定一个选择来求另一个选择即可,然后按照题目意思处理,我们固定群体伤害,这样即使数据范围扩大我们也是o(n)

void solve()
{
    int a,b,x,y; cin>>a>>b>>x>>y;
    
    int ans=20;// 相对最大值
    for(int i=0;i<=20;i++){
        int aa=a-i*y,bb=b-i*y;
        int res=i;
        if(aa>0) res+=ceill(1.0*aa/x);
        if(bb>0) res+=ceill(1.0*bb/x);
        ans=min(ans,res);
    }
    cout<<ans<<endl;
    return ;
}

小红的元素分裂

考察简单dp?

1. 实现1

目标是全部变成1,所以我们是1的时候直接初始值为0即可,然后我们发现每一个数可以分裂为两个乘积为x的约数，然后我们直接枚举所有约数即可然后看哪一种情况最优即可

时间复杂度：n*sqrt(n)

void solve()
{
    cin>>n;
     
    memset(dp,0x3f,sizeof dp);
    dp[1]=0;
    for(int i=2;i<N;i++){
        dp[i]=dp[i-1]+1;
        for(int j=2;j<=i/j;j++){
            if(i%j==0){
                dp[i]=min(dp[i],dp[j]+dp[i/j]+1);
            }
        }
    }    
    int ans=0;
    while(n--){
        int x; cin>>x;
        ans+=dp[x];
    }
    cout<<ans<<endl;
     
    return ;

2. 实现2

我们可以采用记忆化搜索的方式每个点也只会走一次时间复杂度同上

int dfs(int x){
    int&v=dp[x];
    if(~v) return v;
    v=INF;
    v=min(v,dfs(x-1)+1);
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
             v=min(v,dfs(i)+dfs(x/i)+1);
        }
    }
    return v;
}
void solve()
{
    memset(dp,-1,sizeof dp);
    dp[1]=0;
    cin>>n;
    int ans=0;
    while(n--){
        int x; cin>>x;
        ans+=dfs(x);
    }
    cout<<ans<<endl;
     
    return ;
}

D.小红的扫雷游戏

考察暴力搜索以及题意理解 我们可以发现对于一个地方要填X是必须在所有的情况下都必须填X，这具有填X的唯一性,上面意思呢？也就是对于满足题目要求的可能有很多种情况比如

...
1.1
... 
的答案可以是
...
1.1
X.X 

也可以是
...
1X1
... 

也就是这样也是可以的
所有没有必须填X的地方

如果一个点是可能填下也可能不填X那就是.
如果不能填X那就是O

那么怎处理也就是我们找出所有情况来看一个点是不是只有一种情况即可

我们考虑收到影响的点只有在数字的9宫格内的点可以采取剪枝的做法只考虑这些点填X还是.

  for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(isdigit(s[i][j])){
                dian.push_back({i,j});
                for(int u=0;u<8;u++){
                    int x=i+dx[u],y=j+dy[u];
                    if(x>=1 &&x<=n &&y>=1 &&y<=n &&s[x][y]=='.'){
                        S.insert({x,y});
                    }
                }
            }
        }
    for(auto&v:S) res.push_back(v);

check函数

bool check(){
    for(auto&[i,j]:dian){
        int t=s[i][j]-'0',now=0;
        for(int k=0;k<8;k++){
            int a=dx[k]+i,b= dy[k]+j;
            if(a<1 || b<1 || a>4 || b> 4) continue;
            now+=s[a][b]=='X';
        }
        if(now!=t) return false;       
    } 
    return true;
}

然后暴搜

void dfs(int u){
    if(u==res.size()){
        if(!check()) return ;
        
        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
                if(!isdigit(s[i][j])){
                    if(s[i][j]=='X') yes[i][j].first=1;// 在满足要求的情况下是不是有多种可能
                    else yes[i][j].second=1;
                }
        return ;
    }
    auto [x,y]=res[u];
    s[x][y]='X';
    dfs(u+1);
    s[x][y]='.';
    dfs(u+1);
}

最后

int t,n=4,m;
char s[M][M];
set<PII> S;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
vector<PII> res;
vector<PII> dian;
bool st[M][M];
PII yes[M][M];

bool check(){
    for(auto&[i,j]:dian){
        int t=s[i][j]-'0',now=0;
        for(int k=0;k<8;k++){
            int a=dx[k]+i,b= dy[k]+j;
            if(a<1 || b<1 || a>4 || b> 4) continue;
            now+=s[a][b]=='X';
        }
        if(now!=t) return false;       
    } 
    return true;
}

void dfs(int u){
    if(u==res.size()){
        if(!check()) return ;
        
        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
                if(!isdigit(s[i][j])){
                    if(s[i][j]=='X') yes[i][j].first=1;
                    else yes[i][j].second=1;
                }
        return ;
    }
    auto [x,y]=res[u];
    s[x][y]='X';
    dfs(u+1);
    s[x][y]='.';
    dfs(u+1);
}
void solve()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
             cin>>s[i][j];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(isdigit(s[i][j])){
                dian.push_back({i,j});
                for(int u=0;u<8;u++){
                    int x=i+dx[u],y=j+dy[u];
                    if(x>=1 &&x<=n &&y>=1 &&y<=n &&s[x][y]=='.'){
                        S.insert({x,y});
                    }
                }
            }
        }
    for(auto&v:S) res.push_back(v);
    dfs(0);
    
    for(auto [i,j]:res){
        if(yes[i][j].first==1 &&yes[i][j].second==1) s[i][j]='.';
        else if(yes[i][j].first==1) s[i][j]='X';
        else s[i][j]='O';
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
           cout<<s[i][j];
        }
        cout<<endl;
    }
    return ;
}