給出一棵二分搜索樹，再給一個節點編號n，求以這個節點為根節點的子樹葉子節點的最大值與最小值。若n是奇數，那么他必然是個葉子節點，最大最小都是他自己。否則求n所在的層數，他的層數就是他的因子中2的個數（規律），轉化為求n的因子中2的個數。而2的個數取決于n的二進制表示中最后一個1所處的位置i，因為之前的某幾個1，假設處于j（j>i）,那么n可以表示為2^j+2^i+2^x(x>i且個數未定)=2^i*(1+2^(j-i)+2^(x-i)),看見米有，n必須有i個因子2.求出i的值后，即層數，可得n的左右各有num=2^i-1個兒孫（女），不信請看圖，概不解釋。那么最小值就是n-num,最大值就是n+num.那馬怎么求num呢，這時就可以請出神奇的位運算了（以速度"嗖嗖嗖"的快而揚名ACM界），首先是確定二進制n后綴連續0的個數，這樣想：怎么取出這i個0呢？其實不必考慮這個掣肘的問題，咱們直接跑到結果上考慮，就是求2^i-1,你花仙米有，這是個等差數列的前n項和：2^0+2^1+2^2+……+2^(i-1).那么這又是個什么形式呢，這就是二進制只有連續i個1的（其余都是前導0）數的十進制表示形式，OK，好辦了，利用系統自動轉換功能，咱們只需把這i個1羅列出來即可：把n的后i個0變成1，可采取如下形式n^(n|n-1),稍微解釋下，n|n-1是將后i個0變成1，把第i+1個1變成0，然后和n抑或一下，得到什么？哈，就是2^i-1,即i個1的十進制形式,代碼就不放了，上面明白了實現很簡單的！
那啥，轉載務必注明：Pzjay原創呃！

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/shifuwawa/archive/2010/01/07/5153446.aspx

以下是我根據上面的描述寫出來的代碼，一次AC，0MS
#include<iostream>
using namespace std;
int main()
{
 int n;
 cin>>n;
 while(n--)
 {
  int k;
  cin>>k;
  if(k%2!=0)
  {
   cout<<k<<" "<<k<<endl;
   continue;
  }
  int num=k^(k|k-1);
  cout<<k-num<<" "<<k+num<<endl;
 }
 return 0;
}

不得不說poj 2305是一道進制轉換的經典題目。一開始我沒有考慮到整除的情況。所以總是WA。后來加了一個判斷就AC了。
#include<iostream>
#include<cstring>
using namespace std;
char s1[1005],s2[15];
int main()
{
 int n;
 while(cin>>n&&n)
 {
  cin>>s1>>s2;
  __int64 a=0,b=0;int len1,len2;
  len1=strlen(s1);len2=strlen(s2);
  for(int i=0;i<len2;i++)
  {
   a*=n;
   a+=s2[i]-'0';
  }
  for(int j=0;j<len1;j++)
  {
   b*=n;
   b+=s1[j]-'0';
   if(b>=a)
    b%=a;
  }
  int k=0;
  if(b==0)
  {
   cout<<"0"<<endl;
   continue;
  }
  while(b!=0)
  {
   s2[k++]=b%n+'0';
   b/=n;
  }
  s2[k]='\0';
  int len=strlen(s2);
  for(k=len-1;k>=0;k--)
   cout<<s2[k];
  cout<<endl;
 }
 return 0;
} 這應該是一道DP題。下面的代碼是我見過的最短的代碼。拿出來跟大家分享。
#include<iostream>
#include<stdio.h>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
int arrival[1450];
int trip[1450];
int time[1450];
int n,t,m;
int main()
{
 int test;
 cin>>test;
 while(test--)
 {
  cin>>n>>t>>m;
  for(int i=1;i<=m;i++)
   scanf("%d",arrival+i);
  trip[0]=time[0]=0;
  for(int j=1;j<=m;j++)
  {
   time[j]=max(time[max(j-n,0)],arrival[j])+2*t;
   trip[j]=trip[max(j-n,0)]+1;
  }
  printf("%d %d\n",time[m]-t,trip[m]);
 }
 return 0;
}


然后是該作者的介紹

題目大意：有一些汽車在左岸，你要用一條小破船把它們拉到右岸去。每個測試點包含多個測試數據。第一行的整數C表示測試數據的數目。接下來每個測試數據的第一行為三個整數N, T, M表示一次可以運送N輛汽車，到達對岸的時間為T，汽車的總數是M。接下來的M行每行有一個整數，表示這輛汽車什么時候會來到左岸。對于每個測試數據，輸出兩個整數，分別是最少要耗用多少時間（包括你等車的時間，就是從0開始直到最后一輛車到達右岸），以及在這個前提下你最少要運送多少次。只要到右岸去就算作一次。

