【牛客小白月赛25】
A-AOE还是单体？
这道题很简单，理解题目就是：
- 单伤1点mp，群伤x点mp，杀光最少要多少mp。
算法解析：
- 这道题唯一特殊的就是群伤，群伤就是对多个个体进行单伤。所以如果要群伤，就必须有用群伤的理由。
- 用群伤的理由是什么呢？就是比单伤所要花的mp要少。所以如果群伤花x点，打的伤害却比x要少，岂不是就亏了。
- 所以我们一直打群伤，打到怪物只剩x个以下为止。
操作分析：
- 既然是打到对手只剩下x为止，所以我们群伤次数就是第n - k大数。
- 然后后面每个都是单伤，我们就统计起来就好了。
- 所以为了操作方便，我们排个序，上面的都可以O（1）查询了。
打代码嘿：
- 初始化题目数组。
- 给这数组排个序。
- 判断一下，如果n比x要小，就直接全部打单伤。把总和输出就好了（单伤伤害为1）。
- 如果不是的话，就先打出a[n - k]次群伤，消耗a[n - k] * x点mp。后面的就每个减去a[n - k]（被群伤消耗的）累加起来就好了。（用n - k是因为我们舍弃了a[0]，从1开始的）。
- 就算出来咯，看代码~
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 2e5 + 7;
ll a[MAX];
//全局变量区
int main() {
IOS;
int n, x; cin >> n >> x;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
ll mp = 0;
if (n > x) {
mp = a[n - x] * x;
for (int i = n - x + 1; i <= n; i++)
mp += a[i] - a[n - x];
}
else
for (int i = 1; i <= n; i++)
mp += a[i];
cout << mp << endl;
return 0;
}
//函数区
D-抽卡
这道题首先是一道数学题，然后才扯到的逆元。
首先，我们要知道，我们用数学该怎么把这个概率算出来：
- 我们都知道，如果要中奖，只要至少有一个中奖就可以了的概率。也可以说是：总概率 - 中不了奖的概率。
- 为什么要用中不了的概率呢？因为好算呀，中不了的概率就是每个卡池都失败的概率之积。
- 也就是说，其实我们的答案就是1 - 失败概率，在mod下的一个值。
逆元：
- 简单来说就是一个数的倒数。
- 但是我们在mod取余的情况下就不一样了，除法是不能直接做的，只能用分子 * 分母的逆元。
- 分母的逆元怎么算呢？我们这里就要用到费马小定理了：a与p互质时就有：ap-1 ≡ 1（mod p）。
- 所以1/a = ap-2。再用取模快速幂就好了。
打代码嘞：
- 先保存题目要求数组。
- 然后分别将分子和分母求出来。
- 最后用逆元把公式变成代码。
- 看我代码嘞~
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 7;
int n, a[MAX], b[MAX];
//全局变量区
ll calc(ll down, ll up);//计算up/down的值
ll modpow(ll n, ll m);//取模快速幂
//函数预定义区
int main() {
IOS;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
int up = 1, down = 1;//分子和分母
for (int i = 1; i <= n; i++) {
up = 1ll * up * (a[i] - b[i]) % MOD;
down = 1ll * down * a[i] % MOD;
}
cout << (1 - calc(down, up) + MOD) % MOD << endl;
return 0;
}
ll calc(ll down, ll up) {
return up * modpow(down, MOD - 2) % MOD;
}
ll modpow(ll n, ll m) {
ll mul = 1;
while (m) {
if (m & 1) mul = mul * n % MOD;
m >>= 1;
n = n * n % MOD;
}
return mul;
}
//函数区
E-点击消除
这道题我想过几种解法：去重呀，差分啊，dp嘞。但是时间复杂度绝对爆表的，直接放弃。
- 但是对于这道题的性质我是真没想到可以简单用栈来写。
算法解析：
- 这道题，我们可以看到，是相邻的两个数就要删除，删除后相邻的两数也要删除。
- 我们无论是去重还是差分都是从最后从整个字符串来看的，但我们这里阔以从前往后看。
- 从前往后看是啥意思呢？就是从前往后看到重复的就给删掉，删掉之后相邻的自然就可以继续删掉了。
- 栗子：先入栈abc，因为和前面不同所以就好好存进去了。然后我们再存个c，和前面重复了，就把前面的c删了，加上这个就是删了两个。
再进一个b也是一样删掉了。那如果再进一个b，因为前面不是b了，所以没事，就正常进栈。 - 所以满足阔以轻易添加删除，与从前往后这两个性质的结构，就是栈了。
操作分析：
- 从前往后遍历栈，我们就是碰到相同即删除，不同即进栈就行了（同上面例子）。
打代码哈：
- 先保存好我们的字符串。
- 然后从前往后入栈并按上面判断操作，一条龙去重。
- 然后把栈倒过来，再输出就好了。
- 看我代码~
AC代码
#include <iostream>
#include <string>
#include <stack>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
stack<char> st, t;
//全局变量区
int main() {
IOS;
string s; cin >> s;
int len = s.length();
for (int i = 0; i < len; i++)
if (st.empty()) st.push(s[i]);
else {
char ch = st.top();
if (ch == s[i]) st.pop();
else st.push(s[i]);
}
if (st.empty()) cout << 0 << endl;
else {
while (!st.empty()) {
t.push(st.top()); st.pop();
}
while (!t.empty()) {
cout << t.top();
t.pop();
}
cout << endl;
}
return 0;
}
//函数区
F-疯狂的自我检索者
货真价实大水题：
- 当不知道的人全部是1时最少，不知道的人全部为5时最多。
打代码呗：
- 输入我们的参数。
- 然后输入已知得分，把和求出来就好了。
- 然后特判一下n是不是等于m（防止被除数为0）。
- 最后直接最大和最小情况分别进行求平均值就好。
- 看代码咯~
AC代码
#include <iostream>
using namespace std;
//代码预处理区
int main() {
int n, m; scanf("%d %d", &n, &m);
int sum = 0;
for (int i = 1; i <= n - m; i++) {
int x; scanf("%d", &x);
sum += x;
}
if (n == m) printf("%.5f %.5f\n", 1.0, 5.0);
else printf("%.5f %.5f\n", 1.0 * (sum + m) / n, 1.0 * (sum + 5 * m) / n);
return 0;
}
//函数区
G-解方程
这道题就是看到是个方程就知道是个简单的二分。
再看一遍就发现有两种情况：ab同号，ab异号。
梅开三度（问了大佬），我才发现，题目说ab都是正数！！（我瞎，我超瞎，我sa）orz。
好了好了，二分：
- 二分咋整，就是根据题目意思，我们先看函数。
- 函数里面可以看出来幂次函数和对数函数都一定是单调递增的，所以我们的这个函数也是单调递增的。
- 判断到pow(mid, a) + b * log(mid) >= c时，就说明，答案大了，就把右边的区间不要了。反之亦然。
打代码哈：
- 先保存变量咯。
- 然后二分查找，按照上面的方法来就好了。
- 看代码哈~
AC代码
#include <iostream>
#include <cmath>
using namespace std;
//代码预处理区
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
int a, b, c;
//全局变量区
inline bool judge(double mid) {
if (1 == a) return mid + b * log(mid) >= c;
if (2 == a) return mid * mid + b * log(mid) >= c;
if (3 == a) return mid * mid * mid + b * log(mid) >= c;
}
//函数预定义区
int main() {
scanf("%d %d %d", &a, &b, &c);
double l = 0, r = INF;
while ((l + r) / 2 - l > eps) {
double mid = (l + r) / 2;
if (judge(mid)) r = mid;
else l = mid;
}
printf("%.14f", l);
return 0;
}
//函数区
H-神奇的字母（二）
货真价实二水题：
- 每个字母散列到数组里面统计一下个数，再给输出最多的那个数就好了。
散列：
- 我们就把a~z这26个字母，用ASCII码值散列到0~25的数组中：a[ch - 'a']++。
打代码嘞：
- 输入参数（因为可以换行，所以就是文件末结束，疯狂循环输入就好了）。
- 读取并散列。
- 数组0~25查找一遍。最大的字母位置+'a'输出就好了。
- 看代码嘞~
AC代码
#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
int chs[26];
//全局变量区
int main() {
IOS;
char ch;
while (cin >> ch)
if ('a' <= ch && ch <= 'z')
chs[ch - 'a']++;
int ans = 0;
for (int i = 1; i < 26; i++)
if (chs[ans] < chs[i])
ans = i;
cout << char(ans + 'a') << endl;
return 0;
}
//函数区
I-十字爆破
这道题一眼看出来的前缀和，但是我瞎，很瞎，超级瞎orz（我以为n和m范围都是1e6，范围都不知道炸到哪里去了）
那为啥说这个可以一眼看出来是前缀和呢？
- 因为我们看题目就知道，每一个位置上的值都是行列所有值之和。
算法操作：
- 既然说是行列所有项相加，也就可以说是行和 + 列和 - 本位（重复）值。
- 也就是说我们只要存下来所有行和（row[MAX]）与所有列和（column[MAX]），还有本位值就好了。
- 这里唯一要注意的就是，本位要存下来，我们知道n * m <= 1e6。我们当然不能开一个1e12的数组，所以这里阔以用指针分配，也可以直接用vector容器。
打代码呗：
- 先用容器把我们的矩阵与前缀和保存好。
- 然后用上面的公式直接输出就好啦。
- 看我代码呗~
AC代码
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 1e6 + 7;
vector<int> mp[MAX];
ll row[MAX], column[MAX];
//全局变量区
int main() {
IOS;
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
mp[i].push_back(0);
for (int j = 1; j <= m; j++) {
int x; cin >> x; mp[i].push_back(x);
row[i] += x;//求行和
column[j] += x;//求列和
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cout << row[i] + column[j] - mp[i][j] << " ";
cout << endl;
}
return 0;
}
//函数区比赛 文章被收录于专栏
憨憨的专栏
投递美团等公司10个岗位