【2022河南萌新联赛第（三）场：河南大学】【部分思路题解+代码解析】

2022河南萌新联赛第（三）场：河南大学

---

A 玉米大炮

题目描述
小蓝正在玩一个植物大战僵尸的改版,在一个特别的关卡中,他需要用玉米大炮击溃僵王博士。

现在小蓝已经部署了 n 个玉米大炮,对于第 i 个玉米大炮,有一个伤害值 $a_i$,一个装填时间 $b_i$,玉米大炮每次发射后需要 $b_i$ 的装填时间,装填完毕之后才可以再次发射。

小蓝已经知道僵王博士有 m 点生命值,但他不知道他什么时间可以击溃僵王博士,你需要计算出出小蓝最少需要多少时间可以击溃僵王博士。

小蓝可以同时控制所有玉米大炮, 玉米大炮每次对僵王博士的攻击会扣除等于其伤害值的血量,如果血量低于或者等于 0 ,僵王博士被消灭,僵王博士被永久冻结不会攻击,开始时所有玉米大炮都装填完毕,装填完毕后小蓝会直接控制其立即攻击,攻击所花费的时间忽略不计。

输入描述:
第一行两个整数 $n,m(1\le n\le 10^5,1\le m\le 10^9)$。
接下来 n 行,每行两个整数 $a_i,b_i(1\le a_i\le 10^9,1\le b_i\le 10^9)$

输出描述:
输出一行一个整数,代表击溃僵王博士需要的最小时间。

示例1
输入

3 3
1 1
2 2
3 3

输出

0

说明

开始时,小蓝控制所有大炮立即发射炮弹,僵王博士受到 6 点伤害,直接被击溃。

题目解析：

很容易发现答案具有单调性, 如果花费 x 的时间可以击溃目标, 则花费 x + 1 的时间也可以击溃目标, 可以直接二分答案, 考虑到二分的左右区间在 $[0,10^{18}]$，可能需要使用long long 或者在二分的过程提前判断是否合法。

时间复杂度 $O(n\times log(10^{18}))$

————————————————————————

一些奇怪的思考：

但是我最开始的想法并非是二份答案，而是完全背包。

一个物品可以被选 n 次，使得背包的总花费最小

const int maxn=1e6+5;
int f[maxn];
void solve(){
    
    int n, m;
    cin >> n >> m;
    vpii yumi;
    ll sum = 0;
    for (int i = 1;i<=n;i++){
    
        int a, b;
        cin >> a >> b;
        sum += a;
        yumi.push_back({
    a, b});
    }
    if(sum>=m){
    
        cout << 0 << nl;
        return;
    }else{
    
        m -= sum;
        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        for (int i = 0; i < n; i ++ ){
    
            int v = yumi[i].first;
            int w = yumi[i].second;
            for (int j = v; j <= m; j ++ ){
    
                f[j] = min(f[j], f[j - v] + w);
            }
        }
        cout<<f[m]<<endl;
    }
}

当然WA了的原因也显而易见，数据太大啦，数组必越界。

好了，接下来看正解吧：

AC代码：

vpii yumi;
ll sum, n, m;
bool check(ll x){
    
    ll ans = 0;
    for (auto i : yumi){
    
        ll cnt = 1;
        if (i.second <= x)
            cnt += x / i.second;
        ans = ans + cnt * i.first;
        if (ans >= m)
            return true;
    }
    return false;
}

void solve(){
    
    cin >> n >> m;
    int maxx = 0;
    for (int i = 1; i <= n; i++){
    
        int a, b;
        cin >> a >> b;
        sum += a;
        maxx = max(maxx, b);
        yumi.push_back({
    a, b});
    }
    sort(yumi.begin(), yumi.end());
    ll l = 0, r = (m / sum + 1) * maxx;
    while (l < r){
    
        ll mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r;
}

---

B 逆序对计数

题目描述
大小为 $n$ 的排列是大小为 $n$ 的数组且使得从 $1$ 到 $n$ 的每个整数在该数组中恰好出现一次。对于给定的一个排列，逆序对就是排列中 $i>j$ 且 $a_i<a_j$的有序对。例如，一个排列 $[3，4，1，2]$ 包含 4 个逆序对, $(3，1)$ , $(4，1)$ , $(3，2)$ , $(4，2)$ 。

您将获得一个大小为 $n$ 的排列 $a$ 并对其进行 $m$ 次询问。每个询问由两个索引 $l$ 和 $r$ 表示，表示您必须反转排列的段 $[l,r]$ 。例如，如果 $a=[1,2,3,4,5]$和查询 $l=2,r=4$ ，那么得到的排列是 $[1,4,3,2,5]$ 。每次询问后，您需要输出逆序对的数量。每次询问相互独立，即该次查询询问对下一次询问不产生影响。

输入描述:
第一行包含一个整数 $n(1\le n\le 6000)$ ,表示排列的大小。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i\le n)$,排列的元素,这些整数是成对不同的。

