阿里国际笔试

• 两个数相加为偶数，只可能偶+偶/奇+奇，维护当前的奇偶数量，枚举当前数，特判前一个数即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N];
signed main()
{
    int n,ans=0;
    cin >> n;
    for (int i = 1;i<=n;i++)
        cin >> a[i];
    int odd = 0, even = 0;
    for (int i = 1; i <= n;i++){
        if(a[i]&1){
            ans += odd;
            if(i>=2&&a[i-1]%2!=0)
                ans--;
        }else{
            ans += even;
            if(i>=2&&a[i-1]%2==0)
                ans--;
        }
		odd+=(a[i]&1);
		even+=(a[i]%2==0);
    }
    cout << ans;
}

• 当n为偶数时，所有格子都可以染色，不会冲突，连成环只有两种情况，红黄红黄... 当为奇数时，有一个格子不能染色，先用前缀和维护两种情况的总和，红黄红黄红黄，以及黄红黄红黄红，枚举不能染色的格子，答案为前面的一种情况+后面的一种情况解决冲突，取max即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N], s1[N], s2[N];
int main()
{
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    if (n & 1)
    {
        for (int i = 1; i <= n; i++)
        {
            s1[i] += s1[i - 1] + (i & 1 ? a[i] : b[i]);
            s2[i] += s2[i - 1] + (i & 1 ? b[i] : a[i]);
        }

        for (int i = 1; i <= n; i++)
        {
            ans = max(ans, s1[i - 1] + s2[n] - s2[i]);
            ans = max(ans, s2[i - 1] + s1[n] - s1[i]);
        }

        cout << ans << endl;
    }
    else
    {
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i & 1)
                res += a[i];
            else
                res += b[i];
        }
        int ans = res;
        res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i & 1)
                res += b[i];
            else
                res += a[i];
        }
        ans = max(ans, res);
        cout << ans << endl;
    }
}

• 首先dfs算出每个子树的size，枚举每个节点，计算出max-min即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> g[N];
int sz[N], ans = 0;
int dfs(int x, int fa)
{
    sz[x] = 1;
    for (auto v : g[x])
    {
        if (v == fa)
            continue;
        dfs(v, x);
        sz[x] += sz[v];
    }
    int m1 = 0, m2 = 1e9;
    for (auto v : g[x])
    {
		if(v==fa) continue;
        m1 = max(m1, sz[v]);
        m2 = min(m2, sz[v]);
    }
	if(m2!=1e9)// 存在极值
    	ans += m1 - m2;
	return sz[x];
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, -1);
    cout << ans;
}