這個題出在DP專場不太合適……事實上本人用貪心的手段就解決了這個問題。

貪心策略：先運送M % N輛汽車到對岸（就是M除上N的余數），之后每次運N輛汽車，直到運完為止。這里的意思是，只有船上確實有了這么多車才出發，在此之前等著那些車來。對于這個策略的證明各位可以使用數學歸納法，比較簡單，這里就不耗費篇幅了。

DFS題目啊。看通過率就知道非常簡單的。一下付代碼，大家自己看下。
#include<iostream>
using namespace std;
char array[100][100];
int n,m;int count=0;
void dfs(int i,int j)
{
 if(i<0||i>n||j<0||j>m)
  return ;
 if(array[i][j]!='W')
  return ;
 array[i][j]='.';
 dfs(i-1,j);dfs(i+1,j);dfs(i,j-1);dfs(i,j+1);dfs(i-1,j-1);dfs(i-1,j+1);dfs(i+1,j-1);dfs(i+1,j+1);
}
void check()
{
 int i,j;
 for(i=0;i<n;i++)
 {
  for(j=0;j<m;j++)
  {
   if(array[i][j]=='W')
   {
    dfs(i,j);
    count++;
   }
  }
 }

}
int main()
{
 cin>>n>>m;
 for( int i=0;i<n;i++)
 {
  for(int j=0;j<m;j++)
  {
   cin>>array[i][j];
  }
 }
 check();
 cout<<count<<endl;
 return 0;
}

這道題目視枚舉題。直接枚舉各個長度，然后求最小面積即可。
#include<iostream>
using namespace std;
int main()
{
 int test;
 cin>>test;
 while(test--)
 {
  int n;
  cin>>n;
  int min=100000000;
  int area;
  int k;
  for(int i=1;i<=n;i++)
  {
   for(int j=1;i*j<=n;j++)
   {
    if(n%(i*j)==0)
    {
     k=n/(i*j);
     area=i*j+i*k+j*k;
     if(area<min)
      min=area;
    }
   }
  }
  cout<<min*2<<endl;
 }
 return 0;
}

這是一道模擬題。說白了就是石頭剪子布的問題。此題的關鍵點是要開兩個數組。一個是原來的。一個是改動后的，每次改動完之后都要用改動之后的初始化原來的一次。下面請看代碼。我把函數分的比較詳細。便于大家閱讀。
#include<iostream>
using namespace std;
char array[102][102];
char temp[102][102];
int r,c,n;
void init()
{
 int i,j;
 for( i=1;i<=r;i++)
  {
   for( j=1;j<=c;j++)
   {
    array[i][j]=temp[i][j];
   }
  }
}
void change(int i,int j)
{
 if(array[i][j]=='R')
 {
  if(i>1&&array[i-1][j]=='S')
   temp[i-1][j]='R';
  if(i+1<=r&&array[i+1][j]=='S')
   temp[i+1][j]='R';
  if(j>1&&array[i][j-1]=='S')
    temp[i][j-1]='R';
  if(j+1<=c&&array[i][j+1]=='S')
    temp[i][j+1]='R';
 }
 else
  if(array[i][j]=='P')
 {
  if(i>1&&array[i-1][j]=='R')
   temp[i-1][j]='P';
  if(i+1<=r&&array[i+1][j]=='R')
    temp[i+1][j]='P';
  if(j>1&&array[i][j-1]=='R')
    temp[i][j-1]='P';
  if(j+1<=c&&array[i][j+1]=='R')
    temp[i][j+1]='P';
 }
 else
  if(array[i][j]=='S')
 {
  if(i>1&&array[i-1][j]=='P')
   temp[i-1][j]='S';
  if(i+1<=r&&array[i+1][j]=='P')
    temp[i+1][j]='S';
  if(j>1&&array[i][j-1]=='P')
    temp[i][j-1]='S';
  if(j+1<=c&&array[i][j+1]=='P')
    temp[i][j+1]='S';
 }
}
void occupy()
{
 int i,j;
 while(n--)
 {
  for(i=1;i<=r;i++)
   {
    for(j=1;j<=c;j++)
    {
     change(i,j);     
    }
   }
  init();
 }

}
int main()
{
 int test;
 cin>>test;
 int i,j;
 while(test--)
 {
  cin>>r>>c>>n;
  for( i=1;i<=r;i++)
  {
   for( j=1;j<=c;j++)
   {
    cin>>array[i][j];
    temp[i][j]=array[i][j];
   }
  }
  /////////////OK 輸入字符完畢。
  occupy();
  for( i=1;i<=r;i++)
  {
   for( j=1;j<=c;j++)
   {
    cout<<array[i][j];
   }
   cout<<endl;
  }
  if(test!=0)
   cout<<endl;
 }
 return 0;
}

