2020年3月24日 星期二

2020年1月12日 星期日

2020年1月4日 星期六

2020年1月1日 星期三

2019年12月26日 星期四

P2T補充

                No comments   

/*
P2T 12/13-2   陣列的練習
給一個正整數 n {1<n<10^6} ，接著給n-1個 1~n的編號，請問少了哪一個？
例如 5 4 1 2 3 ，後面4個編號中少了5
     6 5 6 1 3 2 ，後面5個編號中少了4
*/
#include <iostream>
using namespace std;
int a[1000001];  // 0~1000000
int main()
{
    int i,j,k,n;
    while( cin >> n )
    {
       for(i=1; i<=n; ++i)
          a[i]=0;       
       for(i=1; i<n; ++i)
       {
          cin >> k;
          a[k] = 1;         
       }
       for(i=1; i<=n; ++i)
       {
          if( !a[i])
          {
              cout << i << endl;
              break;    
          }
       }
    }
  return 0;
}

/*
P2T 12/27-1   陣列的練習
給一個正整數 n {1<n<10^4} ，接著給n個相異編號{ 1~10^9}，
再n-1個編號，請問少了哪一個？  6 1 12 23 34 56 67  56 67 1 34 23  少了12 
例如 5 66666666 123456 234567 33 777777 
            66666666 123456 234567 777777，後面4個編號中少了33
     6 543 612 93333333 93333336 2345 111 
        543 612 933336 2345 111  後面5個編號中少了93333333
*/
#include <iostream>
using namespace std;
int a[100000001]; //a[100000001];  // 0~1000000000 記憶體容量 不允許
int main()
{
    int i,k,n,m; 
    while( cin >> n )
    {
       for(i=1; i<=n; ++i)
          a[i]=0;       
       for(i=1; i<=n; ++i)
       {
          cin >> k;
          a[k] = 1;         
       }
       m=0;
       for(i=1; i<n; ++i)
       {
          cin >> k;
          if(k>m) m=k;  //最大的數 
          a[k] = 0;      
       }
       
       for(i=1; i<=m; ++i)
       {
          if( a[i])
          {
              cout << i << endl;
              break;    
          }
       }
    }
  return 0;
}


/*  P2T 12/27-2   陣列的應用 + map
C++ STL
vector 
set 
map
... 
P2T 12/27-2   陣列的練習
給一個正整數 n {1<n<10^4} ，接著給n個相異編號{ 1~10^9}，
再n-1個編號，請問少了哪一個？  6 1 12 23 34 56 67  56 67 1 34 23  少了12 
例如 5 666666666 123456789 234567891 33 7777777 
      a[0]        a[1]     a[2]      a[3]   a[4]  
       666666666 123456789 234567891 7777777，後面4個編號中少了33
     6 543 612 933333333 933333336 2345 111  
        933333336 2345 111  543 612  ， 
後面5個編號中少了933333333
*/
#include <iostream>
#include <map>  // 字典類
#include <cstring> // memset
using namespace std;
map<int,int> mp;  //某個名稱或數字(可能很大) 對應至序號 
int mpcnt;
int a[10000];
bool b[10000];
int main()
{
   int n,i,j;
   while( cin >> n )
   {
      mp.clear(); //mp清空
      memset(b,0,sizeof(b)); // b全清為 0 
      for(i=0; i<n; ++i)
      {
         cin >> a[i];         
         mp[ a[i] ] = i;
      }  
      // 只回來 n-1 個，少了哪一個 
      for(i=0; i<n-1; ++i)
      {
         cin >> k;
         j = mp[ k ]  //直接傳回原序號 
         b[j]=1;
      }  
      for(i=0; i<n; ++i)
      {
         if( b[i] == 0 ) //印出未回的
         {
           cout << a[i] << endl; 
           break;
         }
      }  
           
   }
  system("pause");
  return 0;
}


2019年12月20日 星期五

P2T a007判斷質數

                No comments   
方法一： 判斷是否被  2 ~ 根號n 整除 ， 但在 zerojudge的 a007仍會 TLE
    1 算出 q = int(sqrt(n))
    2 for i=2 ~ q ，若 n 被 i 整除則非質數
    3  i ~ q 皆不整除就是質數

方法二：先建一個質數表pr 再判斷是否被 2 ~ q 之內的質數整除 {大約會快10倍}
     (一)建 2~46340之間的質數表，共有4792個質數，最小是2、最大是 46337
           vector <int> pr;
     pr.push_back(2);           // 2 是質數，直接加入 pr
     for( i=3; i<=46340; i+=2 )  // 只判斷奇數是否為質數
     {
        q = int( sqrt(i) );
        bool y = 1;   //以下 判斷 i 是否被質數表中的質數整除
        for(j=0; y && j<pr.size() && pr[j]<=q ; ++j)
              if( i % pr[j] == 0 ) y=0;
        if( y ) pr.push_back(i);   // i 也是質數
     }
    註：vector<資料型別 > 可說是記憶空間動態調整的陣列
            不需 int pr[ 須先宣告大小 ]; 當有新資料時 pr.push_back( 新資料 );
            總共有幾個元素可由 pr.size() 的值查詢

     (二) 每輸入的 n 只檢查 2~q 中的質數是否可整除 n 可加快速度
           while( cin >> n ) //有  20 萬筆 n
     {
        q = int( sqrt(n) );
        bool y = 1;   //以下 判斷 n 是否被質數表中的質數整除
        for(j=0; y && j<pr.size() && pr[j]<=q ; ++j)
              if( n % pr[j] == 0 ) y=0;
        if( y ) cout << "質數\n";  // 印出質數
        else  cout << "非質數\n";  // 印出非質數
     }

 I/O 加速： cin,cout 會比 scanf,printf慢，可改為如下
        while( scanf("%d", &n)==1 ) //有  20 萬筆 n
    {
       …
       if( y ) printf("質數\n");  
       else  printf("非質數\n");    
    }