当前位置：首页 > article >正文

牛客周赛 Round 65

article 2024/10/28 23:55:18

文章目录

- - 超市
  - - 思路：
    - Solved：
  - 雨幕
  - - 思路：
    - Solved：
  - 闺蜜
  - - 思路：
    - Solved：
  - 医生
  - - 思路：
    - Solved：
  - 降温（easy）
  - - 思路：
    - - Solved：
  - F-降温（hard）
  - - 思路：
    - Solved：

超市

思路：

签到题，哪个便宜就买哪个

Solved：

void solve()
{
	int n,a,b;cin>>n>>a>>b;
	cout<<n/min(a,b);
}

雨幕

思路：

数据范围很小，直接暴力每个点并判断即可

Solved：

void solve()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='*'&&a[i-1][j]=='*'&&a[i][j-1]=='*'&&a[i-1][j-1]=='*'){
				ans++;
			}
		}
	}
	cout<<ans;
}

闺蜜

思路：

读题发现每次都会拿当前最大的那个数，没换之前每组小红拿的数均为大的，若将小紫最小的和小红最大的比较，那么每组小紫的数就均为最大的了，因此，除了该数组中元素均相同，其余均为小紫win

Solved：

void solve()
{
	int n;cin>>n;
	map<int,int> mp;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		mp[x]++;
	}
	for(auto &s:mp){
		if(s.se==n){
			cout<<"draw"<<endl;
			return ;
		}
	}
	cout<<"yukari"<<endl;
}

医生

思路：

通过数据可得知，可以对每个病人暴力枚举所有药物，选出最优

可以通过dfs 构造每种药物选与不选的情况

若不选，则递归下一种药物

若选，则先将病人情况用该种药物恢复，再递归到下一种药物

直至病人痊愈，取最小值

Solved：

void dfs(string s,int index,int t)
{
    bool flag=1;
    for(int i=0;i<m;i++){
        if(s[i]=='1'){
            flag=0;
        }
    }
    //直至病人痊愈，取最小值
    if(flag){
        minx=min(minx,t);
        return ;
    }
    if(index>=k) return ;
    //若不选，则递归下一种药物
    dfs(s,index+1,t);
    //若选，则先将病人情况用该种药物恢复，递归到下一种药物
    for(int i=0;i<m;i++){
        if(s[i]=='1'&&b[index][i]=='1'){
            s[i]='0';
        }
    }
    dfs(s,index+1,t+1);
}
 
void solve()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>k;
    for(int i=0;i<k;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        minx=INT_MAX;
        dfs(a[i],0,0);
        if(minx==INT_MAX){
            cout<<"-1"<<endl;
        }else{
            cout<<minx<<endl;
        }
    }
}

降温（easy）

思路：

读题发现有天数气温未知，所以可通过构造未知气温达到最优的寒潮天数

顺序构造，可不考虑前面未知天数（因为前面未知天数会补上）

最大寒潮

顺序构造

如果是第一天，那么直接无脑最高气温
顺序遍历，肯定是优先比前一天降低x度
如果降低x度达不成寒潮（低于最低温度），无脑最高气温

最小寒潮

逆序构造

如果是最后一天，无脑最高温度，保证没有寒潮
逆序遍历，肯定是优先比后一天升温x-1度，保证没有寒潮
如果升高x-1度超过最高温度，设置为最高温度

Solved：

void solve()
{
    int n,x;cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==-999){
            st[i]=1;
        }
    }
    //最多
    for(int i=1;i<=n;i++){
        if(st[i]==1&&i==1){
            a[i]=50;
        }
        else if(st[i]==1&&a[i-1]-x>=-50){
            a[i]=a[i-1]-x;
        }else if (st[i]==1){
            a[i]=50;
        }
    }
    int mx=0;
    for(int i=1;i<=n-1;i++){
        if(a[i]-a[i+1]>=x){
            mx++;
        }
    }
    //最少
    for(int i=n;i>=1;i--){
        if(st[i]==1&&i==n){
            a[i]=50;
        }
        else if(st[i]==1&&a[i+1]+x<=50){
            a[i]=a[i+1]+x-1;
        }else if (st[i]==1){
            a[i]=50;
        }
    }
    int mi=0;
    for(int i=1;i<=n-1;i++){
        if(a[i]-a[i+1]>=x){
            mi++;
        }
    }
    cout<<mx<<" "<<mi<<endl;
}

F-降温（hard）

思路：

hard版是气温最大值和最小值改变，未知天气气温值改变，其余思路同easy

Solved：

void solve()
{
	int n,x;cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==-999999999){
			st[i]=1;
		}
	}
	//最多
	for(int i=1;i<=n;i++){
		if(st[i]==1&&i==1){
			a[i]=num1;
		}
		else if(st[i]==1&&a[i-1]-x>=num2){
			a[i]=a[i-1]-x;
		}else if (st[i]==1){
			a[i]=num1;
		}
	}
	int mx=0;
	for(int i=1;i<=n-1;i++){
		if(a[i]-a[i+1]>=x){
			mx++;
		}
	}
    //最少
	for(int i=n;i>=1;i--){
		if(st[i]==1&&i==n){
			a[i]=num1;
		}
		else if(st[i]==1&&a[i+1]+x<=num1){
			a[i]=a[i+1]+x-1;
		}else if (st[i]==1){
			a[i]=num1;
		}
	}
	int mi=0;
	for(int i=1;i<=n-1;i++){
		if(a[i]-a[i+1]>=x){
			mi++;
		}
	}
	cout<<mx<<" "<<mi<<endl;
}