牛客多校赛题解（四）

1. Inverse Pair

题目链接：https://ac.nowcoder.com/acm/contest/11255/I

题目大意：

有一个序列A，其中的元素可以是任意的，还有一个序列B，其中的元素只能为 0 或者 1，现有序列C，其中C = A + B（元素对应相加）

问：C的逆序对最少有多少对

解题思路：

先求出A的逆序对数，再看A中有多少的a[i] = a[j] + 1 其中 i < j，算出满足上述条件的式子直接从答案中减去即可

ACCode:

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2021-07-29 21:15:50
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) Mr.Sen All rights reserved.
 */

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
const int N = 3e5+10;
 
struct node{
    int val,pos;
    bool operator < (const node & x) const { return val < x.val ; }
}p[N];

int tr[N];
int n;
ll num;
 
int lowbit(int x){
    return x & -x;
}
 
void add(int x){
    for(int i=x;i<=N;i+=lowbit(i)) tr[i]++;
}
 
int query(int x){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
    return ans;
}
 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x;  cin>>x;
        p[i]={x,i};
        add(x);
        num+=i-query(x); // 树状数组求逆序对
    }
    sort(p+1,p+1+n);
 
    for(int i=1;i<n;i++)
        if(p[i].pos>p[i+1].pos) num--,i++; 
    cout<<num<<endl;
 
    return 0;
}

2. Average

题目链接：https://ac.nowcoder.com/acm/contest/11255/J

题目大意：

有一个矩阵，矩阵里的值是由数组A和数组B中的元素相加得到的，现在要求其中矩阵最大的平均值，要求矩阵的长度不能小于x，宽度不能小于y

解题思路：

初步推导如下

于是这个问题便转换成了一个一维的问题，即：求两个数组的子数组的最大平均数的和。

再利用二分法成功解出问题

值得注意的是，尽量将输出结果写的精简一点，以免因为精度的问题出错

ACCode:

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2021-07-29 21:15:50
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) Mr.Sen All rights reserved.
 */

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 10;
const int M = 1e9 + 10;

double a[100005];
double b[100005];
double sum[100005] = {0};

double find(int n, int f)
{
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf", &a[i]);
    }
    double l = -1e6, r = 1e6;
    while (r - l > 1e-6) //二分的结束条件
    {
        double mid = (l + r) / 2;
        for (int i = 1; i <= n; i++)
        {
            b[i] = a[i] - mid;
        }
        for (int i = 1; i <= n; i++)
        {
            sum[i] = sum[i - 1] + b[i]; //求前缀和
        }
        // double MIN = (1 << 31) - 1, MAX = -1e10;
        double MIN = (double)((1 << 31) - 1);
        double MAX = (double)(-1e10);
        
        for (int i = f; i <= n; i++)
        {
            MIN = min(MIN, sum[i - f]);   //不断维护左端的最小值
            MAX = max(MAX, sum[i] - MIN); //相见得到区间和
        }
        if (MAX >= 0)
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    // printf("%.10lf\n", r);
    return r;
}

int main()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    double ans1 = find(n, x);
    double ans2 = find(m, y);

//     cout <<  (ans1 + ans2) << endl;
    printf("%.12lf\n", ans1 + ans2);
    
    return 0;
}

3. Just a joke

题目链接：https://ac.nowcoder.com/acm/contest/11255/F

题目大意：

alice和bob在做游戏，内容是拆一个图，每次可以拆一个边或者拆一个树，但是不能拆一个带有回路的组件（component）,当最后一个可以被操作的东西移除以后，最后操作者获胜

解题思路：

这题我看了以后脑子嗡嗡的，不知道他在说啥，后来画了个图，才明白这是正儿八经的水题

因为每次拆一个边或者拆一个树，都是拆除奇数个边，因此只需要判断一下边和点的和的奇偶性就能得到结果了...

ACCode:

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2021-07-29 21:15:50
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) Mr.Sen All rights reserved.
 */

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
const int M = 1e9+10;

int main()
{
    // freopen("input.in", "r", stdin);
    // freopen("output.out","w", stdout);
    int n, m;
    int v, u;
    cin >> n >> m;
    while (cin >> v >> u);
    if ((n + m) & 1) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }
    return 0;
}