题目大意：求给出串的每个前缀串的重复次数。

例如aabaabaabaab;
1.aa中前缀a出现2次。
2.aabaab中前缀aab出现2次
3.aabaabaab中前缀aab出现3次
4.aabaabaabaab中前缀aab出现4次.
大概就是这么个意思。

这里利用了kmp中的next标记的性质。

看看这个字符串
下标：1  2  3  4  5 6  7   8 9  10 11 12
原串：a  a  b  a  a  b  a  a  b   a   a   b
next:  0  1  2  1  2  3  4  5  6  7    8  9
用下标i减去next[i]即为(i-next)匹配的前缀的长度.

若这个数能被整除，整除的个数即为使用该前缀的个数。

so就是这样.....
#include<iostream>
using namespace std;

char t[1111111];
int len,next[1111111];
int ri[1111111],rl[1111111];

void setNext()
{
     int j=0,k=-1;
     next[0]=-1;
     while( j<len )
     {
            if( k==-1|| t[j]==t[k] )
                next[++j]=++k;
            else
                k=next[k];
     }
}

int main()
{
    int Ncase=0;
    while( scanf("%d",&len)!=EOF&&len!=0 )
    {
           scanf( "%s",&t );
           setNext();
           printf( "Test case #%d\n",++Ncase );
           for( int i=2;i<=len;i++ )
                if(  i%(i-next[i])==0&&i/(i-next[i])>1 )
                     printf( "%d %d\n",i,i/(i-next[i]) );
           printf( "\n" );
    }
    return 0;
}

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

题目解析
刚开始看这道题目的时候，比较蒙，大概是因为我一开始就直接看代码，没看到什么细节性质的提示。再读了下题目，基本明白了他的意思，主要意思就是说给你一个序列，你确认下这个序列到底是不是一个二叉搜索树的后序遍历结果。这里稍微讲下，二叉搜索树的概念：根节点为参考，比根节点大的数据在右侧，比根节点小的数据在左侧，叶子节点左子节点比父节点小，右子节点比父节点要大。
解题思路
这个题目属于二叉搜索树的一个性质的考察，懂得什么是二叉搜索树的话才可以顺利进行，否则，概念都不懂根本搞不清楚哪里作为判断的标准。我觉得这个题目而言，找到判定标准很重要的，这应该说是一个决定本题能不能真正求出的关键，那么，我给出的建议是读者在自己思考时辅助举例子的方式进行，自己测试下，根据自己定义的一个二叉搜索树得到他的后续遍历序列，然后逆向推他到底是不是一个二叉搜索树的后续遍历的结果串。
这里以4，8，6，12，16，14，10为例子，首先，根节点10，这是可以直接得到的，那么根据其性质，根节点左侧的小于10，根节点右侧的大于10，那么可以将本题中的序列，切分为两个子集，切分为子集，一般的方式可以采用递归了，因为子集和其本身都是一个集合的抽象，将子集和全集视为一个类型的对象就可以了。注意这里当切分完成后需要进行一个检查，这个检查就是：第一个大于10的后面的这些序列中必须全部大于10，否则直接返回false。再看看左侧子集，左侧子集的话主要是4，8，6这个三个，然后将其视为新的全集进行上述操作，那么将6作为新的根节点，那么6而言，将4，8切分为两个子集，然后子集内进行上面的操作。

