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; } //函数区