微众银行 笔试

单纯记录，纯菜狗一枚，A了前两题

第一题：

从0开始找最大不重复的字串

#include<iostream>
#include<unordered_map>
using namespace std;

int a[50001];

int main() {
    int n;
    cin>>n;
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++) {
        cin>>a[i];
        if (map.find(a[i]) == map.end()) {
            map.emplace(a[i], 1);
        } else {
            break;
        }
    }
    cout<<map.size();
    
}

第二题：

先排序，然后算一下两两元素之间的差就行：

#include<iostream>
#include<algorithm>
using namespace std;

int a[50001];

int main() {
    int n;
    cin>>n;
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    sort(a, a + n);
    int sum = 0;

    for (int i = 0; i < n - 1; i++) {
        if (a[i] >= a[i + 1]) {
            int gap = a[i] - a[i + 1];
            a[i + 1] = a[i + 1] + gap + 1;
            sum += gap + 1;
        } 
    }

    cout << sum;
    
}

第三题：

找子区间平均值与输入一样的数量：

感觉要TLE，暂时不知道咋做。

#include<iostream>
#include<vector>
using namespace std;

int avg(vector<int> &v, int l, int r) {
    int sum = 0;
    for (int i = l; i < r; i++) {
        sum += v[i];
    }
    return sum / (r - l);
}

int main() {
    int n, u, v;
    cin>>n>>u>>v;
    vector<int> vec;
    int x;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin>>x;
        if (x == u/v) sum++;
        vec.push_back(x);
    }
    
    for (int size = 2; size <= n; size++) {
        for (int i = 0; i + size <= n; i++) {
            if (avg(vec, i, size) == u/v) sum++;
        }
    }
    
    cout<<sum;
}