题解

Difficulty：3.2 / Easy

Tag：博弈

首先注意到先手一定更优。反证法然后换个位即可证明。

首先考虑如果小涵与人机都是绝顶聪明会怎么样。

由于求的是最大值，考虑二分答案 $x$。

显然如果存在一个武将有超过两个组合默契值大于等于 $x$，那么小涵先选这个武将即可使答案 $\ge x$；如果所有武将默契值大于等于 $x$ 的不超过一个，那人机见一个堵一个即可，答案 $\lt x$。

而注意到题意中人机的做法就和上面分析的做法一模一样，所以按照题意的做法答案就为 $x$。

进一步可以推出答案为对于每个武将，所有组合的次大值，的最大值。

namespace cjdst{
    void solve(){
		int n;
		std::cin >> n;
		std::vector <std::vector <int>> a(n + 5, std::vector <int> (n + 5));
		int ans = -1;
		for(int i = 1; i <= n; i++){
			for(int j = i + 1; j <= n; j++){
				std::cin >> a[i][j];
				a[j][i] = a[i][j];
			}
		}
		for(int i = 1; i <= n; i++){
			int cur = -1, cur2 = -1;
			for(int j = 1; j <= n; j++){
				if(i == j) continue;
				if(cur < a[i][j]) cur2 = cur, cur = a[i][j];
				else cur2 = std::max(cur2, a[i][j]);
			}
			ans = std::max(ans, cur2);
		}
		std::cout << "1\n" << ans << '\n';
	}
}

时间复杂度：$O(n^2)$。