NOI十连测第四测 T3

思路:

算法一:可以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(,,,);

 }

巴特西

NOI十连测第四测 T3

最新文章

热门文章

巴特西

NOI十连测 第四测 T3

最新文章

热门文章

NOI十连测第四测 T3