A-AOE还是单体?

这道题很简单,理解题目就是:
  • 单伤1点mp,群伤x点mp,杀光最少要多少mp

算法解析
  1. 这道题唯一特殊的就是群伤,群伤就是对多个个体进行单伤。所以如果要群伤,就必须有用群伤的理由
  2. 用群伤的理由是什么呢?就是比单伤所要花的mp要少。所以如果群伤花x点,打的伤害却比x要少,岂不是就亏了。
  3. 所以我们一直打群伤,打到怪物只剩x个以下为止。

操作分析
  1. 既然是打到对手只剩下x为止,所以我们群伤次数就是第n - k大数
  2. 然后后面每个都是单伤,我们就统计起来就好了。
  3. 所以为了操作方便,我们排个序,上面的都可以O(1)查询了。

打代码嘿:
  1. 初始化题目数组。
  2. 给这数组排个序。
  3. 判断一下,如果n比x要小,就直接全部打单伤。把总和输出就好了(单伤伤害为1)。
  4. 如果不是的话,就先打出a[n - k]次群伤,消耗a[n - k] * x点mp。后面的就每个减去a[n - k](被群伤消耗的)累加起来就好了。(用n - k是因为我们舍弃了a[0],从1开始的)。
  5. 就算出来咯,看代码~


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. 我们都知道,如果要中奖,只要至少有一个中奖就可以了的概率。也可以说是:总概率 - 中不了奖的概率。
  2. 为什么要用中不了的概率呢?因为好算呀,中不了的概率就是每个卡池都失败的概率之积。
  3. 也就是说,其实我们的答案就是1 - 失败概率,在mod下的一个值

逆元
  1. 简单来说就是一个数的倒数。
  2. 但是我们在mod取余的情况下就不一样了,除法是不能直接做的,只能用分子 * 分母的逆元
  3. 分母的逆元怎么算呢?我们这里就要用到费马小定理了:a与p互质时就有:ap-1 ≡ 1(mod p)。
  4. 所以1/a = ap-2。再用取模快速幂就好了。

打代码嘞:
  1. 先保存题目要求数组。
  2. 然后分别将分子和分母求出来。
  3. 最后用逆元把公式变成代码。
  4. 看我代码嘞~


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嘞。但是时间复杂度绝对爆表的,直接放弃。
  • 但是对于这道题的性质我是真没想到可以简单用栈来写

算法解析
  1. 这道题,我们可以看到,是相邻的两个数就要删除,删除后相邻的两数也要删除。
  2. 我们无论是去重还是差分都是从最后从整个字符串来看的,但我们这里阔以从前往后看
  3. 从前往后看是啥意思呢?就是从前往后看到重复的就给删掉,删掉之后相邻的自然就可以继续删掉了。
  4. 栗子:先入栈abc,因为和前面不同所以就好好存进去了。然后我们再存个c,和前面重复了,就把前面的c删了,加上这个就是删了两个。
    再进一个b也是一样删掉了。那如果再进一个b,因为前面不是b了,所以没事,就正常进栈。
  5. 所以满足阔以轻易添加删除,与从前往后这两个性质的结构,就是栈了。

操作分析
  • 从前往后遍历栈,我们就是碰到相同即删除,不同即进栈就行了(同上面例子)。

打代码哈:
  1. 先保存好我们的字符串。
  2. 然后从前往后入栈并按上面判断操作,一条龙去重。
  3. 然后把栈倒过来,再输出就好了。
  4. 看我代码~


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时最多

打代码呗:
  1. 输入我们的参数。
  2. 然后输入已知得分,把和求出来就好了。
  3. 然后特判一下n是不是等于m(防止被除数为0)。
  4. 最后直接最大和最小情况分别进行求平均值就好。
  5. 看代码咯~


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。

好了好了,二分
  1. 二分咋整,就是根据题目意思,我们先看函数。
  2. 函数里面可以看出来幂次函数和对数函数都一定是单调递增的,所以我们的这个函数也是单调递增的。
  3. 判断到pow(mid, a) + b * log(mid) >= c时,就说明,答案大了,就把右边的区间不要了。反之亦然。

打代码哈:
  1. 先保存变量咯。
  2. 然后二分查找,按照上面的方法来就好了。
  3. 看代码哈~


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']++。

打代码嘞:
  1. 输入参数(因为可以换行,所以就是文件末结束,疯狂循环输入就好了)。
  2. 读取并散列。
  3. 数组0~25查找一遍。最大的字母位置+'a'输出就好了。
  4. 看代码嘞~


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,范围都不知道炸到哪里去了)

那为啥说这个可以一眼看出来是前缀和呢?
  • 因为我们看题目就知道,每一个位置上的值都是行列所有值之和。

算法操作
  1. 既然说是行列所有项相加,也就可以说是行和 + 列和 - 本位(重复)值
  2. 也就是说我们只要存下来所有行和(row[MAX])与所有列和(column[MAX]),还有本位值就好了。
  3. 这里唯一要注意的就是,本位要存下来,我们知道n * m <= 1e6。我们当然不能开一个1e12的数组,所以这里阔以用指针分配,也可以直接用vector容器

打代码呗:
  1. 先用容器把我们的矩阵与前缀和保存好。
  2. 然后用上面的公式直接输出就好啦。
  3. 看我代码呗~


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