牛客周赛 Round 65

文章目录

- - 超市
  - - 思路：
    - 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;
}