第三行包含一个整数 $q(1\le q\le 2\times 10^5)$,要处理的询问数。

接下来 $q$ 行，接下来的第 $i$ 行包含两个整数 $l_i,r_i(1\le l_i\le r_i\le n)$表示第 $i$ 个查询是反转排列的段 $l_i,r_i$。

输出描述:
$q$ 行,每行一个整数代表询问的结果。

思路解析：

首先, 对于一个排列, 如果区间反转, 逆序数等于区间中所有的对数减去当前的逆序对数, 即原本的正序对变为逆序对, 原本的逆序对变为正序对。

如果对于每个位置记录其到后面所有位置的逆序对个数即可解决本题, 考虑从 $[l,r]\to [l,r+1]$ 逆序对的个数增加区间 $[l,r]$ 中比 $a_{r+1}$ 的数的个数。

所以可以预处理统计对于每一个位置, 到他的前面的每一个位置比他大的数有多少个, 统计完直接计算逆序对即可。

AC代码：

模拟解法：

const int N = 6005;
int a[N], s[N][N];

int fz(int l, int r){
    
    int len = r - l + 1;
    int sm = len * (len - 1) / 2;
    int inv = s[l][r];
    int sx = sm - inv;
    return sx - inv;
}

void solve(){
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int now = 0;
    for (int i = 1; i <= n; i++){
    
        for (int j = 1; j <= i; j++)
            s[j][i] = s[j][i - 1];
        int z = 0;
        for (int j = i - 1; j >= 1; j--){
    
            if (a[j] > a[i])
                now++, z++;
            s[j][i] += z;
        }
    }
    int q;
    cin >> q;
    while (q--){
    
        int l, r;
        cin >> l >> r;
        int ans = now + fz(l, r);
        cout << ans << nl;
    }
}

树状数组：

当然这不就是经典的点修改区间查询吗？

用树状数组啊~

时间复杂度近似 $O(n^2)$

