0918 金山wps笔试

比较简单，选择+编程一小时ac了（编程题写了40分钟）

1、循环数组找最大子数组和

前缀和+后缀和最大值+dp（1e5的数据范围O(N)

class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int maxSubarraySumCircular(vector<int> &nums)
    {
        // write code here
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        vector<int> suffix(n + 1, 0);
        for (int i = 0; i < n; i++)
            prefix[i + 1] = prefix[i] + nums[i];
        for (int i = n - 1; i >= 0; i--)
            suffix[i] = suffix[i + 1] + nums[i];
        for (int i = n - 1; i >= 0; i--)
            suffix[i] = max(suffix[i], suffix[i + 1]);
        int ans = INT_MIN;
        int pre = 0;
        for (int i = 0; i < n; i++) {
            pre = max(pre + nums[i], nums[i]);
            ans = max(ans, max(pre, prefix[i + 1] + suffix[i + 1]));
        }
        return ans;
    }
};

2、给一堆x坐标，找一个坐标y使得所有所有x到y的距离和最小，求最小距离和

前后缀分解+暴力遍历（实际上排序后找中位数就行了吧）(1e6的数据范围，O(N logN)）

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main()
{
    int n;
    cin >> n;
    vector<ll> arr(n);
    int y;
    for (int i = 0; i < n; i++)
        scanf("%lld %d", &arr[i], &y);
    sort(arr.begin(), arr.end());
    vector<ll> prefix(n + 1, 0);
    vector<ll> suffix(n + 1, 0);
    for (int i = 0; i < n; i++)
        prefix[i + 1] = prefix[i] + arr[i];
    for (int i = n - 1; i >= 0; i--)
        suffix[i] = suffix[i + 1] + arr[i];
    ll ans = 1e15;
    for (int i = 0; i < n; i++)
    {
        ll sum1 = arr[i] * i - prefix[i] + suffix[i + 1] - arr[i] * (n - i - 1);
        ans = min(ans, sum1);
    }
    cout << ans << endl;
    return 0;
}

3、给一个1为根的树，有每个结点有权值。同时每个结点的价值以自己为根的子树的所有节点权值和。求任意两个没有祖孙关系的结点(x,y)价值差最小值。（没有祖孙关系就是x不是y的祖先并且y不是x的祖先）

跑一遍dfs，回溯记录子节点价值。然后维护每个节点的孙子节点（O(N^2）直接过了，本来还想着有啥优化方法。(2e3的数据范围，O(N^2)）

#include "bits/stdc++.h"
using namespace std;
const int mod = 1e9;
int main()
{
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    vector<int> vec(n + 1, 0);
    vector<vector<int>> edges(n + 1);
    vector<unordered_set<int>> relation(n + 1);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    int u, v;
    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &u, &v);
        edges[u].push_back(v);
    }
    auto dfs = [&](auto &&dfs, int root) -> int
    {
        vec[root] = arr[root];
        for (auto child : edges[root])
        {
            vec[root] += dfs(dfs, child);
            relation[root].insert(child);
            for (auto nextchild : relation[child])
                relation[root].insert(nextchild);
        }
        return vec[root];
    };
    dfs(dfs, 1);
    int ans = 1e9;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (!relation[i].count(j) && !relation[j].count(i))
                ans = min(ans, abs(vec[i] - vec[j]));
    cout << ans << endl;
    return 0;
}