F:星星点点

题意：

根据生成法则（如果该行的第i和第i+1个位置上的符号不同，则下一行的第i个位置上为“*”，否则为“.”，其最后一个位置的字符由上一行的第一个和最后一个字符决定。）不断向下生成，直至生成的字符串与前面的字符串有重复为止，并找出第一次重复的距离。

思路：

先处理字符串：

把“.”看成0，“*”看成1，这样就可以把字符串转换成<32位的二进制数，用一个int x表示。

next(x) = x ^ (x循环左移1位);

然后是查找：

tle的想法是：如果next(x)出现过，则输出它们的距离，否则，把next(x)插入一个双向链表（你可以用stl的list）。

贴个代码

#include<iostream>
#include<string>
#include<list>
using namespace std;
int main()
{
 string str;
 while(cin>>str)
 {
  list<int> l;
  list<int>::iterator it;
  int n=str.size();
  int cur=0, cnt;
  int i;
  for(i=0;i<n;i++)
  {
   cur<<=1;
   if(str[i]=='*')
    cur|=1;
  }
  while(1)
  {
   l.insert(l.begin(),cur);
   cur ^= (((cur<<1)&(1<<n))!=0)|(cur<<1) & ((1<<n)-1);
   for(cnt=0,it=l.begin();it!=l.end();it++,cnt++)
    if(*it==cur)
     goto end;
  }
end:
  cout<<cnt+1<<endl;
 }
 return 0;
}

ac的想法（非原创）：

令原始整数为x = y，在一个迭代中， x = next(x) ; y = next(next(y));

则以1：2的步长比搜索，直到两个值相同为止，记为t，

然后停止y的搜索，x继续向前搜索，并记录步数，直到x再次搜索到t为止。所用的步数即为答案！

代码自己敲敲！