代码实现
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        
        if(sequence == null || sequence.length == 0) {
			return false;
		}
        
        if(sequence.length == 1) 
        	return true;
        
        int endNum = sequence[sequence.length - 1];
        
        int i = 0;
       	
        for(; i < sequence.length - 1; i ++) {
            
            if(sequence[i] > endNum) {
                break;
            }
        }
        int index = i;
        for(; index < sequence.length - 1; index++) {
        	
        	if(sequence[index] < endNum) {
        		return false;
        	}
        }
        
        int[] smaller = null;
        int[] bigger = null;
        
        smaller = new int[i];
        bigger = new int[sequence.length- i - 1];
        
        int in = 0;
        for(int j = 0; j < sequence.length - 1; j ++) {
        
        	if(j < i) {
            	smaller[j] = sequence[j];
        	} else {
            	bigger[in ++] = sequence[j];
        	}
    	}
        
        if(i == 0) {
        	
            return VerifySquenceOfBST(bigger);
            
        } else if(i == sequence.length - 1) {
            
            return VerifySquenceOfBST(smaller);
        } else {
        	
            return VerifySquenceOfBST(bigger) && VerifySquenceOfBST(smaller);
        }
        
    }
}
这个题还有优化的可能，比如上面的检查可以和查找比他大的数的index同时来进行，但是时间上并不会得到客观的提升，都是O(n),无非是代码减少了，下面是按照几个特例划分了左侧递归，右侧子集的递归，左侧和右侧都进行递归。
需要注意为空的情况，这是一个特例。其实我感觉这个特例不需要设计的，要么就在题目中说明。不过真正的项目中这个确实是要你自己去考虑到的。

题的大概意思是：

输入一个字符串的长度大小，然后输入字符串，首先分别选取字符串的首尾两个字符，进行字典序比较，将较小的放到新创建的字符串的后面，直到原本的字符串长度为0。这种思想适合贪心算法，每选一步就选最值，所以理解了题意应该很简单。只需要做一些简单的处理还有题目要求的处理数据




*
*这题主要是用贪心，目标主要是从已知的字符串构造出字典序尽可能小的字符串
*从字典序性质来看，无论字符串末尾有多大，只要保证前面部分较小就可以咯！
*假设原来字符串为S，目标字符串为T，那么，不断取出S的开头和末尾较小的一个
*字符放到T的末尾。上面的没有针对开头与结尾相同，如果，遇到这样动情况，应
*该比较下一个字符的大小。如果，下一个字符也相同，那么可以得到下面的算法：
*按照字典序比较S和将S反转后的字符串S’
*如果，S较小，那么取出S开头字符，追加到T的末尾
*如果，S'较小，那么取出S结尾字符，追加到T的末尾
*如果，相同则取出那一个都可以。
*
*
*/
#include <iostream>
#include <string>

using namespace std;

int n;
char s[2010];

void solve()
{
    int start = 0, end = n - 1,count = 0;
    while(start <= end)   // 将从左起和从右起的字符串比较
    {
        bool flag = false;
        for(int i = 0; i <= end - start; i++)  // 字符串的开头与结尾相同，则继续比较下一个
        {
            if(s[start+i] < s[end-i])  
            {
                flag = true;
                count++;
                break;
            }
            else if(s[start+i] > s[end-i])
            {
                flag = false;
                count++;
                break;
            }
        }
        if(flag) cout<<s[start++];
        else cout<<s[end--];
        if(count % 80 == 0)
        cout<<endl;
    }
    cout<<endl;
}
int main(void)
{
    cin>>n;
    for(int i = 0; i < n; i++)
    cin>>s[i];
    solve();
    return 0;
}

基础递归题目。



题目：

我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:

1.不作任何处理;

2.在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3.加上数后,继续按此规则进行处理,直到不能再加自然数为止.



理解：

题目不太好理解 
大概意思是说一个 小于输入的数一半的数可以计入总数。
可以一直加到这个数字的一半为0
把每次除以二的过程理解为一层，用递归来做
多层递归， 时间复杂度大概爆炸了。。
代码：




#include<iostream>
#include<string>

using namespace std;
int sum=1,i=0;  //包括这个数字本身，所以sum初始化为1 

int fun(int i);

int main()
{
    cin>>i;
    i=i/2;   //第一层 
    sum +=i; 
    fun(i); //开始递归 
    cout<<sum<<endl;

}

int fun(int i)
{
    for(int j=1;j<=i;j++) //遍历该层所有的数 
    {
        if(j/2 != 0)    {   //判断下一层是否存在 
            sum+=j/2;
            fun (j/2);  
        }
    }


}