Atcoder Beginner Contest 351

A - The bottom of the ninth(模拟)

题意

    两支队伍A,B正在进行比赛,比赛分为上半和下半两场各有9局,已知上半局A的全部得分和下半局B的前8局得分,问B的最后一局得分至少是多少才能使得B的总分严格大于A?

思路

    设所有A的总和sum_A= ,前八局B的总和sum_B为;易知，当sum_Asum_B时,此时B需要sum_A-sum_B+1的得分，反之，B已经严格高于A的得分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
int a[15], b[15];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int sum1 = 0, sum2 = 0;
    for (int i = 1; i <= 9;i++)
        cin >> a[i], sum1 += a[i];
    for (int i = 1; i < 9; i++)
        cin >> b[i], sum2 +=  b[i];
    int ans = max(sum1 - sum2 + 1, 0LL);
    cout << ans << endl;
    return 0;
}

B - Spot the Difference(模拟)

题意

两个NN的网格，已知这两个网格有且只有一个位置(i,j)内的字符不同。请找出这个(i,j)的位置，行列的下标从1开始编号。

数据范围

  • ,均为小写字母

    思路

    由于N的范围极小，输入两个方格后直接按行遍历即可，找到第一个不同的字符位置就是答案.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #include<bits/stdc++.h>
    #define int long long
    #define endl '\n' 
    using namespace std;
    char a[105][105], b[105][105];
    signed main(){
        std::ios::sync_with_stdio(false);cin.tie(0);
        int n,sx,sy;cin >> n;
        for (int i = 1; i <= n;i++) cin >> a[i];
        for (int i = 1; i <= n;i++) cin >> b[i];
        for (int i = 1; i <= n;i++)
            for (int j = 0; j < n;j++)
                if(a[i][j] != b[i][j])
                    sx = i, sy = j + 1;
        cout << sx << ' ' << sy;
        return 0;
    }

    C - Merge the balls(栈)

    题意

        拥有N个球，其中每个球的体积大小为,从i=1开始依次将球装进盒子里。每次装完球后执行以下操作：
  1. 若当前只有一个球，则结束操作
  2. 若最靠右的两个球体积不等，则结束操作
  3. 若最靠右的两个球体积相等，则将其合并为一个球，体积翻倍，并返回步骤1重新操作；

    数据范围

  • 思路

        由于每次是从右往左依次合并，符合“后进先出”的特征，所以可以用栈去模拟合并的过程。对于每次的合并，显然只有相同的指数可以进行相加，又+=，故主需要在栈内丢入指数，合并时将指数加一。最终输出栈内的元素数量即可.
        虽然N高达，但是从感性方面去理解，每合并一次数量减一，从最坏情况去考虑，加入一个球后前面全部进行合并，但从该球往后整个盒子内的球数再度变为1…所以整体的复杂度还是O(N)量级的
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include<bits/stdc++.h>
    #define int long long
    #define endl '\n' 
    using namespace std;
    int a[200010],stk[200010];
    signed main(){
        std::ios::sync_with_stdio(false);cin.tie(0);
        int n;cin >> n;
        for (int i = 1; i <= n;i++) cin >> a[i];
        int top = 0;stk[++top] = a[1];
        for (int i = 2;i <= n;i++){
            stk[++top] = a[i];
            while(stk[top] == stk[top-1]){
                stk[top - 1] = stk[top] + 1;
                top--;
            }
        }
        cout << top << endl;
        return 0;
    }

    D - Grid and Magnet

    待补

    E - Jump Distance Sum

    待补

    F - Double Sum(树状数组+离散化)

    题意

        给定一个整数序列 A=(,…),计算以下表达式：

    数据范围

  • 保证答案小于

    思路

        形式化地， 等价于当i < j 时，所有的逆序对的差值和，其中.顾名思义，设对于任意的i，其逆序对的数量为num,则其对答案的贡献为. 所以我们需要知道其数量和对应的值的总和.
        从逆序对数量的角度出发，我们以往可以通过树状数组模拟桶去维护小于等于某个数的数量，同样，我们也可以去维护小于某个数的总和；对于逆序对的求解，我们选择从i-1开始倒序模拟本题需要求的条件是大于，所以需要进行转换，大于的数量只需要用区间的总数量减去小于等于的总数量，即 ,同理，大于的总和为，其中，区间的总和可以用前缀和实现.
        同时，因为的值最高的值为，已经远远超过了桶的承受范围，所以需要对进行离散化操作，但是求和的时候必须用到的是真实值，所以还需要再开一个数组保存原始数值，以便在求和的时候通过下标索引到真实值.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    #include<bits/stdc++.h>
    #define int long long
    #define endl '\n' 
    #define INF 1e15
    using namespace std;
    struct node{
        int val, id;
        //按照val的大小进行重载
        bool operator<(const node s)const{
            return val < s.val;
        }
    }a[400010];
    int b[400010], c[400010], pre[400010];
    //b数组表示离散化后的值，c数组表示原始值，pre数组表示原始值的前缀和
    int cnt[400010], sum[400010];
    //cnt[i]表示小于等于i的数量，sum[i]表示小于等于i的总和
    signed main(){
        std::ios::sync_with_stdio(false);cin.tie(0);
        int n;
        cin >> n;
        for (int i = 1; i <= n;i++){
            cin >> a[i].val, a[i].id = i;
            pre[i] = pre[i - 1] + a[i].val;
        }
        //分别对数量和值建立“单点修改、区间查询”的树状数组
        auto add1 = [&](int x, int k) -> void{
            for (int i = x; i <= 4e5; i += i & (-i))
                cnt[i] += k;
        };
        auto add2 = [&](int x, int k) -> void{
            for (int i = x; i <= 4e5; i += i & (-i))
                sum[i] += k;
        };
        auto query1 = [&](int x) -> int{
            int res = 0;
            for (int i = x; i; i -= i & (-i))
                res += cnt[i];
            return res;
        };
        auto query2 = [&](int x) -> int{
            int res = 0;
            for (int i = x; i; i -= i & (-i))
                res += sum[i];
            return res;
        };
        for (int i = 1; i <= n;i++)
            c[i] = a[i].val;
        //离散化操作
        sort(a + 1, a + n + 1);
        for (int i = 1;i<=n;i++){
            b[a[i].id] = i;
            if (i > 1 && a[i].val == a[i - 1].val)
                b[a[i].id] = b[a[i - 1].id];
        }
        int ans = 0;
        //倒序求逆序对
        for (int i = n - 1; i >= 1;i--){
            //前者插入数量1，后者插入真实值c[i+1]
            add1(b[i + 1], 1), add2(b[i + 1], c[i + 1]);
            int cnt1 = (n - i) - query1(b[i]);
            int sum1 = (pre[n] - pre[i]) - query2(b[i]);
            ans += sum1 - cnt1 * c[i];
        }
        cout << ans << endl;
        return 0;
    }