這個題首先要把輸入的坐標轉化成鄰接矩陣的形式。之后再利用鄰接矩陣使用普里姆算法計算最小生成樹。并對其中的邊進行排序。找出減去S個較大的后最大的那一個。因為較大的那幾個可以用衛星傳輸
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef struct
{
 double x;
 double y;
}point;
point array[505];
double len[505][505];
double kk[505],next[505];
double re[505];
int sa,num;
double dis(point first,point second)
{
 return sqrt((first.x-second.x)*(first.x-second.x)+(first.y-second.y)*(first.y-second.y));
}
void prim(int n)
{
 int i,j;
  //////////讀入數據完畢。開始構建鄰接矩陣
  for(i=0;i<num;i++)
  {
   for(j=0;j<num;j++)
   {
    len[i][j]=15000000;
   }
  }
  for(i=0;i<num;i++)
  {
   for(j=0;j<num;j++)
   {
    if(i!=j)
     len[i][j]=dis(array[i],array[j]);
   }
  }
  for(i=0;i<num;i++)
  {
   kk[i]=len[0][i];
   next[i]=0;
  }
  /////////鄰接矩陣構建完畢
  int count=0;i=0;
  while(count<num-1)
  {
   if(next[i]!=-1)
   {
    for(j=0;j<num;j++)
    {
     if(i!=j&&next[j]!=-1)
     {
      if(len[i][j]<kk[j])
      {
       kk[j]=len[i][j];
       next[j]=i;
      }
     }
    }
    next[i]=-1;
    double max=999999999;int k;
    for(j=0;j<num;j++)
    {
     if(kk[j]<max&&next[j]!=-1)
     {
      k=j;
      max=kk[j];
     }
    }
    re[count]=max;
    i=k;
    count++;
   }
  }
}
int main()
{
 int n;
 cin>>n;
 int i;
 while(n--)
 {
  cin>>sa>>num;
  for( i=0;i<num;i++)
  {
   scanf("%lf%lf",&array[i].x,&array[i].y);
  }
  prim(0);
  sort(re,re+num-1);
  printf("%.2f\n",re[num-1-sa]);
 }
 return 0;
}

pku2126 poj2126
題目大意：
給定多項式的系數，問這個多項式能不能分解!
如果能輸出NO 否則輸出YES
實系數多項式分解定理：
當n<2的時候不能分解輸出YES
當n==2的時候如果有實數根就能分解輸出NO   否則不能分解輸出YES
當n>2的時候一定能分解，那么輸出NO

#include<iostream>
using namespace std;
int array[25];
bool root(int a,int b,int c)
{
 if(b*b>=4*a*c)
  return true;
 else
  return false;
}
int main()
{
 int n;
 cin>>n;
 for(int i=0;i<=n;i++)
 {
  cin>>array[i];
 }
 if(n<=1)
  cout<<"YES"<<endl;
 else
  if(n==2)
  {
   if(root(array[0],array[1],array[2]))
    cout<<"NO"<<endl;
   else
    cout<<"YES"<<endl;
  }
  else
   cout<<"NO"<<endl;
  return 0;

}

3096暴力求解，0M通過
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
char str[85];
char first[3],second[3];
int main()
{
 first[2]='\0',second[2]='\0';
 while(gets(str))
 {
  bool flag=true;
  if(str[0]=='*')
   break;
  int len=strlen(str);
  for(int i=0;i<len;i++)
  {//從第幾個開始找起
   for(int j=1;j<(len-1)&&i+j<len;j++)
   {////////這個是間隔
    first[0]=str[i];first[1]=str[j+i];
    for(int k=i+1;k<len&&k+j<len;k++)
    {
     second[0]=str[k];second[1]=str[k+j];
     if(strcmp(first,second)==0)
      flag=false;
    }
    
   }
  }
  if(flag)
   cout<<str<<" is surprising."<<endl;
  else
   cout<<str<<" is NOT surprising."<<endl;
 }
 return 0;
} 這個題就是用一個遞歸轉化數字。10以下的不用轉換。
#include<iostream>
using namespace std;
int k;
int ff(int a)
{
 int sum=1;
 for(int i=0;i<a;i++)
  sum*=10;
 return sum;
}
void convert(int a)
{
 if(k/ff(a)==0)
  return ;
 else
 {
  if(k%ff(a)>=ff(a)/2)
   k=k/ff(a)+1;
  else
   k=k/ff(a);
  k*=ff(a);
  convert(a+1);  
 }
}
int main()
{
 int n;
 cin>>n;
 while(n--)
 {
  cin>>k;
  if(k<10)
  {
   cout<<k<<endl;
   continue;
  }
  convert(1);
  cout<<k<<endl;
 }
 return 0;
}