Boleyn Su's Blog

用g[i][j]表示以(i,j)和(i-K+1,j-K+1)为两个顶点的正方形的价值，然后递推求之。

f1_1[i][j]表示以(1,1)和(i,j)为两个顶点的矩形内最大的K*K的方形的价值，递推求之。f1_N,fM_1,fM_N用相似的方法弄出来。

然后，进入主要的部分，分情况。因为我们需要三个方块，其实就是将油区整个分为3份，然后每份里找一个方块。不难发现，一共只有6种情况。如下图：

然后，利用先前的预处理，加上枚举分割线，就可以得出结果了。

然后，可能会发现TLE，这可能是因为读文件太慢了，可以自己用底层函数重写输入语句。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-17

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

 

#define MAXM 1500

#define MAXN 1500

#define MAX(a,b) ((a)>(b)?(a):(b))

#define update(who,with) if ((who)<(with)) {(who)=(with);}

 

int M,N,K;

int map[MAXM][MAXN];

 

int f[MAXM][MAXN];

int g[MAXM][MAXN];

int maxx[MAXM];

int maxy[MAXN];

int max[MAX(MAXM,MAXN)];

int f1_1[MAXM][MAXN];

int f1_N[MAXM][MAXN];

int fM_1[MAXM][MAXN];

int fM_N[MAXM][MAXN];

 

int answer;

 

void update_case1234(int,int);

void update_case5();

void update_case6();

 

bool isNumber[256];

void read(int& who)

{

    char get;

    who=0;

    while (isNumber[get=getchar()]) who=who*10+get-‘0’;

}

 

int main()

{

    //freopen(“oil.in”,”r”,stdin);

    //freopen(“oil.out”,”w”,stdout);

    isNumber[‘0’]

    =isNumber[‘1’]

    =isNumber[‘2’]

    =isNumber[‘3’]

    =isNumber[‘4’]

    =isNumber[‘5’]

    =isNumber[‘6’]

    =isNumber[‘7’]

    =isNumber[‘8’]

    =isNumber[‘9’]

    =true;

    read(M);

    read(N);

    read(K);//scanf(“%d %d %d\n”,&M,&N,&K);

    for (int i=0;i<M;i++)

        for (int j=0;j<N;j++)

        {

            //scanf(“%d”,&map[i][j]);

            //if (j+1==N) scanf(“\n”);

            //else scanf(” “);

            read(map[i][j]);

        }

    for (int i=0;i<M;i++)

        for (int j=0;j<N;j++)

        {

            if (j>=K)

                f[i][j]=f[i][j-1]+map[i][j]-map[i][j-K];

            else if (j>0)

                f[i][j]=f[i][j-1]+map[i][j];

            else

                f[i][j]=map[i][j];

            //printf(“f[%d][%d]=%d\n”,i+1,j+1,f[i][j]);

            if (i>=K)

                g[i][j]=g[i-1][j]+f[i][j]-f[i-K][j];

            else if (i>0)

                g[i][j]=g[i-1][j]+f[i][j];

            else

                g[i][j]=f[i][j];

            //printf(“g[%d][%d]=%d\n”,i+1,j+1,g[i][j]);

            if (maxx[i]<g[i][j]) maxx[i]=g[i][j];

            if (maxy[j]<g[i][j]) maxy[j]=g[i][j];

        }

    //for (int i=0;i<M;i++) printf(“maxx[%d]=%d\n”,i+1,maxx[i]);

    //for (int j=0;j<N;j++) printf(“maxy[%d]=%d\n”,j+1,maxy[j]);

    for (int i=K-1;i<M;i++)

        for (int j=K-1;j<N;j++)

        {

            f1_1[i][j]=g[i][j];

            if (i>0) update(f1_1[i][j],f1_1[i-1][j]);

            if (j>0) update(f1_1[i][j],f1_1[i][j-1]);

            //printf(“f1_1[%d][%d]=%d\n”,i+1,j+1,f1_1[i][j]);

        }

    for (int i=K-1;i<M;i++)

        for (int j=N-K;j>=0;j–)

        {

            f1_N[i][j]=g[i][j+K-1];

            if (i>0) update(f1_N[i][j],f1_N[i-1][j]);

            if (j<N-1) update(f1_N[i][j],f1_N[i][j+1]);

            //printf(“f1_N[%d][%d]=%d\n”,i+1,j+1,f1_N[i][j]);

        }

    for (int i=M-K;i>=0;i–)

        for (int j=K-1;j<N;j++)

        {

            fM_1[i][j]=g[i+K-1][j];

            if (i<M-1) update(fM_1[i][j],fM_1[i+1][j]);

            if (j>0) update(fM_1[i][j],fM_1[i][j-1]);

            //printf(“fM_1[%d][%d]=%d\n”,i+1,j+1,fM_1[i][j]);

        }

    for (int i=M-K;i>=0;i–)

        for (int j=N-K;j>=0;j–)

        {

            fM_N[i][j]=g[i+K-1][j+K-1];

            if (i<M-1) update(fM_N[i][j],fM_N[i+1][j]);

            if (j<N-1) update(fM_N[i][j],fM_N[i][j+1]);

            //printf(“fM_N[%d][%d]=%d\n”,i+1,j+1,fM_N[i][j]);

        }

 

    //CASE 1 2 3 4

    for (int i=K-1;i<=M-K;i++)

        for (int j=K-1;j<=N-K;j++)

            update_case1234(i,j);

    //CASE 5

    update_case5();

    //CASE 6

    update_case6();

    printf(“%d\n”,answer);

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}

 

