URAL1007[Code words]

水题,不说了。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-12


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <cassert>


//using std::assert;


 


class Application


{


      public:


      int run()


      {


          int n;


          cin>>n;


          string word;


          while (cin>>word)


          {


                int sum;


                if (word.length()==n)


                {


                   sum=0;


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


                       sum+=(word[i]==’1′?i+1:0);


                   if (sum%(n+1)==0) cout<<word<<endl;


                   else


                   {


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


                           if ((word[i]==’1′)&&(((sum-(i+1))%(n+1))==0))


                           {


                              word[i]=’0′;


                              break;


                           }


                       cout<<word<<endl;


                   }


                }


                if (word.length()==n+1)


                {


                   int insert;


                   for (insert=0;insert<n+1;insert++)


                   {


                       sum=0;


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


                           if (word[i]==’1′)


                           {


                              if (i<insert) sum+=i+1;


                              else if (i>insert) sum+=i+11;


                           }


                       if (sum%(n+1)==0) break;


                   }


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


                       if (i!=insert) cout<<word[i];


                   cout<<endl;


                }


                if (word.length()==n-1)


                {


                   int remove;


                   bool is0;


                   for (remove=0;remove<n;remove++)


                   {


                       sum=0;


                       for (int i=0;i<n-1;i++) if (word[i]==’1′)


                           {


                              if (i<remove) sum+=i+1;


                              else if (i>=remove) sum+=i+1+1;


                           }


                       if (sum%(n+1)==0)


                       {


                          is0=true;


                          break;


                       }


                       if ((sum+remove+1)%(n+1)==0)


                       {


                          is0=false;


                          break;


                       }


                   }


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


                   {


                       if (i==remove) cout<<char(is0?’0′:’1′);


                       if (i<n-1)cout<<word[i];


                   }


                   cout<<endl;


                }


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1006[Square frames]

一道巨麻烦的题,但是没有多少算法上的价值。


枚举x,y,a一直找,如果找到(即每边都没有错误的点,即,不是该是的图案,又不是被覆盖了),就输出,并覆盖所有边框上的点。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-11


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <vector>


using std::vector;


#include <string>


//using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <cassert>


//using std::assert;


 


class Application


{


      typedef unsigned char uc;


      static const int W=50,H=20;


      static const uc LU=218,//Left upper corner


                      RU=191,//Right upper corner


                      LB=192,//Left bottom corner


                      RB=217,//Right bottom corner


                      VE=179,//Vertical (left and right) border line


                      HO=196,//Horizontal (top and bottom) border line


                      DO=46,//Dot


                      CO=0;//Cover


      uc pic[H][W];


      public:


      Application()


      {


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


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


                            cin>>pic[i][j];


      }


      int run()


      {


          bool update=true;


          stack<pair<pair<int,int>,int> > answer;


          while (update)


          {


                /*


                cout<<“updating…”<<endl;


                for (int x=0;x<H;x++)


                {


                    for (int y=0;y<W;y++)


                    {


                        switch(pic[x][y])


                        {


                                         case LU:cout<<‘/’;break;


                                         case RU:cout<<‘\\’;break;


                                         case LB:cout<<‘\\’;break;


                                         case RB:cout<<‘/’;break;


                                         case VE:cout<<‘|’;break;


                                         case HO:cout<<‘-‘;break;


                                         case DO:cout<<‘.’;break;


                                         case CO:cout<<‘ ‘;break;


                        }


                    }


                    cout<<endl;


                }


                */


                update=false;


                for (int x=0;x<H;x++)


                    for (int y=0;y<W;y++)


                        if (pic[x][y]==CO||pic[x][y]==LU)


                           for (int a=2;a<=H;a++)


                               if ((pic[x+a-1][y]==CO||pic[x+a-1][y]==LB)


                                  &&(pic[x][y+a-1]==CO||pic[x][y+a-1]==RU)


                                  &&(pic[x+a-1][y+a-1]==CO||pic[x+a-1][y+a-1]==RB))


                               {


                                  #define impossibleHO(x,y) ((x>=H)or(y>=W)or((pic[x][y]!=CO)&&(pic[x][y]!=HO)))


                                  #define impossibleVE(x,y) ((x>=H)or(y>=W)or((pic[x][y]!=CO)&&(pic[x][y]!=VE)))


                                  bool ispossible=true;


                                  bool L=false,R=false,U=false,B=false;


                                 


                                  if (pic[x][y]==LU) L=U=true;


                                  if (pic[x+a-1][y]==LB) L=B=true;


                                  if (pic[x][y+a-1]==RU) R=U=true;


                                  if (pic[x+a-1][y+a-1]==RB) R=B=true;


                                 


                                  for (int i=1;i<a-1;i++)


                                  {


                                      if (impossibleHO(x,y+i)


                                         ||impossibleHO(x+a-1,y+i)


                                         ||impossibleVE(x+i,y)


                                         ||impossibleVE(x+i,y+a-1))


                                      {


                                         ispossible=false;


                                         break;


                                      }


                                      if (pic[x][y+i]==HO) U=true;


                                      if (pic[x+a-1][y+i]==HO) B=true;


                                      if (pic[x+i][y]==VE) L=true;


                                      if (pic[x+i][y+a-1]==VE) R=true;


                                  }


                                  #define cover(x,y) pic[x][y]=CO;


                                  if (ispossible&&(L||R||U||B))


                                  {


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


                                     {


                                         cover(x,y+i);


                                         cover(x+a-1,y+i);


                                         cover(x+i,y);


                                         cover(x+i,y+a-1);


                                     }


                                     update=true;


                                     answer.push(make_pair(make_pair(y,x),a));


                                     //cout<<y<<” “<<x<<” “<<a<<endl;


                                  }


                                  #undef impossibleHO


                                  #undef impossibleVE


                                  #undef cover


                               }


          }


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


          while (!answer.empty())


          {


                cout<<answer.top().first.first<<” “


                    <<answer.top().first.second<<” “


                    <<answer.top().second<<endl;


                answer.pop();


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


URAL1005[Stone pile]

很水的背包,方程f[i]=f[i] or f[i-W[k]]。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-10


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <cassert>


//using std::assert;


 


class Application


{


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


      int N;


      vector<int> W;


      int total;


      public:


      Application()


                    :total(0)


      {


                    cin>>N;


                    W.resize(N);


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


                    {


                        cin>>W[i];


                        total+=W[i];


                    }


      }


      int run()


      {


          vector<bool> f(total+1,false);


          f[0]=true;


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


              for (int i=total;i>=W[k];i–)


                  f[i]=f[i] or f[i-W[k]];


         


          int answer=oo;


          for (int i=(total+1)/2;i<=total;i++)


          {


              if (f[i])


              {


                 answer=i*2-total;


                 break;


              }


          }


          cout<<answer<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1004[Sightseeing trip]

Floyd求最小环。



CODE:


/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-3-10
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <map>
//using std::map;
#include <stack>
using std::stack;
#include <queue>
using std::queue;
using std::pair;
using std::make_pair;
#include <cassert>
//using std::assert;

class Question
{
     
static const int oo=1<<29;
      vector<vector<
int> > map;
     
void print(stack<int>& s,vector<vector<int> >& mid,int u,int v)
      {
          
if (mid[u][v]<0)
           {
             
if (s.top()!=u) s.push(u);
             
if (s.top()!=v) s.push(v);
           }
          
else
           {
               print(s,mid,u,mid[u][v]);
               print(s,mid,mid[u][v],v);
           }
      }
     
public:
     
bool read()
      {
          
int N,M;
           cin>>N;
          
if (N==-1) return false;          
           cin>>M;
          
           map.resize(N,vector<
int>(N,oo));
          
          
for (int i=0;i<M;i++)
           {
              
int u,v,l;
               cin>>u>>v>>l;
               u–;
               v–;
              
//assert(u<N&&v<N);
               if (map[u][v]>l) map[u][v]=l;
              
if (map[v][u]>l) map[v][u]=l;
           }
          
return true;
      }
     
void solve()
      {
           vector<vector<
int> > dist,mid;
          
           dist=map;
           mid.resize(dist.size(),vector<
int>(dist.size(),-1));
          
          
int min=oo;
          
int min_i,min_j,min_k;
          
for (int k=0;k<dist.size();k++)
           {
              
for (int i=0;i<k;i++)
                  
for (int j=i+1;j<k;j++)
                   {
                      
//assert(i!=j&&i!=k&&j!=k);
                       if (min>(dist[j][i]+map[i][k]+map[k][j]))
                       {
                          min=dist[j][i]+map[i][k]+map[k][j];
                          min_i=i;
                          min_j=j;
                          min_k=k;
                       }
                   }
              
              
for (int i=0;i<dist.size();i++)
                  
for (int j=0;j<dist.size();j++)
                      
if (dist[i][j]>dist[i][k]+dist[k][j])
                          dist[i][j]=dist[i][k]+dist[k][j];
           }
          
          
if (min<oo)
           {
              dist=map;
              dist[min_i][min_k]=dist[min_k][min_i]=oo;
              dist[min_j][min_k]=dist[min_k][min_j]=oo;
             
             
for (int k=0;k<dist.size();k++)
                 
for (int i=0;i<dist.size();i++)
                     
for (int j=0;j<dist.size();j++)
                         
if (dist[i][j]>dist[i][k]+dist[k][j])
                          {
                             dist[i][j]=dist[i][k]+dist[k][j];
                             mid[i][j]=k;
                          }
             
              stack<
int> s;
             
              s.push(min_k);
              print(s,mid,min_i,min_j);
             
             
for (;;)
              {
                  cout<<s.top()+
1;
                  s.pop();
                 
if (s.empty())
                  {
                     cout<<endl;
                    
break;
                  }
                 
else cout<<” “;
              }
           }
          
else cout<<“No solution.”<<endl;
          
           map.clear();
      }
};

class Application
{
     
public:
      Application()
      {
      }
     
int run()
      {
          Question q;
         
while (q.read()) q.solve();
         
return 0;
      }
};

int main()
{
    Application app;
   
return app.run();
}

URAL1003[Parity]

(又见POJ1733,VIJOS1112)


有人用并查集还有哈希,不知道为什么,我没有用他们,就用了一个排序二叉树(STL中的std::map)。然后就AC了。


思路:


对每一个点,记录其前驱和后驱(如果有),以及到前驱和后驱的线段上1出现的奇偶性。


每次读入一条线段时,插入分四种情况:


URAL1003[Parity] - 天之骄子 - 天之骄子的家


黑线为某条已有线段。


黄线代表,左端与一条已有线段重合,且右端在这条线段及其衍生出的线段上,这样,就将图中第二条黑线段(左数,后同)分为第二红点到d和d到第三红点两条线段。


绿线代表,左端与一条已有线段重合,且右端在这条线段及其衍生出的线段外,这样,就在图中增加一条右端红点到f的线段。


粉红与蓝色线段同上面对称。


并且,这时候是不能推出矛盾的。


如果读入线段上的点不与任何已有线段有公共点,就直接插入,并且不能推出矛盾。


若两端都有公共点,就扫描整条线段,看是否有矛盾。


具体的还是看我的CODE吧。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-9


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <cstring>


using std::memset;


#include <string>


using std::string;


#include <vector>


using std::vector;


using std::pair;


using std::make_pair;


#include <map>


using std::map;


 


class Question


{


      int length;


      int Q;


      map<int,pair<int,bool> > record_l,record_r;


      bool dfs_judge_l(int l,int r,bool isEven)


      {


           map<int,pair<int,bool> >::iterator it;


           if ((it=record_l.find(l))!=record_l.end())


           {


              if (it->second.first==r)


                 return it->second.second==isEven;


              else if (it->second.first>r)


              {


                   //it->first to it->second.first it->second.second


                   record_l[r+1]=make_pair(it->second.first,isEven xor it->second.second);


                   //it->first to r isEven


                   it->second=make_pair(r,isEven);


                   return dfs_judge_r(r+1,record_l[r+1].first,record_l[r+1].second);


              }


              else


              {


                  return dfs_judge_l(it->second.first+1,r,isEven xor it->second.second);


              }


           }


           else


           {


               record_l[l]=make_pair(r,isEven);


               return true;


           }


      }


      bool dfs_judge_r(int l,int r,bool isEven)


      {


           map<int,pair<int,bool> >::iterator it;


           if ((it=record_r.find(r))!=record_r.end())


           {


              if (it->second.first==l)


                 return it->second.second==isEven;


              else if (it->second.first<l)


              {


                   //it->second.first to it->first it->second.second


                   record_r[l-1]=make_pair(it->second.first,isEven xor it->second.second);


                   //l to it->first isEven


                   it->second=make_pair(l,isEven);


                   return dfs_judge_l(record_r[l-1].first,l-1,record_r[l-1].second);


              }


              else


              {


                  return dfs_judge_r(l,it->second.first-1,isEven xor it->second.second);


              }


           }


           else


           {


               record_r[r]=make_pair(l,isEven);


               return true;


           }


      }


      public:


      bool read()


      {


           cin>>length;


           if (length==-1) return false;


           cin>>Q;


           return true;


      }


      void solve()


      {     


           int l,r;


           string answer;


          


           int answerq=1;


          


           for (;answerq<=Q;answerq++)


           {


               cin>>l>>r>>answer;


               if (!dfs_judge_l(l,r,answer==“odd”))  break;


               if (!dfs_judge_r(l,r,answer==“odd”))  break;


           }


           cout<<answerq-1<<endl;


          


           for (;answerq<Q;answerq++)


               cin>>l>>r>>answer;


           record_l.clear();


           record_r.clear();


      }


};


 


class Application


{


      public:


      int run()


      {


          Question q;


          while (q.read()) q.solve();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1002[Phone numbers]

动态规划。(又见POJ1732)


f[i]=min{f[j],从j到i可以被匹配}+1


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-8


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <cstring>


using std::memset;


#include <string>


using std::string;


#include <vector>


using std::vector;


#include <stack>


using std::stack;


 


class Question


{


      int get_num[256];


      string number;


      vector<string> dictionary;


      bool match(int f,int t,int id)


      {


           if (t-f!=dictionary[id].length()) return false;


           else


           {


               for (int i=f;i<t;i++)


                   if (get_num[dictionary[id][i-f]]!=(number[i]-‘0’)) return false;


               return true;


           }


      }


      public:


      Question()


      {


                get_num[‘a’]=2;


                get_num[‘b’]=2;


                get_num[‘c’]=2;


                get_num[‘d’]=3;


                get_num[‘e’]=3;


                get_num[‘f’]=3; 


                get_num[‘g’]=4;


                get_num[‘h’]=4;


                get_num[‘i’]=1;


                get_num[‘j’]=1;


                get_num[‘k’]=5;


                get_num[‘l’]=5;


                get_num[‘m’]=6;


                get_num[‘n’]=6;


                get_num[‘o’]=0;


                get_num[‘p’]=7;


                get_num[‘q’]=0;


                get_num[‘r’]=7;


                get_num[‘s’]=7;


                get_num[‘t’]=8;


                get_num[‘u’]=8;


                get_num[‘v’]=8;


                get_num[‘w’]=9;


                get_num[‘x’]=9;


                get_num[‘y’]=9;


                get_num[‘z’]=0;


      }


      bool read()


      {


           dictionary.clear();


           cin>>number;


           if (number==“-1”) return false;


          


           int n;


           cin>>n;


           while (n–)


           {


                 string get;


                 cin>>get;


                 dictionary.push_back(get);


           }


           return true;


      }


      void solve()


      {


           int* f=new int[number.length()+1];


           int* pre=new int[number.length()+1];


           int* use=new int[number.length()+1];


           memset(f,0x7f,sizeof(int)*(number.length()+1));


           f[0]=0;


           for (int k=1;k<=number.length();k++)


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


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


                       if (match(i,k,j))


                          if (f[k]>f[i]+1)


                          {


                             f[k]=f[i]+1;


                             pre[k]=i;


                             use[k]=j;


                          }


           if (f[number.length()]>number.length()) cout<<“No solution.”<<endl;


           else


           {


               stack<int> s;


              


               s.push(number.length());


               while (pre[s.top()])


                     s.push(pre[s.top()]);


              


               for (;!s.empty();)


               {


                   cout<<dictionary[use[s.top()]]<<char(s.size()>1?’ ‘:’\n’);


                   s.pop();


               }


           }


           delete[] f;


      }


};


class Application


{


      public:


      Application()


      {


      }


      int run()


      {


          Question q;


          while(q.read()) q.solve();


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


 

URAL1001[Reverse root]

这是一道很水的题,有人会看题解吗?


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-8


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <cstring>


using std::memset;


#include <stack>


using std::stack;


#include <cmath>


using std::sqrt;


#include <iomanip>


using std::setiosflags;


using std::setprecision;


 


class Application


{


      stack<long long int> A;


      public:


      Application()


      {


                    long long int input;


                    while (cin>>input)


                          A.push(input);


      }


      int run()


      {


          long long int pop;


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


          while (!A.empty())


          {


                pop=A.top();


                A.pop();


                cout<<sqrt(double(pop))<<endl;


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}


 


URAL1000[A+B Problem]

这是一道十分水的题,所以没人想写题解。


CODE:


 


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-8


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <cstring>


using std::memset;


 


class Application


{


      int a,b;


      public:


      Application()


      {


                    cin>>a>>b;


      }


      int run()


      {


          cout<<(a+b)<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}