简要题意：
每两个武将都有一定的默契值。你和电脑轮流选择武将，电脑总会选择让你得不到最大默契值的那个武将；你要选择一种方法，使得你的最大默契值最大。如果会输给电脑则输出 \(0\)，否则输出 \(1\) 和那个最大的默契值。
首先，人肯定比电脑聪明
如果你抱着骗分的态度
printf("0\n");
然后你会得到一个完美的 \(0pt\).
也就是说，始终存在某种方案，使得人可以胜利！
你会发现，电脑的选法是有些死板（但也有些道理）的，它总是会阻止你拿到最高的那个默契值。
所以，每行最大的默契值肯定不是你的。但也不是它的。为什么呢？
假设第 \(i\) 个武将和第 \(j\) 个武将拥有最高的默契值 \(k\).
此时如果你选了 \(i\) 和 \(j\) 中的一个，那么电脑会选另一个，\(k\) 就谁也不属于。
如果你一个也不选，电脑肯定也不会来选这两个，所以 \(k\) 仍然谁也不属于。
那么结论得到了，既然最大值抢不到，可不可以抢次大值？
比方说，\(i\) 号武将和 \(j\) 号武将仍有最高的默契值 \(k\)，而 \(i\) 号武将和另一个 \(x\) 号武将有次大的默契值 \(y\).
此时你选了 \(i\)，然后电脑把 \(j\) 拿走了，紧接着你再拿走 \(x\).
此时，在与 \(i\) 号武将的所有搭配中，你占了优势：因为最大值谁也没捞到，但你却捞到了次大值。
类似的，每一行的最大值都是谁也没捞到，但你却捞到了每一行的次大值。
首先你显然胜利了，其次，那么你搭配的最大值是多少呢？
显然，就是 每一行的次大值的最大值 。
意思是，把每行的次大值搞出来，再这 \(n\) 个数中取最大值！
吐槽：数据太弱了。（爆搜都能拿 \(70pts\)，这什么东西）
你可能觉得，把每一行开 \(\texttt{vector}\) 分别排序即可，取次大值打擂即可。
时间复杂度： \(O(n^2 \log n)\).
还真过了？
好，那加强一下。
对于 \(100 \%\) 的数据，\(N \leq 5 \times 10^3\).
你会发现，此时你要用 \(O(n)\) 的时间取出次大值。
你打擂法没学好吧，这还叫加强，我真是服了
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=5e2+1;
inline int read(){char ch=getchar();int f=1;while(ch<‘0‘ || ch>‘9‘) {if(ch==‘-‘) f=-f; ch=getchar();}
int x=0;while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x*f;}
int n,a[N][N];
int ans=0;
int main(){
n=read();
for(int i=1;i<n;i++)
for(int j=1;j<=n-i;j++) {
a[i][j+i]=read();
a[j+i][i]=a[i][j+i];
} for(int i=1;i<=n;i++) {
int max1=0,max2=0; //max1 是最大值，max2 是次大值
for(int j=1;j<=n;j++)
if(a[i][j]>max1) max2=max1,max1=a[i][j]; //此时两个值一起变
else if(a[i][j]>max2) max2=a[i][j]; //只改变次大值
ans=max(ans,max2);
} printf("1\n%d\n",ans);
return 0;
}
原文：https://www.cnblogs.com/bifanwen/p/12546898.html