void update_case1234(int a,int b)

{

    //CASE 1

    if (a<M-1&&b<N-1)

        update(answer,f1_1[a][b]+f1_N[a][b+1]+fM_N[a+1][0]);

    //CASE 2

    if (a>0&&b<N-1)

        update(answer,fM_1[a][b]+fM_N[a][b+1]+f1_N[a-1][0]);

    //CASE 3

    if (a<M-1&&b<N-1)

        update(answer,f1_1[a][b]+fM_1[a+1][b]+fM_N[0][b+1]);

    //CASE 4

    if (a<M-1&&b>0)

        update(answer,f1_N[a][b]+fM_N[a+1][b]+fM_1[0][b-1]);

}

void update_case5()

{

    static int maxx3[4][MAXM];

    for (int k=1;k<=3;k++)

        for (int i=K-1;i<M;i++)

            if (i>=K&&maxx3[k][i-1]<maxx3[k-1][i-K]+maxx[i])

                maxx3[k][i]=maxx3[k-1][i-K]+maxx[i];

            else if (i<K&&maxx3[k][i-1]<maxx[i])

                maxx3[k][i]=maxx[i];

            else

                maxx3[k][i]=maxx3[k][i-1];

    //printf(“case5=%d\n”,maxx3[3][M-1]);

    if (answer<maxx3[3][M-1]) answer=maxx3[3][M-1];

}

void update_case6()

{

    static int maxy3[4][MAXN];

    for (int k=1;k<=3;k++)

        for (int i=K-1;i<N;i++)

            if (i>=K&&maxy3[k][i-1]<maxy3[k-1][i-K]+maxy[i])

                maxy3[k][i]=maxy3[k-1][i-K]+maxy[i];

            else if (i<K&&maxy3[k][i-1]<maxy[i])

                maxy3[k][i]=maxy[i];

            else

                maxy3[k][i]=maxy3[k][i-1];

    //printf(“case6=%d\n”,maxy3[3][N-1]);

    if (answer<maxy3[3][N-1]) answer=maxy3[3][N-1];

}

 

先选两个来确定公园，然后判断。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-16

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define MAXM 100

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

 

int L,A;

int M;

struct Record

{

       int p;

       int a;

       int x,y;

};

Record record[MAXM];

 

inline

void check(int left,int bottom,int& get_min)

