zj:94-北縣賽-D249~D252

第1題d249: 94北縣賽-1-心意相通的指數(Match)

以下程式碼在 ZJ 沒有 AC ，只有60分

討論區有人說測資與題意不符

http://zerojudge.tw/ShowThread?postid=2568&reply=2567#2568

測資解的順序不是像題目所說的任意解皆可。

當LCS的dp[a-1][b] == dp[a][b-1]時要取dp[a][b-1]，

這樣解的順序才會跟測資一樣，

另有morris的 AC 請查 下列網址

http://mypaper.pchome.com.tw/zerojudge/post/1322395974

我覺得我以下的小珠部份旋轉方向改一下、取dp[a][b-1]部份改一下應可以過，但還沒仔細試

下週再補

#include <iostream>

#include <sstream>

#include <iomanip>

#include<cstring>

using namespace std;

string LCS( string x , string y )

{

   string z;

    int i,j, m,n,t;  

      m = x.size();  

      n = y.size();  

      int b[m+1][n+1] , c[m+1][n+1];  

      for(i=0; i<=m; ++i ) c[i][0]=0;  

      for(j=0; j<=n; ++j ) c[0][j]=0;  

   // 開始由 c[1][1]開始設定，至c[m][n]即為 LCS 長度  

   // 由b[m][n]往回找若 b[i][j]==0 印出 { 0左上、1上、2左 }   

      for(i=1; i<=m; ++i )  

      {   

         for(j=1; j<=n; ++j )  

         {  

            if(x[i-1]==y[j-1])   // 字串從 0 開始   

              { c[i][j]=c[i-1][j-1]+1 ;  b[i][j]=0; }   // 左上   

            else if(c[i-1][j]<c[i][j-1]) 

              { c[i][j]=c[i][j-1] ;  b[i][j]=2; }       // 左  

            else   { c[i][j]=c[i-1][j] ;  b[i][j]=1; }  // 上  

         }              

      }  

   // 產生 LCS 字串 z  

 //     cout << x << " " << y << " = ";

      i=m; j=n;  z="";  

      if( c[m][n]==0 )  return z; //{ cout << 0 << endl; continue; }  

      while ( i && j )  

      {  

         if( b[i][j]==1) --i;  

         else if( b[i][j]==2) --j;  

         else if( b[i][j]==0 )  

         {  

            --i; --j;  

            z = x[i] + z;  

         }  

      }  

      return z;

}

int main( )

{

   string a , a2 , b , c , d , e;

   int an ,  abn , m , i;

   cin >> a >> b;   // 讀兩字串 ，求 LCS

   an = a.size();   // 串成環的長度 

   a2 = a + a.substr(0,an-1); 

   abn = an + b.size();

   for ( m=0 , i=0; i<an; ++i)

   {

      c = a2.substr( i , an ); // a2 循環 取 a 長度  

      d = LCS( c , b );   // 找出 c , b 的 lcs 字串傳回 d;

      if( d.size() > m )  

      {

         m = d.size();

         e = d;

      }

   }

   if ( m==0 ) cout << "no" << endl;

   else

   {   cout << e << endl;

       cout << fixed << setprecision(2) <<  2.0*m / abn << endl;

   }

   return 0 ; 

}

第2題d250: 94北縣賽-2-數獨問題 (Sudoku)

#include <iostream>

using namespace std;

int main( )

{

    string s;

    bool m[10];

    int i;    

   while(cin>>s) {

      bool m[10]={false};

      for(i=0;i<9;i++)  if(s[i]) m[s[i]-'0']=true; 

      for(i=1;i<=9;i++)  if( !m[i] ) cout<<i<<endl; 

   }

    return 0 ; 

}

第3題d251: 94北縣賽-3-羅馬數字 (Roman)

#include <iostream>

using namespace std;

// ----------------------------------------

string rtb="IVXLCDM";

int  ntb[]={1,5,10,50,100,500,1000};

int rton(string s)  // 羅馬字串轉數字 

{

 int i,j,n=s.size();

  int v1,v2,sum=0;

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

     j=i+1;

     v1= ntb[rtb.find(s[i])];

     sum+=v1;

     if(j>=n) return sum;

     else {

        v2= ntb[rtb.find(s[j])];

        if(v1<v2) { sum+=(v2-v1-v1); i++; }

     }

   }

   return sum;

}

// -------------------------------------------

string r,ms[]={"IV","IX","XL","XC","CD","CM"};

int    m[]={4,9,40,90,400,900};

string ntor(int n)  // 數字轉羅馬字串 

{

int ti;

  //千

  r="";

  while(n>=1000) {r+='M'; n-=1000; }

  for(ti=5;ti>=0;ti--) {

     if(n>=m[ti]) { r+=ms[ti]; n-=m[ti]; }

     while(n>=ntb[ti]) { r+=rtb[ti]; n-=ntb[ti]; }

  }

  return r;

}

// -------------------------------------------

int b2t(int m)

{

   return (m+450)%1440;  //部落總分鐘數+7小時30分的總分鐘數 

}

// ----------------------------------------------------

int main( )

{

   

   string rh , rm ;  //羅馬數字 時rh 、 分rm

   int bhm , thm ;  // 轉成數字的部落總分鐘bhm , 台灣的總分鐘 thm

   cin >> rh >> rm ;

   thm = b2t( rton( rh ) * 60 + rton( rm ) );

   cout << ntor( thm/60 ) << endl;

   cout << ntor( thm%60 ) << endl;

   return 0 ;

}

第4題d252: 94北縣賽-4-字串處理問題 (String)

/*

輸入： 

hellol, I am a frog.

$-----xxxxipieirisioin0u++xs

hellol, I am a frog.

0uuuxxxxssss----++++uuuussssxxxxuuuuipipipipipipip

範例輸出 ：

Hello, I am a person.

HEL I AFROGppppppp.

*/

#include <iostream>

#include <cctype>

using namespace std;

int main( )

{

   string data , cmd ; //資料、指令

   getline( cin , data );

   getline( cin ,cmd );

   int dn = data.size();

   int cn = cmd.size();

   if( data[dn-1] == 13 ) { --dn; data.erase(dn); }  //若最後1字為換行，刪

   string dd=data;

   if( cmd[cn-1] == 13 ) { --cn; cmd.erase(cn); }  //若最後1字為換行，刪

   int p=0;  // 游標在第1個字{索引值0}

   char c , t;

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

   {

      c=cmd[i];

      switch( c )

      {

         case '0' : p=0; break;  // 行首 

         case '$' : p=data.size(); break;  // 行尾 

         case 'x' : if( (p < data.size()) && (data.size()>0) ) data.erase(p,1) ; break;  // 刪1字元 

         case 's' : if( p < data.size()-1 )          // p , p+1 兩字元交換

                  { t=data[p];  data[p]=data[p+1] ; data[p+1]=t; }  break; 

         case 'i' : if(i+1<cn)                  // 游標前插入1字元 

                  { ++i ; data.insert(p,1,cmd[i]); ++p; }  break; 

         case 'u' : if( (p < data.size()) ){ data[p]=toupper(data[p]); ++p; } break; // 轉大寫

         case '+' :  ++p; break; // 右移if( p < data.size() )

         case '-' :  --p; break; // 左移if( p > 0 )

       }

   }

   cout << data << endl;

   return 0 ;

}