给出一棵二分搜索树，再给一个节点编号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;
}