Boleyn Su's Blog

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

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();

}

 

 

本来挺水的题，却把我水惨了。

注意（我就是因此被水）：用01串存一个节点的位置时，若深度为N，则编号0到2^N-1（满二叉树），也就是说题目中的Ep和Dp要减个一。

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

{

      typedef int bit;

      bit D,E,F,Dp,Ep,H;

      static bit abs(bit a)

      {

             return a>=0?a:-a;

      }

      public:

      Application()

      {

                   cin>>D>>E>>F>>Dp>>Ep>>H;

      }

      int run()

      {

          bit cut=(~0);

          bit need=0;

          for (;;cut<<=1,need++)

              if (((Dp-1)&cut)==((Ep-1)&cut))

              {

                 if (D>=need&&E>=need) need=abs(D-E);

                 else need=abs(D-need)+abs(E-need);

                 if (need<=H) cout<<“YES”<<endl;

                 else cout<<“NO”<<endl;

                 break;

              }

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}