2.刷题偶遇小技巧<2>

[cccreator]

c++中substr()的用法

str.substr(int a , int b);//a，b两个参数：第一个参数是要截取的字符串的起始位置，后一个参数是要截取字符串的长度。 Example: string str ("adfas afdsafa gagfg"); cout<<str.substr(3,4)<<endl; cout<<str.substr()<<endl; 输出结果为:as a adfas afdsafa

[cccreator]

移位运算

移位运算用来将整型或字符型数据作为二进位信息串作整体移动。有两个运算符：

<< (左移) 和 >> (右移)

移位运算是双目运算，有两个运算分量,左分量为移位数据对象，右分量的值为移位位数。移位运算将左运算分量视作由二进位组成的位串信息,对其作向左或向右移位，得到新的位串信息。 移位运算符的优先级低于算术运算符，高于关系运算符，它们的结合方向是自左至右。

左移运算符(<<)

左移运算将一个位串信息向左移指定的位，右端空出的位用0补充。例如014<<2,结果为060,即48。
左移时，空出的右端用0补充，左端移出的位的信息就被丢弃。在二进制数运算中，在信息没有因移动而丢失的情况下，每左移1位相当于乘2。如4 << 2，结果为16。

右移运算符(>>)

右移运算将一个位串信息向右移指定的位，右端移出的位的信息被丢弃。例如12>>2,结果为3。与左移相反，对于小整数，每右移1位，相当于除以2。在右移时，需要注意符号位问题。对无符号数据，右移时，左端空出的位用0补充。对于带符号的数据，如果移位前符号位为0(正数)，则左端也是用0补充；如果移位前符号位为1(负数)，则左端用0或用1补充，取决于计算机系统。对于负数右移，称用0 补充的系统为“逻辑右移”，用1补充的系统为“算术右移”。以下代码能说明读者上机的系统所采用的右移方法：
 printf("%d/n/n/n", -2>>4);

若输出结果为-1，是采用算术右移；输出结果为一个大整数，则为逻辑右移。 移位运算与位运算结合能实现许多与位串运算有关的复杂计算。设变量的位自右至左顺序编号，自0位至15位，有关指定位的表达式是不超过15的正整数。

一个小栗子：整数与IP地址间转换

[cccreator]

全排列

• 递归全排列算法

  #include<iostream>
  #include<algorithm>
  using namespace std;
  void swap(int* a, int* b)
  {
  int m;
  m=*a;
  *a=*b;
  *b=m;
  }
  void permutation(int* a,int k,int m)
  {
  if(k==m)
      {
      for(int i=0;i<m;i++)
          cout<<a[i]<<" ";
      cout<<a[m]<<endl;
  }
  else
      {
      for(int j=k;j<=m;j++)
          {
          swap(a[j],a[k]);
          permutation(a,k+1,m);
          swap(a[j],a[k]);
      }
  }
  }
  int main()
  {
  int n;
  while(cin>>n)
      {
      int a[9];
      for(int i=0;i<n;i++)
          {
          cin>>a[i];
      }
      sort(a,a+n);
      permutation(a,0,n-1);
  }
  //system("pause");
  return 0;
  }

• 非递归全排列算法，即字典序排列算法

  #include<iostream>
  #include<algorithm>
  using namespace std;
  void swap(int* a,int i,int j)
  {
  a[i]^=a[j];
  a[j]^=a[i]; //利用异或运算，实现两个元素的交换
  a[i]^=a[j];
  }
  void reverse(int* a,int i,int j)
  {
  for(;i<j;++i,--j)
  {
      swap(a,i,j);
  }
  }
  void print(int* a,int length)
  {
  for(int i=0;i<length;i++)
      cout<<a[i]<<" ";
  cout<<endl;
  }
  void permutation(int* a,int length)
  {
  if(length<2)
      return;
  bool end=false;
  while(true)
  {
      print(a,length);
      int i,j;
      for(i=length-2;i>=0;--i)
      {
          if(a[i]<a[i+1])
              break;
          else if(i==0)
              return;
      }
      for(j=length-1;j>i;--j)
      {
          if(a[j]>a[i])
              break;
      }
      swap(a,i,j);
      reverse(a,i+1,length-1);
  }
  }
  int main()
  {
  int n;
  while(cin>>n)
  {
      int a[9];
      for(int i=0;i<n;i++)
      {
          cin>>a[i];
      }
      sort(a,a+n);
      permutation(a,n);
  }
  system("pause");
  return 0;
  }

• 用STL实现字典序排序

  
  #include <iostream>  
  #include <algorithm>  
  using namespace std;  

void permutation(int* a, int len)
{
do{
for(int i = 0; i < len-1; ++i){
cout<<a[i]<<" ";
}
cout<<a[len-1]<<endl;
}while(next_permutation(a, a + len));
}

int main()
{
int n; while(cin>>n) { int a[9]; for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n); permutation(a,n); } system("pause"); return 0;
}