const int N = 6010;
int f[N][N];
int a[N];
int c[N]; //树状数组
int lowbit(int x){
    
    return x & -x;
}
void add(int x, int k){
    
    while (x <= N){
    
        c[x] += k;
        x += lowbit(x);
    }
}
int ask(int x){
    
    int res = 0;
    while (x){
    
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
void solve(){
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++){
    
        for (int j = i; j <= n; j++){
    
            f[i][j] = f[i][j - 1] + (j - i - ask(a[j]));
            add(a[j], 1);
        }
        for (int i = 1; i <= n; i++)
            c[i] = 0;
    }
    int q;
    cin >> q;
    int ans = f[1][n];
    while (q--){
    
        int l, r;
        cin >> l >> r;
        int res = (r - l + 1) * (r - l) / 2 - 2 * f[l][r];
        cout << ans + res << nl;
    }
}

莫队解法：

官方题解中给到的莫队解法，膜拜大佬

时间复杂度近似 $O(q\times \sqrt{n}\times log(n))$

莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

莫队介绍参见 OIWIKI普通莫队算法

const int N = 6100, M = 2e5 + 100;
int ans[M], n;
struct Node{
    
    int l, r, id;
} q[M];
bool cmp(Node a, Node b){
    
    int la = a.l / sqrt(n), lb = b.l / sqrt(n);
    if(la == lb)
        return a.r < b.r;
    return la < lb;
}
int a[N];
int tr[N];//树状数组
int lowbit(int x){
    
    return x & -x;
}
void add(int x, int v){
    
    for (int i = x; i <= N; i += lowbit(i))
        tr[i] += v;
}
int query(int x){
    
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
void solve(){
    
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++){
    
        int a, b;
        cin >> a >> b;
        q[i] = {
    a, b, i};
    }
    q[m + 1] = {
    1, n, 0};
    sort(q + 1, q + m + 1, cmp);
    int ql = 1, qr = 0, res = 0;
    for (int i = 1; i <= m + 1; i++){
    
        while (qr < q[i].r){
    
            qr++;
            res += query(n) - query(a[qr]);
            add(a[qr], 1);
        }
        while (ql > q[i].l){
    
            ql--;
            res += query(a[ql]);
            add(a[ql], 1);
        }
        while (ql < q[i].l){
    
            add(a[ql], -1);
            res -= query(a[ql]);
            ql++;
        }
        while (qr > q[i].r){
    
            add(a[qr], -1);
            res -= query(n) - query(a[qr]);
            qr--;
        }
        if (!q[i].id)
            ans[q[i].id] = res;
        else{
    
            int len = q[i].r - q[i].l + 1;
            ans[q[i].id] += len * (len - 1) / 2 - 2 * res;
        }
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[0] + ans[i]);
}

---

C 区间操作
D 小蓝的新技能
E 演算任务

---

F 爱学习的小蓝

题目描述

小蓝最近对化学特别感兴趣，但是小蓝在学习化学的时候遇到一个问题，想请聪明的你帮他解决。

我们已知：原子序数 == 核电荷数 == 核外电子数，目前已经发现的元素最多有七个电子层。

小蓝根据这些展开奇思妙想，如果元素的核电子排布严格满足以下条件的话 :

1 . 七个电子层最多容纳的核外电子数依次是 $2,8,8,18,18,32,32$。
2 . 只有当前面的电子层都排满，元素多余的核外电子才会考虑去下一个电子层。

现在小蓝给你一个元素的原子序数 $x$，让你快速的求出该元素的占据的电子层数。

请你设计一个程序，帮他解决该问题。

注：不考虑元素得电子，失电子的情况。

输入描述:
第一行一个整数 $t(1\le t\le 118)$ ，$t$ 为测试样例数。
接下来 $t$ 行 ，每行一个整数 $x(1\le x\le 118)$，代表该元素的原子序数为 $x$。
输出描述:
每行一个整数 $y$ ，代表该元素占据的电子层数。

思路解析：

初中化学，模拟题意

AC代码：

int a[] = {
    0, 2, 8, 8, 18, 18, 32, 32};
void solve(){
    
    int n;
    cin >> n;
    int k = 1;
    while(n>0){
    
        n -= a[k];
        k++;
    }
    cout << --k << nl;
}

---

G 小蓝的玻璃球
H 树上问题
I 旅行

---

J 神奇数字

题目描述
小蓝有三个正整数 $a$ , $b$ , $c$，小蓝想找出所有正整数 $x$ ，使得 $a\equiv b\equiv c$$(mod$$x)$ 。
请从小到大输出所有 $x$ 可能的取值,如果有无限种可能的 $x$ ，则输出 $-1$ 。

输入描述:
本题包含多组测试样例，第一行包含一个正整数 $t(t\le 10^5)$ 表示 $t$ 组数据。
每组数据一行，包括三个正整数 $a,b,c(1\le a,b,c\le 10^5)$。

输出描述:
输出 tt 行。
每组样例输出一行表示结果。

示例1
输入

2
1 2 3
371 429 516

输出

1
1 29

说明

$371\equiv 429\equiv 516$$(mod$$29)$

解题思路：

如果三个数相等, 对任何数取余结果都相同, 输出 −1。

如果不相等, 想到任何数都可以写成 x*y + w, 作 a − b = (x1 −x2) * y, 此时 a, b 对 x1 − x2, y 取余结果相同, 如果是 a, b, c 则取 gcd(abs(a − b), abs(b − c), abs(a − c)) 然后输出所有的质因子即可。

AC代码：

typedef vector<int> vi;
#define all(a) a.begin(), a.end()
void solve(){
    
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && b == c){
    
        cout << -1 << nl;
        return;
    }
    int x = __gcd(abs(a - b), abs(b - c));
    vi res;
    for (int i = 1; i <= x / i;i++){
    
        if (x % i == 0){
    //两个因子
            res.push_back(i);
            if (x / i != i)
                res.push_back(x / i);
        }
    }
    sort(all(res));
    for(auto i:res)
        cout << i << " ";
    cout << nl;
}

---

K 实习生的任务
L 合成游戏