本文共 2989 字，大约阅读时间需要 9 分钟。

1406A. Subset Mex

Example

input

460 2 1 5 0 130 1 240 2 0 161 2 3 4 5 6

output

5340

Note

In the first test case,\(A=\{0,1,2\},B=\{0,1,5\}\) is a possible choice.

In the second test case, \(A=\{0,1,2\},B=∅\) is a possible choice.

In the third test case, \(A=\{0,1,2\},B=\{0\}\) is a possible choice.

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

题意：

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

如：\(mex(\{1,4,0,2,2,1\})=3\)

求 集合分为两部分的最大值：\(max( mex(A) + mex(B) )\)

思路：

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

#include
   
    #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

Example

input

45-1 -2 -3 -4 -56-1 -2 -3 1 2 -16-1 0 0 0 -1 -16-9 -7 -5 -3 -2 1

output

-120120945

Note

In the first test case, choosing \(a1,a2,a3,a4,a5\) is a best choice: \((−1)⋅(−2)⋅(−3)⋅(−4)⋅(−5)=−120\).

In the second test case, choosing \(a1,a2,a3,a5,a6\) is a best choice: \((−1)⋅(−2)⋅(−3)⋅2⋅(−1)=12\).

In the third test case, choosing\(a1,a2,a3,a4,a5\) is a best choice: \((−1)⋅0⋅0⋅0⋅(−1)=0\).

In the fourth test case, choosing \(a1,a2,a3,a4,a6\) is a best choice: \((−9)⋅(−7)⋅(−5)⋅(−3)⋅1=945\).

题意：

给定 大小为n的一个数组，求下标 \((i,j,k,l,t) (i<j<k<l<t).\) 使得\(a1,a2,a3,a4,a5\) 最大

思路：

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

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

#include
   
    #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

题目太长这里不粘贴了。

题意：

思路：

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

#include 
   
    #define int long longusing namespace std;const int N = 1e5 + 10;int n;int p1, p2, p3, c[N];vector
    
     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;}