{

     int right=left+A;

     int top=bottom+A;

     if (left<1||right>L+1||bottom<1||top>L+1) return;

     int get_max=1;

     for (int i=0;i<M;i++)

     {

         int cleft=max(record[i].x,left);

         int cright=min(record[i].x+record[i].a,right);

         int cbottom=max(record[i].y,bottom);

         int ctop=min(record[i].y+record[i].a,top);

         if (cleft<cright&&cbottom<ctop)

            get_max=max(get_max,record[i].p);

     }

     get_min=min(get_min,get_max);

}

 

int main()

{

    scanf(“%d %d\n%d\n”,&L,&A,&M);

    for (int i=0;i<M;i++)

        scanf(“%d %d %d %d\n”,&record[i].p,

                              &record[i].a,

                              &record[i].x,

                              &record[i].y);

    record[M].p=1;

    record[M].a=L;

    record[M].x=1;

    record[M].y=1;

    M++;

    int get_min=255;

    int left,bottom;

    for (int i=0;i<M;i++)

    {

        left=record[i].x;

        for (int j=0;j<M;j++)

        {

            bottom=record[j].y;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a;

            check(left,bottom,get_min);

            bottom=record[j].y-A;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a-A;

            check(left,bottom,get_min);

        }

        left=record[i].x+record[i].a;

        for (int j=0;j<M;j++)

        {

            bottom=record[j].y;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a;

            check(left,bottom,get_min);

            bottom=record[j].y-A;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a-A;

            check(left,bottom,get_min);

        }

        left=record[i].x+record[i].a-A;

        for (int j=0;j<M;j++)

        {

            bottom=record[j].y;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a;

            check(left,bottom,get_min);

            bottom=record[j].y-A;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a-A;

            check(left,bottom,get_min);

        }

        left=record[i].x-A;

        for (int j=0;j<M;j++)

        {

            bottom=record[j].y;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a;

            check(left,bottom,get_min);

            bottom=record[j].y-A;

            check(left,bottom,get_min);

            bottom=record[j].y+record[j].a-A;

            check(left,bottom,get_min);

        }

    }

    if (get_min<=100) printf(“%d\n”,get_min);

    else printf(“IMPOSSIBLE\n”);

    return 0;

}

 

 

水水的BFS，注意图是有向的。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-15

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define MAXNODE 2000

 

int K;

int map[MAXNODE][MAXNODE];

int T;

int S1,S2;

 

int main()

{

    scanf(“%d\n”,&K);

    for (int i=1;i<=K;i++)

    {

        int u,v;

        scanf(“%d %d\n”,&u,&v);

        map[u-1][v-1]=i;

    }

    scanf(“%d %d %d\n”,&T,&S1,&S2);

   

    bool inq[MAXNODE];

    int q[MAXNODE];

    int open=0,close=0;

    int dis[MAXNODE];

    int pre[MAXNODE];

    memset(inq,false,sizeof(inq));   

    inq[q[open++]=S1-1]=true;

    pre[S1-1]=S1-1;

    dis[S1-1]=0;

    inq[q[open++]=S2-1]=true;

    pre[S2-1]=S2-1;

    dis[S2-1]=0;

    while (close<open)

    {

          int now=q[close++];

          for (int i=0;i<MAXNODE;i++)

              if (map[now][i]&&!inq[i])

              {

                 inq[q[open++]=i]=true;

                 pre[i]=now;

                 dis[i]=dis[now]+1;

              }

    }

    if (inq[T-1])

    {

       printf(“%d\n”,dis[T-1]);       

       int s[MAXNODE];

       int top=0;

       int u=T-1;

       while (pre[u]!=u)

             u=pre[s[top++]=u];

       s[top++]=u;

       for (int i=top-1;i>0;i–)

           printf(“%d\n”,map[s[i]][s[i-1]]);

    }

    else printf(“IMPOSSIBLE\n”);

    return 0;

}

 

 

恩，因为一定有1，2，3，4。而且1234可以组合出mod7的值为0到6的数，所以就先留下一组1234，其他直接输出（注意0不能开头），然后用1234来将mod7的值配成0。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-15

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define MAXLEN 20

 

int N;

char num[MAXLEN+1];

int counter[10];

 

int main()

