Boleyn Su's Blog

水题，不说。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-3

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;

#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;

      static int abs(int a)

      {

             return a>0?a:-a;

      }

      public:

      Application()

      {

                   cin>>N;

      }

      int run()

      {

          cout<<(N+1)*(abs(N-1)+1)/2<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，不说。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-3

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;

#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;

 

struct FileTree

{

       string node;

       map<string,FileTree> child;

       void add(const string& path)

       {

            int end=path.find(‘\\’);

            if (end!=-1)

               child[path.substr(0,end)]

               .add(path.substr(end+1,path.length()));

            else

               child[path.substr(0,end)];

       }

       void print(const string& pre=“”)

       {

            for (map<string,FileTree>::iterator it=child.begin();

                 it!=child.end();it++)

            {

                cout<<pre<<it->first<<endl;

                it->second.print(” “+pre);

            }

       }

};

 

class Application

{

      int N;

      FileTree ft;

      public:

      Application()

      {

      }

      int run()

      {

          cin>>N;

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

          {

              string path;

              cin>>path;

              ft.add(path);

          }

          ft.print();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

数学题。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-8

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <iomanip>

 

#include <cstring>

using std::memset;

 

#define oo 1e10

#define MAXN 1000

 

int N;

double A;

double B;

 

void read()

{

     cin>>N>>A;

}

void write()

{

     cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);

     cout<<B<<endl;

}

void solve()

{

     /*

     h[i]=(h[i-1]+h[i+1])/2-1

     h[i]*2+2=(h[i-1]+h[i+1])

     h[i+1]=h[i]*2+2-h[i-1]

     h[i]=h[i-1]*2-h[i-2]+2

     h[i]-h[i-1]=h[i-1]-h[i-2]+2

    

     令a[i]=h[i]-h[i-1]

     则a[2]=h[2]-h[1]

       a[i]=a[i-1]+2

     所以a[i]=a[2]+(i-2)*2

     h[i]=h[i]-h[i-1]+h[i-1]-h[i-2]+…+h[2]-h[1]+h[1]

         =a[i]       +a[i-1]       +…+a[2]     +h[1]

         =sum{a[j],2<=j<=i}+h[1]

         =sum{(a[2]+(j-2)*2),2<=j<i}+h[1]

         =(i-2+1)*a[2]+(0+(i-2)*2)*(i-2+1)/2+h[1]

         =(i-1)*(h[2]-h[1])+(i-2)*(i-1)+h[1]

         =(i-1)*h[2]-(i-2)*h[1]+(i-2)*(i-1)

     */

     double h[MAXN+2];

     h[1]=A;

     B=oo;

     for (int i=2;i<=N;i++)//假设其中一个贴地

     {

         h[i]=0;

         h[2]=(h[i]-(i-2)*(i-1)+(i-2)*h[1])/(i-1);

        

         bool can=true;

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

         {

             h[j]=(j-1)*h[2]-(j-2)*h[1]+(j-2)*(j-1);

             if (h[j]<0)

             {

                can=false;

                break;

             }

         }

         if (can)

            if (B>h[N]) B=h[N];

     }

}

 

int main()

{

    read();

    solve();

    write();

    return 0;

}

 

 

恩，有点计算几何的知识，还有动态规划。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-8

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <iomanip>

 

#include <cmath>

using std::sqrt;

#include <cstring>

using std::memset;

 

#define oo 1e10

#define MAXN 50

#define MAXM 1000

 

typedef long long int Type;

struct Point{Type x,y;};

 

int N,M;

Point outter[MAXN];

Point inner[MAXM];

double answer;

 

void read()

{

     cin>>N>>M;

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

         cin>>outter[i].x>>outter[i].y;

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

         cin>>inner[i].x>>inner[i].y;

}

void write()

{

     cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);

     cout<<answer<<endl;

}

 

Type cross(const Point& a,const Point& b,const Point& c)

{

     Type abx=b.x-a.x,

          aby=b.y-a.y,

          acx=c.x-a.x,

          acy=c.y-a.y;

     return abx*acy-aby*acx;

}

bool sameside(const Point& a,const Point& b,const Point& c,const Point& d)

{

     return cross(a,b,c)*cross(a,b,d)>=0;

}

bool inside(const Point& a,const Point& b,const Point& c,const Point& d)

{

     return sameside(a,b,c,d)&&sameside(a,c,b,d)&&sameside(b,c,a,d);

}

double distance(const Point& a,const Point& b)

{

       return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));

}

