思路:
算法一:可以n^2找出每个点的权值，然后n^2做完，预计得分10
算法二:随机找点然后每次找最高。。貌似只有10分？然而考试的时候煞笔了，边界设成inf。。
算法三:随机找几个点，然后随机爬山，听说有50~70
算法四:考虑将列分治，每次分成2部分，找出每部分边界的最大值，判断最大值左边和右边的大小，然后往大的那一边递归，预计得分70
算法五:不仅将列分治，并且将行分治，将一个n*n的矩阵划分，然后递归找，预计得分100
#include<bits/stdc++.h>
#include"MXPOINT.h"
using namespace std;
int mp[][];
int ask(int x,int y){
if (!mp[x][y]) return mp[x][y];
else
if (x<||x>n||y>m||y<) return mp[x][y]=-;
else return mp[x][y]=ASK(x,y);
}
bool check(int x,int y){
if (mp[x][y]<=mp[x+][y]) return ;
if (mp[x][y]<=mp[x][y+]) return ;
if (mp[x][y]<=mp[x-][y]) return ;
if (mp[x][y]<=mp[x][y-]) return ;
return ;
}
pair<int,int>find(int lx,int rx,int ly,int ry){
if ((rx-lx)<=&&(ry-ly)<=){
for (int i=lx;i<=rx;i++)
for (int j=ly;j<=ry;j++)
if (check(i,j)) return make_pair(i,j);
assert();
}
int mxed=,idx,idy;
for (int i=lx-;i<=rx+;i++)
for (int j=ly-;j<=ry+;j++){
if ((int)(i>=lx&&i<=rx)+(int)(j>=ly&&j<=ry)==) continue;
if (ask(i,j)>mxed){
mxed=ask(i,j);
idx=i;
idy=j;
}
}
if (rx-lx+>ry-ly+){
int mid=(lx+rx)>>;
int mx=;
for (int i=ly;i<=ry;i++) mx=std::max(mx,ask(mid,i));
if (mx<mxed){
if (idx<mid) return find(lx,mid-,ly,ry);
else if (idx==mid) assert();
else return find(mid+,rx,ly,ry);
}
for (int i=ly;i<=ry;i++)
if (mx==ask(mid,i)){
int p1=ask(mid-,i),p2=ask(mid+,i);
if (check(mid,i)) return make_pair(mid,i);
else
if (p1>mx&&mx>p2) return find(lx,mid-,ly,ry);
else
if (p1<mx&&mx<p2) return find(mid+,rx,ly,ry);
else assert();
}
}else{
int mid=(ly+ry)>>;
int mx=;
for (int i=lx;i<=rx;i++) mx=std::max(mx,ask(i,mid));
if (mx<mxed){
if (idy<mid) return find(lx,rx,ly,mid-);
else if (idy==mid) assert();
else return find(lx,rx,mid+,ry);
}
for (int i=lx;i<=rx;i++)
if (mx==ask(i,mid)){
int p1=ask(i,mid-),p2=ask(i,mid+);
if (check(i,mid)) return make_pair(i,mid);
else
if (p1>mx&&mx>p2) return find(lx,rx,ly,mid-);
else
if (p1<mx&&mx<p2) return find(lx,rx,mid+,ry);
else assert();
}
}
}
pair<int,int> FINDMXPOINT(){
memset(mp,,sizeof mp);
return find(,,,);
}