{

    scanf(“%d\n”,&N);

    for (int i=0;i<N;i++)

    {

        scanf(“%s\n”,num);

        memset(counter,0,sizeof(counter));

        for (char* j=num;*j;j++)

            counter[*j-‘0’]++;

        int mod7=0;

        for (int j=9;j>4;j–)

            for (int k=0;k<counter[j];k++)

            {

                printf(“%d”,j);

                mod7=(mod7*10+j)%7;

            }

        for (int j=4;j>0;j–)

            for (int k=1;k<counter[j];k++)

            {

                printf(“%d”,j);

                mod7=(mod7*10+j)%7;

            }

        for (int k=-4;k<counter[0];k++)

            mod7=(mod7*10)%7;

        int mod1234=1;

        for (int k=0;k<counter[0];k++)

            mod1234=(mod1234*10)%7;

        bool printed=false;

        for (int i1=1;i1<=4&&!printed;i1++)

            for (int i2=1;i2<=4&&!printed;i2++)

                for (int i3=1;i3<=4&&!printed;i3++)

                    for (int i4=1;i4<=4&&!printed;i4++)

                        if (i1!=i2&&i1!=i3&&i1!=i4

                            &&i2!=i3&&i2!=i4

                            &&i3!=i4)

                           if (((i1*1000+i2*100+i3*10+i4)*mod1234+mod7)%7==0)

                           {

                              printf(“%d%d%d%d”,i1,i2,i3,i4);

                              printed=true;

                           }

        for (int k=0;k<counter[0];k++)

            printf(“0”);

        printf(“\n”);

    }

    return 0;

}

 

 

然后，水题，当然就是直接模拟啦。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-14

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define WIDTH 80

 

int pos;

char get;

char screen[WIDTH];

 

int main()