void solve()

{

     bool can[MAXN][MAXN];

     memset(can,0,sizeof(can));

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

     {

         bool flag=true;

         for (int j=i+1;j<N+i;j++)

         {

             if (cross(outter[i],outter[j%N],outter[(j-1)%N])!=0)

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

                    if (inside(outter[i],outter[j%N],outter[(j-1)%N],inner[k]))

                    {

                       flag=false;

                       break;

                    }

             if (flag) can[i][j%N]=true;

         }

     }

    

     double map[MAXN][MAXN];

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

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

             if (can[i][j]) map[i][j]=distance(outter[i],outter[j]);

             else map[i][j]=oo;

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

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

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

                 if (map[i][k]+map[k][j]<map[i][j])

                    map[i][j]=map[i][k]+map[k][j];

    

     answer=oo;

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

         for (int j=i+1;j<N;j++)

             for (int k=j+1;k<N;k++)

                 if (cross(outter[i],outter[j],outter[k])!=0)

                    if (map[i][j]+map[j][k]+map[k][i]<answer)

                       answer=map[i][j]+map[j][k]+map[k][i];

}

 

 

int main()

{

    read();

    solve();

    write();

    return 0;

}

 

 

其实，就是简单模拟。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-7

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;

#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 MAXN=10000;

      int i,L;

      int BinarySearch(int x,int N)

      {

          int p, q, i, L;         

          p = 0;   /* Left border of the search  */

          q = N-1; /* Right border of the search */

          L = 0;   /* Comparison counter         */

          while (p <= q)

          {

                i = (p + q) / 2;

                ++L;

                if (i == x)

                   return L;

                if (x < i)

                   q = i – 1;

                else

                    p = i + 1;

          }

          return –1;

      }

      public:

      Application()

      {

                   cin>>i>>L;

      }

      int run()

      {

          int counter=0;

          stringstream sout;

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

          {

              if (BinarySearch(i,j)==L)

              {

                 sout<<j<<” “;

                 while ((j+1<=MAXN)&&(BinarySearch(i,j+1)==L)) j++;

                 sout<<j<<endl;

                 counter++;

              }

          }

          cout<<counter<<endl;

          cout<<sout.str();

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

图论题，先要知道，一个无向图存在欧拉路，当且仅当此图为强连通图，且度数为奇的节点数为0或2。

然后要做的就是先将图强联通，然后贪心加边。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-6

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;

#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 oo=~(1<<31);

      static const int SIDE=6;

      vector<vector<int> > c;

      vector<int> degree;

      //GET PART

      vector<int> getid;

      void dfs(int id,stack<int>& s)

      {

           static vector<bool> visited(SIDE,false);

           if (!visited[id])

           {

              visited[id]=true;

              s.push(id);

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

                  if (c[id][i])

                     dfs(i,s);

           }

      }

      void get_part()

      {

           vector<vector<int> > part;

           getid.resize(SIDE);

           stack<int> s;

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

           {

               if (degree[i])

               {

                  dfs(i,s);

                  if (!s.empty())

                  {

                     part.push_back(vector<int>());

                     while (!s.empty())

                           part.back().push_back(s.top()),

                           getid[s.top()]=part.size(),

                           s.pop();

                  }

               }

           }

      }

      //END GET PART

      //GET ANSWER

      int answer;

      vector<pair<int,int> > list;

      bool check()

      {

           vector<vector<bool> > link(SIDE,vector<bool>(SIDE,false));

          

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

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

                   link[i][j]=c[i][j]||i==j;

          

           for (int k=0;k<SIDE;k++)

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

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

                       if (link[i][k]&&link[k][j])

                          link[i][j]=true;

          

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

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

                   if (degree[i]&&degree[j]&&(!link[i][j])) return false;

          

           return true;

      }

      void update(vector<pair<int,int> >& record)

      {

           int nanswer=0;

           for (int i=0;i<record.size();i++)

               nanswer+=record[i].first+1+record[i].second+1;

           vector<pair<int,int> > nlist(record);

          

           int counter=0;

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

               if (degree[i]%2) counter++;

           vector<int> add;

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

           {

               if (counter==2||counter==0) break;

               if (degree[i]%2)

               {

                  nanswer+=i+1;

                  counter–;

                  add.push_back(i);

               }

           }

           for (int i=0;i<add.size();i+=2)

               nlist.push_back(make_pair(add[i],add[i+1]));

          

           if (nanswer<answer)

           {

              answer=nanswer;

              list=nlist;

           }

      }

      void search(const vector<int>& getid)

      {

           static vector<pair<int,int> > record;

           set<int> part;

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

               if (getid[i])

                  part.insert(getid[i]);

          

           if (part.size()>1)

           {

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

                  for (int j=i+1;j<SIDE;j++)

                      if (degree[i]&&degree[j]&&getid[i]!=getid[j])

                      {

                         vector<int> ngetid=getid;

                         for (int k=0;k<SIDE;k++)

                             if (getid[k]==getid[i])

                                ngetid[k]=ngetid[j];

                         c[i][j]++;

                         c[j][i]++;

                         degree[i]++;

                         degree[j]++;

                         record.push_back(make_pair(i,j));

                         search(ngetid);

                         record.pop_back();

                         degree[j]–;

                         degree[i]–;

                         c[j][i]–;

                         c[i][j]–;

                      }

           }

           else

           {

               if (check())

                  update(record);

           }

      }

      //END GET ANSWER

      public:

      Application()

                   :c(SIDE,vector<int>(SIDE,0)),degree(SIDE,0)

      {

                   int N;

                   cin>>N;

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

                   {

                       int u,v;

                       cin>>u>>v;

                       c[u-1][v-1]++;

                       c[v-1][u-1]++;

                       degree[u-1]++;

                       degree[v-1]++;

                   }

      }

      int run()

      {

          get_part();

          answer=oo;

          search(getid);

          cout<<answer<<endl;

          cout<<list.size()<<endl;

          for (int i=0;i<list.size();i++)

              cout<<list[i].first+1<<” “<<list[i].second+1<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

半平面交，然后先暂时用O(n^2)的过了。

半平面交O(n^2)，一共这样做n次，总的时间复杂度O(n^3)。

半平面交有O(nlogn)的分治法，不过现在还不会。

然后讲一下O(n^2)的半平面交：

先有一个凸包{(-oo,-oo),(oo,-oo),(oo,oo),(-oo,oo)}（点有序），然后用线依次去切。

对凸包上的点：

1.如果它不被切掉，保留它(如下图中的绿线切C点)；

2.它被切掉，先丢掉它（如下图中的红线切A点），然后如果与它相邻的点不被切掉（相邻指按级角排序后的顺序中相邻），那么加入它与相邻点所在直线与切割线的交点（如下图中的蓝线切B点，加入的是两个红点）。

主要思路就是这样了。

CODE:

//DATE:2010-4-1

#include <cstdio>

using std::printf;

using std::scanf;

#include <cstring>

using std::memcpy;

 

#define MAXN 100

#define KIND 3

#define oo 1e10

#define zero 1e-10

 

typedef int Player[MAXN][KIND];

struct Point{double x,y;};

struct Line{double a,b,c;};

 

int N;

Player player;

Line line[MAXN];

bool canWin[MAXN];

 

void read()

{

     scanf(“%d”,&N);

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

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

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

}

void write()

{

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

         if (canWin[i]) printf(“Yes\n”);

         else printf(“No\n”);

}

void initLines()

{

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

         line[i].a=1.0/player[i][0],

         line[i].b=1.0/player[i][1],

         line[i].c=1.0/player[i][2];

}

Point intersect(Line l,Point a,Point b)

{

      Point get;

      double fa=l.a*a.x+l.b*a.y+l.c;

      double fb=l.a*b.x+l.b*b.y+l.c;

      get.x=(fb*a.x-fa*b.x)/(fb-fa);

      get.y=(fb*a.y-fa*b.y)/(fb-fa);

      return get;

}

void cut(Point* p,int& pn,Line cutter)

{

     Point q[MAXN+4];

     int qn=0;

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

     {

         if (p[i].x*cutter.a+p[i].y*cutter.b+cutter.c>zero)

            q[qn++]=p[i];

         else

         {

             int before=(i-1+pn)%pn;

             int next=(i+1)%pn;

             if (p[before].x*cutter.a+p[before].y*cutter.b+cutter.c>zero)

                q[qn++]=intersect(cutter,p[before],p[i]);

             if (p[next].x*cutter.a+p[next].y*cutter.b+cutter.c>zero)

                q[qn++]=intersect(cutter,p[i],p[next]);

         }

     }

     memcpy(p,q,sizeof(q));

     pn=qn;

}

bool isEmpty(Line* l,int n)

{

     Point p[MAXN+4];

     int pn=0;

     p[pn].x=0;

     p[pn].y=0;

     pn++;

     p[pn].x=oo;

     p[pn].y=0;

     pn++;

     p[pn].x=oo;

     p[pn].y=oo;

     pn++;

     p[pn].x=0;

     p[pn].y=oo;

     pn++;

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

         cut(p,pn,l[i]);

     return pn<3;

    

}

bool can(int id)

{

     Line l[MAXN];

     memcpy(l,line,sizeof(line));

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

         if (i!=id)

            l[i].a-=l[id].a,

            l[i].b-=l[id].b,

            l[i].c-=l[id].c;

     l[id]=l[N-1];

     if (isEmpty(l,N-1)) return false;

     else return true;

}

void solve()

{

     initLines();

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

         canWin[i]=can(i);

}

int main()

{

    read();

    solve();

    write();

    return 0;

}

 

 

水题，数学题，在长度为L的数列中求长度为K的和最小的连续子数列。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-30

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;

#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 long long int oo=1000000000;

      int N,K,L;

      vector<long long int> data;

      vector<long long int> sum;

      public:

      Application()

      {

                   cin>>N>>K;

                   data.resize(N);

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

                   {

                       char c;

                       cin>>c;

                       if (c==’*’) data[i]=oo;

                       else data[i]=c-‘0’;

                   }

      }

      int run()

      {

          sum.resize(N+1);

          sum[0]=0;

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

              sum[i+1]=sum[i]+data[i];

         

          long long int min=oo;

          L=0;

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

              if (sum[i+K]-sum[i]<min)

              {

                 L=i+1;

                 min=sum[i+K]-sum[i];

              }

          cout<<L<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

水题，BFS就行了。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-30

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;

#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;

 

struct State

{

       static const int SIZE=4;

       bool map[SIZE][SIZE];

       int id;

       void getId()

       {

            id=0;

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

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

                {

                    id<<=1;

                    if(map[i][j]) id++;

                }

       }

       void read()

       {

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

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

                {

                    char c;

                    cin>>c;

                    map[i][j]=(c==’w’);

                }

            getId();

       }

       void set(bool what)

       {

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

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

                    map[i][j]=what;

            getId();

       }

       void turn(int x,int y)

       {

            map[x][y]=!map[x][y];

            if (x-1>=0) map[x-1][y]=!map[x-1][y];

            if (x+1<SIZE) map[x+1][y]=!map[x+1][y];

            if (y-1>=0) map[x][y-1]=!map[x][y-1];

            if (y+1<SIZE) map[x][y+1]=!map[x][y+1];

            getId();

       }

       void print()

       {

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

            {

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

                    cout<<map[i][j];

                cout<<endl;

            }

       }

};

 

class Application

{

      static const int NOTREACH=~(1<<31);

      State s,t1,t2;

      public:

      Application()

      {

                   s.read();

                   t1.set(true);

                   t2.set(false);

      }

      int run()

      {

          vector<int> step(1<<((State::SIZE)*(State::SIZE)),NOTREACH);

          queue<State> q;

         

          q.push(s);

          step[s.id]=0;

         

          while (!q.empty())

          {

                State& now=q.front();

                for (int i=0;i<State::SIZE;i++)

                    for (int j=0;j<State::SIZE;j++)

                    {

                        State get=now;

                        get.turn(i,j);

                        if (step[get.id]==NOTREACH)

                        {

                           q.push(get);

                           step[get.id]=step[now.id]+1;

                        }

                    }

                q.pop();

          }

          int answer=step[t1.id]<step[t2.id]?step[t1.id]:step[t2.id];

          if (answer==NOTREACH) cout<<“Impossible”<<endl;

          else cout<<answer<<endl;

         

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}

 

 

后缀表达式。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-30

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;

#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;

      public:

      Application()

      {

                   cin>>N;

      }

      int run()

      {

          cout<<0<<endl;

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

              cout<<“X”<<endl<<“*”<<endl<<i<<endl<<“+”<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}