https://acm.hdu.edu.cn/showproblem.php?pid=7067
一棋子初始位于(1,1)，A先手，A可以横移棋子，B可以竖移棋子，或者，到某人行动的时候可以立刻终止游戏。游戏执行$k$轮后会结束。最终棋子停留的底下的值为最终得分，A目标是最大化，B目标是最小化。求最终答案。
结论题，先上结论：
设$maxn[i]$为第$i$行最大值，$minn[i]$为第$i$列最小值。
$k=1$时为$maxn[1]$（这个显然）；
除此以外，$k$为奇数时为$max(a[1][1],min{maxn})$，$k$为偶数时为$max(a[1][1],max{minn})$。
这题看起来很复杂，实际上两个人是在终极拉锯战。举例来说最后一步假设是A，那他肯定会去选择当前行最大值，于是倒数第二步B就要将棋子移动到最小的当前行最大值的行上。以此类推……
那么“终止游戏”操作呢？两边一般都不会去用的，因为按照上述所说的拉锯战，每一步都会达到一个最值，因此终止游戏只会使得当前结果不符合当局者的利益。但是终止游戏对于A还是有用的，即可以直接拿初始值走人，防止拉着拉着被对面偷家了（。
（所以我为啥会WA了呢……离谱我还以为我智商退化了害……）
#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+5; const int INF=1e9+10; inline ll read(){ ll X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int n,m,maxn[N],minn[N]; vector<vector<int> >a; int sol(ll k){ if(k==1)return maxn[0]; if(k&1){ int ans=INF; for(int i=0;i<n;i++){ ans=min(ans,maxn[i]); } return max(a[0][0],ans); } else{ int ans=0; for(int j=0;j<m;j++){ ans=max(ans,minn[j]); } return max(a[0][0],ans); } } int main(){ int T=read(); while(T--){ a.clear(); n=read(),m=read(); ll k=read(); for(int i=0;i<n;i++){ vector<int>v; maxn[i]=0; for(int j=0;j<m;j++){ v.push_back(read()); maxn[i]=max(maxn[i],v[j]); } a.push_back(v); } for(int j=0;j<m;j++){ minn[j]=INF; for(int i=0;i<n;i++){ minn[j]=min(minn[j],a[i][j]); } } printf("%d ",sol(k)); } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++