{

    memset(screen,’ ‘,sizeof(screen));

    while (scanf(“%c”,&get)!=EOF)

    {

          if (get==’\n’) continue;

          if (get=='<‘) pos–;

          else if (get==’>’) pos++;

          else screen[pos++]=get;

          if (pos==-1) pos++;

          if (pos==WIDTH) pos-=WIDTH;

    }

    printf(“%s\n”,screen);

}

 

 

几何题，然后解一下方程就行，然后注意浮点误差。

具体思路看注释。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-14

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <math.h>

 

#define g 10.0f

#define zero(n) (-1e-9<=n&&n<=1e-9)

#define oo 1e16

 

struct Point

{

       double x,y,z;

       Point(){}

       Point(double _x,double _y,double _z):x(_x),y(_y),z(_z){}

};

 

Point C,N,S,V;

double R;

 

bool check(double t)

{

     if (t<0) return false;

     Point M(S.x+V.x*t,S.y+V.y*t,S.z+V.z*t-(g*t*t)/2);

     Point d(M.x-C.x,M.y-C.y,M.z-C.z);

     double distance_sqr=d.x*d.x+d.y*d.y+d.z*d.z;

     if (distance_sqr<R*R) return true;

     else return false;

}

 

int main()

{

    scanf(“%lf %lf %lf %lf %lf %lf %lf\n”

          “%lf %lf %lf %lf %lf %lf\n”,

          &C.x,&C.y,&C.z,&N.x,&N.y,&N.z,&R,

          &S.x,&S.y,&S.z,&V.x,&V.y,&V.z);

    /*

    M=S+V*t+(0,0,-(g*t^2)/2)

    (M-C)*N=0

    distance(M,C)<R

    有解?HIT:MISSED

   

    (M-C)*N=0

    => (Mx-Cx)*(Nx)+(My-Cy)*(Ny)+(Mz-Cz)*(Nz)=0

    => (Sx+Vx*t-Cx)*(Nx)+(Sy+Vy*t-Cy)*(Ny)+(Sz+Vz*t-(g*t^2)/2-Cz)*(Nz)=0

    => (-g*Nz)/2*t^2

       +(Vx*Nx+Vy*Ny+Vz*Nz)*t

       +(Sx*Nx+Sy*Ny+Sz*Nz-Cx*Nx-Cy*Ny-Cz*Nz)

       =0

    */

    bool have_answer=false;

    double a=(-g*N.z)/2,

           b=(V.x*N.x+V.y*N.y+V.z*N.z),

           c=(S.x*N.x+S.y*N.y+S.z*N.z-C.x*N.x-C.y*N.y-C.z*N.z);

    double t;

    if (!zero(a))

    {

       double delta=b*b-4.0*a*c;

       if (delta>0||zero(delta))

       {

          if (zero(delta)) delta=0;

          double t1=(-b+sqrt(delta))/(2*a),

                 t2=(-b-sqrt(delta))/(2*a);

          if (t1>=0)

            if (check(t=t1))

               have_answer=true;

          if (t2>=0)

            if (check(t=t2))

               have_answer=true;

       }

    }

    else

    {

        if (!zero(b))

           if (check(t=-c/b))

              have_answer=true;

    }

   

    if (have_answer) printf(“HIT\n”);

    else printf(“MISSED\n”);

    return 0;

}

 

 

这是做URAL以来提交次数最多的一道题，而且还是看着题解做的，无语死了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-14

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <assert.h>

 

#define MAXN 20

 

int N;

char map[MAXN*2+1][MAXN*2+1];

 

void print()

{

     /*

     for (int i=0;i<N*2+1;i++)

     {

         for (int j=0;j<N*2+1;j++)

             printf(“%c”,map[i][j]);

         printf(“\n”);

     }

     */

}

inline

void change(char& who)

{

     if (who==’+’) who=’-‘;

     else who=’+’;

}

 

void shift(int a,int b,int c,int d)

{

     change(map[a][d]);

     change(map[a][b]);

     change(map[c][b]);

     change(map[c][d]);

     for (int i=0;i<N*2+1;i++)

     {

         if (i==a) printf(“%d”,b+1);

         else if (i==c) printf(“%d”,d+1);

         else if (i==b) printf(“%d”,a+1);

         else if (i==d) printf(“%d”,c+1);

         else printf(“%d”,i+1);

         if (i+1==N*2+1) printf(“\n”);

         else printf(” “);

     }

     for (int i=0;i<N*2+1;i++)

     {

         if (i==a) printf(“%d”,d+1);

         else if (i==c) printf(“%d”,b+1);

         else if (i==b) printf(“%d”,a+1);

         else if (i==d) printf(“%d”,c+1);

         else printf(“%d”,i+1);

         if (i+1==N*2+1) printf(“\n”);

         else printf(” “);

     }

     print();

}

 

int main()

{

    scanf(“%d\n”,&N);

    for (int i=0;i<N*2+1;i++)

    {

        for (int j=0;j<N*2+1;j++)

            scanf(“%c”,&map[i][j]);

        scanf(“\n”);

    }

    printf(“There is solution:\n”);

    int counter=0;

    for (int i=0;i<N*2+1;i++)

        for (int j=0;j<N*2+1;j++)

            if (map[i][j]==’+’)

               counter++;

    if (counter%2)

       for (int i=0;i<N*2+1;i++)

       {

           change(map[i][i]);

           printf(“%d”,i+1);

           if (i+1==N*2+1) printf(“\n”);

           else printf(” “);

       }

    print();

    for (int i=0;i<N*2+1;i++)

    {

        int j=N*2+1–1,_j,k=N*2+1–1,_k;

        while (j>i)

        {

              while ((j>i)&&(map[i][j]!=’+’)) j–;

              _j=j;

              j–;

              while ((j>i)&&(map[i][j]!=’+’)) j–;

              if (j>i) shift(i,j,N*2+1–1,_j);

              else break;

              _j=-1;

        }

        if (_j>i) shift(i,i,N*2+1–1,_j);

        while (k>i)

        {

              while ((k>i)&&(map[k][i]!=’+’)) k–;

              _k=k;

              k–;

              while ((k>i)&&(map[k][i]!=’+’)) k–;

              if (k>i) shift(k,i,_k,N*2+1–1);

              else break;

              _k=-1;

        }

        if (_k>i&&map[i][i]==’+’) shift(i,i,_k,N*2+1–1);

    }

    return 0;

}

 

 

看到题目的数据规模，马上想到直接搜索。但是TLE#2，然后加入一个减枝，然后TLE#8，然后优化常数一次TLE#8，然后用构造法做AC，然后在搜索中加入又一个减枝，然后又一次AC。

然后，只给出搜索的代码。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-13

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int K,S;

      vector<int> a;

      int answer;

      void search(int begin,int rest,int pre_gcd)

      {

           if (answer==10000) return;

           if (rest)

           {

              rest–;

              for (a[rest]=begin;a[rest]<=S;)

              {

                  int _a=a[rest],_b=pre_gcd;

                  int _t;

                  while (_b) _t=_a,_b=_t%(_a=_b);

                  a[rest]++;

                  if (_a!=1&&(S-a[rest]+1>=rest))

                  {

                     search(a[rest],rest,_a);

                     if (answer==10000) return;

                  }

              }

           }

           else answer++;

      }

      public:

      Application()

      {

                   cin>>K>>S;

      }

      int run()

      {

          answer=0;

          a.resize(K);

          search(2,K,0);

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

哎呀，又是线段树，我发觉自己好讨厌线段树啊，又写了很久耶，恩。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-12

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      int N,K;

      vector<vector<int> > data;

      int answer;

      static int count(const vector<int>& bst,int root,int l,int r,int c)

      {

             if (l>=c) return bst[root];

             if (l<r)

             {

                int g=0;

                int mid=(l+r)/2;

                if (l<=c)

                   g+=count(bst,(root*2),l,mid,c);

                if (c<=r)

                   g+=count(bst,(root*2)+1,mid+1,r,c);

                return g;

             }

             return 0;

      }

      static void insert(vector<int>& bst,int root,int l,int r,int i)

      {

             bst[root]++;

             if (l<r)

             {

                int mid=(l+r)/2;

                if (l<=i&&i<=mid)

                   insert(bst,(root*2),l,mid,i);

                if (mid+1<=i&&i<=r)

                   insert(bst,(root*2)+1,mid+1,r,i);

             }

      }

      public:

      Application()

      {

                   cin>>N>>K;

                   data.resize(K,vector<int>(N));

                   for (int i=0;i<K;i++)

                       for (int j=0;j<N;j++)

                       {

                           int get;

                           cin>>get;

                           data[i][j]=get-1;

                       }

      }

      int run()

      {

          int max=-1;

          for (int i=0;i<K;i++)

          {

              vector<int> bst(N*2*2,0);

              int total=0;

              for (int j=0;j<N;j++)

              {

                  int get=count(bst,1,0,N-1,data[i][j]);

                  total+=get;

                  insert(bst,1,0,N-1,data[i][j]);

              }

              if (total>max)

              {

                 max=total;

                 answer=i+1;

              }

          }

          cout<<answer<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，不说。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-12

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

using std::priority_queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int my_EOF=-1;

      vector<string> vocabulary;

      string content;

      int mistakes;

      public:

      Application()

      {

                   {

                       string get;

                       while (cin>>get)

                             if (get==“#”)

                             {

                                while (cin.get()!=’\n’);

                                break;

                             }

                             else vocabulary.push_back(get);

                   }

                   {

                       char get;

                       while ((get=cin.get())!=my_EOF) content.push_back(get);

                   }

      }

      int run()

      {

          mistakes=0;

          for (int i=0,j;;i=j)

          {

              while ((i<content.length())

                     &&(!(‘a'<=content[i]&&content[i]<=’z’))) i++;

              if (i>=content.length()) break;

              j=i;

              while (‘a'<=content[j]&&content[j]<=’z’) j++;

              string word=content.substr(i,j-i);

              for (int j=0;j<vocabulary.size();j++)

                  if (vocabulary[j].length()==word.length())

                  {

                     int difference=0;

                     for (int k=0;k<word.length();k++)

                         if (vocabulary[j][k]!=word[k]) difference++;

                     if (difference==1)

                     {

                        mistakes++;

                        for (int k=0;k<word.length();k++)

                            content[i+k]=vocabulary[j][k];

                        break;

                     }

                  }

          }

          cout<<content<<mistakes<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}