牛客周赛65（C++实现）

比赛链接：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

1.超市

1.1 题目描述

小红准备去超市买水果。已知苹果aaa元一斤，桃子bbb元一斤。
小红一共带了nnn元钱，她想知道自己最多可以买多少斤水果？
我们认为，同一种水果买的斤数必须是整数。

1.2 思路

为了买更多的水果，我就需要尽可能的买便宜水果。

1.3 代码

#include <vector>
#include <iostream>
#include <queue>
#include <string>using namespace std;int main()
{int a, b, n;cin >> n >> a >> b;int ans = 0;if (a > b){ans = n / b;}else{ans = n / a;}cout << ans;return 0;
}

2. 雨幕

2.1 题目描述

今年的雨水格外的多，喜欢下雨的小红自然也很开心。
给定一个n行m列的地图，用字符表示降雨情况，'.‘代表未降雨，’*'代表降雨。请你帮小红求出有多少个2*2的区域满足该区域内全部都在降雨？

2.2 思路

暴力地遍历除去最后一行和最后一列的所有位置，和题目要求做对应对比，判断是否满足要求。

2.3 代码

#include <vector>
#include <iostream>
#include <queue>
#include <string>using namespace std;int main()
{int n, m;long long ans = 0;cin >> n >> m;vector<vector<char>> vv(n + 1, vector<char>(m + 1));for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)cin >> vv[i][j];for (int i = 1; i < n; ++i){for (int j = 1; j < m; ++j){if (vv[i][j] == '*' && vv[i + 1][j] == '*' && vv[i][j + 1] == '*' && vv[i + 1][j + 1] == '*')ans += 1;}}cout << ans;return 0;
}

3.闺蜜

3.1 题目描述

小红和小紫是好闺蜜，作为闺蜜当然要“友好”的一起玩游戏。
她们拿到了一个长度为偶数的数组，两人轮流进行取数，谁最终总和最大谁就获胜。小红先手取数。
但这个比赛显然对小紫是不公平的，因此小红允许小紫使用一次技能“隙间”，小紫在游戏的任何时期，可以将自己手中的一个元素和小红手中的一个元素进行交换（该技能最多释放1次）。请你判断两人都是用最优策略的情况下，谁将取得最终的胜利？

3.2 思路

因为小红抽卡在前，所以小红一定会拿当前卡组内的最大牌。而小紫只有一次的交换机会，为了使得效益最大化，小紫一定要用卡组内的最小值去换小红手里的最大值。为此交换的卡片就已经确定了，那么我们就可以去掉这两张牌，让两人玩这个游戏，最后再把最小牌给小红，最大牌给小紫。

3.3 代码

#include <vector>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>using namespace std;
int t, n;
int arr[1010];
void slove()
{cin >> t;while (t--){cin >> n;long long sum = 0LL;for (int i = 1; i <= n; ++i){cin >> arr[i];sum += arr[i];}sort(arr + 1, arr + n+1);if (arr[1] == arr[n]){cout << "draw" << endl;continue;}long long tmp = 0LL;for (int i = 1; i <= n; i += 2){tmp += arr[i];}long long kou = sum - tmp;if (kou - arr[n] + arr[0] > tmp - arr[0] + arr[n])cout << "kou" << endl;elsecout << "yukari" << endl;}
}
int main()
{slove();return 0;
}

4. 医生

4.1 题目描述

小红是一名医生。
现在小红对于每个病人的症状用一个长度为mmm的01串表示，第iii个字符代表第iii个身体部位的症状，0代表健康，1代表不健康。
一共有kkk种药，每种药也用一个长度为mmm的01串表示，第iii个字符为’1’代表该药可以治愈第iii个部位的症状。
对于每个病人，请你帮小红求出治愈该病人需要开的最少的药数量。

4.2 思路

本题的思路还挺简单的，因为数据量的原因，药物只有10种。那么我们可以枚举出所有药物的使用组合。一共1024种。这题的巧思也就在这组合上面，我们要怎么写这个组合呢？

    for (int i = 1; i <= (1 << k); ++i){for (int j = 0; j < k; ++j){if ((i >> j)&1)v[i] |= me[j];}}

使用状态压缩的思路，一共k种药物，药物的组合情况一定为（1<<k）。用一个数来枚举这些情况，这个数的二进制位哪里有1，就使用该位对应的药物。这样就可以做到（1<<k）种情况都不遗漏了。最后我们只要数，该数有多少个1那么就说明了使用了多少种药物。

4.3 代码

#include <bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;
int n, m, k;
int p[10010],me[12],v[1050];void solve()
{cin >> n >> m;string s;for (int i = 1; i <= n; ++i){cin >> s;p[i] = stoi(s, 0, 2);}cin >> k;for (int i = 0;i < k; ++i){cin >> s;me[i] = stoi(s, 0, 2);}for (int i = 1; i <= (1 << k); ++i){for (int j = 0; j < k; ++j){if ((i >> j)&1)v[i] |= me[j];}}for (int i = 1; i <= n; ++i){int mi = k + 1;for (int j = 0; j <= (1 << k); ++j){if ((v[j] & p[i]) == p[i]){mi = min(mi,__builtin_popcount(j));}}if (mi == k + 1)cout << -1 << endl;elsecout << mi << endl;}}
int main()
{solve();return 0;
}