Codeforces Round #670 (Div. 2) 深夜掉分（A - C题补题）

1406A. Subset Mex

https://codeforces.com/contest/1406/problem/A

Example

input

4
6
0 2 1 5 0 1
3
0 1 2
4
0 2 0 1
6
1 2 3 4 5 6

output

5
3
4
0

Note

In the first test case, is a possible choice.

In the second test case, is a possible choice.

In the third test case, is a possible choice.

In the fourth test case,$ A={1,3,5},B={2,4,6}$ is a possible choice.

题意：

给定一个集合，并定义 操作：集合中的最小非负数。

如：%3D3#card=math&code=mex%28%5C%7B1%2C4%2C0%2C2%2C2%2C1%5C%7D%29%3D3)

求 集合分为两部分的最大值：%20%2B%20mex(B)%20)#card=math&code=max%28%20mex%28A%29%20%2B%20mex%28B%29%20%29)

思路：

通过维护两个变量从0开始，如果有0、1、2、3…这样的直接慢慢向上叠加

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
ll n, a[N];
void solve() {
    cin >> n; 
    for (int i = 0; i < n; ++i)cin >> a[i];
    sort(a, a + n);
    ll m = 0, k = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == m)m++;
        else if (a[i] == k)k++;
    }
    cout << m + k << endl;//m、k相当于两个集合中的非负最小值
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll _; cin >> _;
    while (_--)solve();
}

1406B. Maximum Product

https://codeforces.com/contest/1406/problem/B

Example

input

4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1

output

-120
12
0
945

Note

In the first test case, choosing is a best choice: %E2%8B%85(%E2%88%922)%E2%8B%85(%E2%88%923)%E2%8B%85(%E2%88%924)%E2%8B%85(%E2%88%925)%3D%E2%88%92120#card=math&code=%28%E2%88%921%29%E2%8B%85%28%E2%88%922%29%E2%8B%85%28%E2%88%923%29%E2%8B%85%28%E2%88%924%29%E2%8B%85%28%E2%88%925%29%3D%E2%88%92120).

In the second test case, choosing is a best choice: %E2%8B%85(%E2%88%922)%E2%8B%85(%E2%88%923)%E2%8B%852%E2%8B%85(%E2%88%921)%3D12#card=math&code=%28%E2%88%921%29%E2%8B%85%28%E2%88%922%29%E2%8B%85%28%E2%88%923%29%E2%8B%852%E2%8B%85%28%E2%88%921%29%3D12).

In the third test case, choosing is a best choice: %E2%8B%850%E2%8B%850%E2%8B%850%E2%8B%85(%E2%88%921)%3D0#card=math&code=%28%E2%88%921%29%E2%8B%850%E2%8B%850%E2%8B%850%E2%8B%85%28%E2%88%921%29%3D0).

In the fourth test case, choosing is a best choice: %E2%8B%85(%E2%88%927)%E2%8B%85(%E2%88%925)%E2%8B%85(%E2%88%923)%E2%8B%851%3D945#card=math&code=%28%E2%88%929%29%E2%8B%85%28%E2%88%927%29%E2%8B%85%28%E2%88%925%29%E2%8B%85%28%E2%88%923%29%E2%8B%851%3D945).

题意：

给定 大小为n的一个数组，求下标 %20(i%3Cj%3Ck%3Cl%3Ct).#card=math&code=%28i%2Cj%2Ck%2Cl%2Ct%29%20%28i%3Cj%3Ck%3Cl%3Ct%29.) 使得 最大

思路：

一开始以为不能排序，搞得卡了好久。

先对所给数组进行排序，这样必然倒数5个最大，又因为存在负数的关系，所以也许 $ - * - $ 反而最大。详情见代码

#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
ll n, a[N];
void solve() {
    cin >> n; ll ans[4] = {};
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    ans[0] = a[n] * a[n - 1] * a[n - 2] * a[n - 3] * a[n - 4];
    ans[1] = a[n] * a[n - 1] * a[n - 2] * a[1] * a[2];
    ans[2] = a[n] * a[1] * a[2] * a[3] * a[4];
    sort(ans, ans + 3); cout << ans[2] << endl;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll _; cin >> _;
    while (_--)solve();
}

1406C. Link Cut Centroids

https://codeforces.com/contest/1406/problem/C

题目太长这里不粘贴了。

题意：

思路：

DFS搜索，详细待补。请先阅读代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n;
int p1, p2, p3, c[N];
vector<int>g[N];
void dfs(int u, int fa) {
    c[u] = 1;
    for (auto v:g[u]) if (v != fa) {
        dfs(v, u), c[u] += c[v];
    }
    if (!p3) {
        if (c[u] == 1) p1 = fa, p2 = u;
        if (n - c[u] == c[u]) p3 = fa;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        p1 = p2 = p3 = 0;
        for (int i = 1; i <= n; i++) g[i].clear(), c[i] = 0;
        for (int i = n; --i;) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, -1);
        cout << p1 << ' ' << p2 << '\n' << p2 << ' ' << (p3 ? p3 : p1) << '\n';
    }
    return 0;
}