/**//*Problem: 1509  User: Uriel 
   Memory: 144K  Time: 16MS 
   Language: C  Result: Accepted*/ 

#include<stdio.h>
#include<string.h>

int min(int a, int b)
{
    return a <= b ? a : b;
}

int MinimumRepresentation(char *s, int l)
{
    int i = 0, j = 1, k = 0, t;
    while (i < l && j < l && k < l)
    {
        t = s[(i + k)%l] - s[(j + k)%l];
        if (!t) ++ k;
        else
        {
            if (t > 0) i = i + k + 1;
            else j = j + k + 1;
            if (i == j) ++j;
            k = 0;
        }
    }
    return min(i,j);
}

int x,len,i,t;
char str[10010];
int main()
{
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        memset(str,0x00,sizeof(str));
        scanf("%s",str);
        len=strlen(str);
        x=MinimumRepresentation(str,len);
        printf("%d\n",x+1);
    }
    return 0;
}

//串的同构是，在若干次循环位移后可以变成相同
    static boolean isIsomorphism(String s1, String s2)
    {
        char[] u = (s1+s1).toCharArray();
        char[] w = (s2+s2).toCharArray();
        
        int i = 0;
        int j = 0;
        int len = s1.length();
        while(i < u.length && j < w.length)
        {
            int k = 0;
            while((i+k) < u.length && (j+k)<u.length  && u[i+k] == w[j+k])k++;//&& k < len
            System.out.println(k);
            if(k >= len) return true;
            
            if(u[i+k] > w[j+k])i = i+k+1;
            else j = j+k+1;
        }
        return false;
    }

     摘要: 最短路径 之 SPFA算法 (转载）(2009-05-06 20:41:51) var $tag='spfa,杂谈'; var $tag_code='0c0816ca8a11d99e776ffbef47dd2fd0'; 标签：spfa 杂谈  ...  阅读全文

#include  <stdio.h>
int add(int x,int y)  {return x+y;}
int sub(int x,int y)  {return x-y;}
int mul(int x,int y)  {return x*y;}
int div(int x,int y)  {return x/y;}
int (*func[])()={add,sub,mul,div};
int num,curch;
char chtbl[]="+-*/()=";
char corch[]="+-*/()=0123456789";
int getach()  {
    int i;
    while(1)  {
        curch=getchar();
        if(curch==EOF)  return -1;
        for(i=0;corch[i]&&curch!=corch[i];i++);
        if(i<strlen(corch))  break;
    }
    return curch;
}

int getid()  {
    int i;
    if(curch>='0'&&curch<='9')  {
        for(num=0;curch>='0'&&curch<='9';getach())    num=10*num+curch-'0';
        return -1;
    }
    else  {
        for(i=0;chtbl[i];i++) if(chtbl[i]==curch)  break;
            if(i<=5)  getach();
            return i;
    }
}

int cal()  {
    int x1,x2,x3,op1,op2,i;
    i=getid();
    if(i==4)    x1=cal();    else  x1=num;
    op1=getid();
    if(op1>=5)  return x1;
    i=getid();
    if(i==4)  x2=cal();    else  x2=num;
    op2=getid();
    while(op2<=4)  {
        i=getid();
        if(i==4)  x3=cal();  else  x3=num;
        if((op1/2==0)&&(op2/2==1))    x2=(*func[op2])(x2,x3);
        else  {
            x1=(*func[op1])(x1,x2);
            x2=x3;
            op1=op2;
        }
        op2=getid();
    }
    return (*func[op1])(x1,x2);
}

void main(void)  {
    int value;
    printf("Please input an expression:\n");
    getach();
    while(curch!='=')  {
        value=cal();
        printf("The result is:%d\n",value);
        printf("Please input an expression:\n");
        getach();
    }
}

（一）简单的函数指针的应用。
//形式1：返回类型(*函数名)(参数表)
char (*pFun)(int);
char glFun(int a){ return;}
void main()
{
    pFun = glFun;
    (*pFun)(2);
}
        第一行定义了一个指针变量pFun。首先我们根据前面提到的“形式1”认识到它是一个指向某种函数的指针，这种函数参数是一个int型，返回值是char类型。只有第一句我们还无法使用这个指针，因为我们还未对它进行赋值。
        第二行定义了一个函数glFun()。该函数正好是一个以int为参数返回char的函数。我们要从指针的层次上理解函数——函数的函数名实际上就是一个指针，函数名指向该函数的代码在内存中的首地址。
        然后就是可爱的main()函数了，它的第一句您应该看得懂了——它将函数glFun的地址赋值给变量pFun。main()函数的第二句中“*pFun”显然是取pFun所指向地址的内容，当然也就是取出了函数glFun()的内容，然后给定参数为2。
（二）使用typedef更直观更方便。
//形式2：typedef 返回类型(*新类型)(参数表)
typedef char (*PTRFUN)(int);
PTRFUN pFun;
char glFun(int a){ return;}
void main()
{
    pFun = glFun;
    (*pFun)(2);
}
        typedef的功能是定义新的类型。第一句就是定义了一种PTRFUN的类型，并定义这种类型为指向某种函数的指针，这种函数以一个int为参数并返回char类型。后面就可以像使用int,char一样使用PTRFUN了。
        第二行的代码便使用这个新类型定义了变量pFun，此时就可以像使用形式1一样使用这个变量了。
（三）在C++类中使用函数指针。
//形式3：typedef 返回类型(类名::*新类型)(参数表)
class CA
{
 public:
    char lcFun(int a){ return; }
};
CA ca;
typedef char (CA::*PTRFUN)(int);
PTRFUN pFun;
void main()
{
    pFun = CA::lcFun;
    ca.(*pFun)(2);
}
        在这里，指针的定义与使用都加上了“类限制”或“对象”，用来指明指针指向的函数是那个类的这里的类对象也可以是使用new得到的。比如：
CA *pca = new CA;
pca->(*pFun)(2);
delete pca;
        而且这个类对象指针可以是类内部成员变量，你甚至可以使用this指针。比如：
        类CA有成员变量PTRFUN m_pfun;
void CA::lcFun2()
{ 
   (this->*m_pFun)(2);
}
        一句话，使用类成员函数指针必须有“->*”或“.*”的调用。

 

 

作者:csumck   更新日期:2004-11-07
来源:CSDN   浏览次数:

系统的可靠度计算公式 收藏
并联:1-(1-p1)(1-p2)

串联:p1p2

p1,p2分别为部件1和部件2的可靠度.
---------------------------------------------------------------------------
eg:
某计算机系统的可靠性结构是如下图所示的双重串并联结构，若所构成系统的每个部件的可靠度为0.9 ，即R=0.9 ，则系统的可靠度为（）？

|－－－（R）————（R）－－－|
———| |－－
|－－－（R）－－－－（R）－－－|

类似于串两个电阻，在并两个电阻的图。问怎样计算？
 
最佳答案
串联的可靠度P1=R1×R1 =0.81
并联起来时可靠度P2=1-（1-P1）×（1-P1）=0.9639

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/zwhfyy/archive/2009/04/02/4042513.aspx

     摘要: 背包问题 1.引子   我们人类是一种贪婪的动物，如果给您一个容量一定的背包和一些大小不一的物品，裝到背包里面的物品就归您，遇到这种好事大家一定不会错过，用力塞不一定是最好的办法，用脑子才行，下面就教您如何解决这样的问题，以获得更多的奖品。 2.应用场景   在一个物品向量中找到一个子集满足条件如下 ：    1）这个子集加起来的体积大小不能...  阅读全文

在今年的信息学冬令营上，陈启峰提出了一个自己创造的BST数据结构—Size Balanced Tree。这个平衡二叉树被全世界内的许多网站所讨论，大家讨论的主题也只有一个—SBT能够取代Treap吗？本文详细介绍SBT树的性质，以及一些常用的操作，最后证明SBT是一颗高度平衡的二分查找树。

一．        介绍

众所周知，BST能够快速的实现查找等动态操作。但是在某些情况下，比如将一个有序的序列依次插入到BST中，则BST会退化成为一条链，效率非常之低。由此引申出来很多平衡BST，比如AVL树，红黑树，treap树等。这些数据结构都是通过引入其他一些性质来保证BST的高度在最坏的情况下都保持在O(log n)。其中,AVL树和红黑树的很多操作都非常麻烦，因此实际应用不是很多。而treap树加入了一些随机化堆的性质，实际应用效果非常好，实现起来很简单，一直以来受到很多人的青睐。本文介绍一种新的平衡BST树，实现起来也是非常之简单，并且能够支持更多的操作，实际评测效率跟treap也不差上下。

在介绍SBT之前，先介绍一下BST以及在BST上的旋转操作。

1.      Binary Search Tree

BST是一种高级的数据结构，它支持很多动态操作，包括查找，求最小值，最大值，前驱，后继，插入和删除，能够用于字典以及优先队列。

       BST是一棵二叉树，每个结点最多有2个儿子。每个结点都有个键值，并且键值必须满足下面的条件：

       如果x是BST中的一个结点。那么x的键值不小于其左儿子的键值，并且不大于其右儿子的键值。

       对于每个结点t，用left[t]和right[t]分别来存放它的两个儿子，ket[t]存放该结点的键值。另外，在SBT中，要增加s[t],用来保存以t为根的子树中结点的个数。

2.      旋转

为了保证BST的平衡(不会退化成为一条链)，通常通过旋转操作来改变BST的结构。旋转操作不会影响binary-search-tree的性质！

 

       2.1右旋操作的伪代码

       右旋操作必须保证左儿子存在

       Right-Rotate(t)

              k←left[t]

              left[t]←right[k]

              right[k]←t

              s[k]←s[t]

              s[t]←s[left[t]]+s[right[t]]+1

              t←k

       2.2 左旋操作的伪代码

       左旋操作必须保证右儿子存在

       Left-Rotate(t)

              k←right[t]

              right[t]←left[k]

              left[k]←t

              s[k]←s[t]

              s[t]←s[left[t]]+s[right[t]]+1

              t←k

四．常用操作

插入操作

SBT和插入操作和BST的基本相同，只是在插入之后需要执行下Maintain操作。

Insert (t,v)

If t=0 then

t←NEW-NODE(v)

Else

s[t] ←s[t]+1

If v<key[t] then

Simple-Insert(left[t],v)

Else

Simple-Insert(right[t],v)

Maintain(t,v≥key[t])

删除操作

如果没有找到要删除的结点，那么就删除最后一个访问的结点并记录。

Delete (t,v)

If s[t]≤2 then

record←key[t]

t←left[t]+right[t]

Exit

s[t] ←s[t]－1

If v=key[t] then

Delete(left[t],v[t]+1)

Key[t] ←record

Maintain(t,true)

Else

If v<key[t] then

Delete(left[t],v)

Else

Delete(right[t],v)

Maintain(t,v<key[t])

另外，由于SBT的平衡性质是靠size域来维护的，而size域本身(子树所含节点个数)对于很多查询算法都特别有用，这样使得查询集合里面的譬如第n小的元素，以及一个元素在集合中的排名等操作都异常简单，并且时间复杂度都稳定在O(log n)。下面仅介绍下上表提到的select(t,k)操作和rank(t,v)操作。

       由于SBT的性质（结点t的关键字比其左子树中所有结点的关键字都大，比其左子树中所有的关键字都小），理解下面的算法非常容易。

3．Select操作

Select(t,k)

       If k=s[left[t]]+1 then

              return key[t]

       If k<=s[left[t]] then

              return Select(left[t],k)

       Else

              return Select(right[t],k-1-s[left[t]])

4．Rank操作

Rank(t,v)

       If t=0 then

              return 1

       If v<=key[t] then

              return rank(left[t],v)

       Else

              return s[left[t]]+1+rank(right[t],v)

同样,求前驱结点的操作Pred和后继结点的操作都很容易通过size域来实现。

 

五．相关证明分析

显然Maintain操作是一个递归过程，可能你会怀疑它是否会结束。下面我们可以证明Maintain操作的平摊时间复杂度为O(1)。

1．关于树的高度的分析

设f[h]表示高度为h的SBT中结点数目的最小值，则有

                             1                                    (h=0)

f[h]=       2                                    (h=1)

           f[h-1]+f[h-2]+1                  (h>1)

a．证明：

（1）       很明显f[0]=1,f[1]=2。

（2）       首先，对于任意h>1,我们假设t是一颗高度为h的SBT的根结点，则这颗SBT包含一颗高度为h-1的子树。不妨假设t的左子树的高度为h-1，根据f[h]的定义，有

s[left[t] ]≥f[h-1]，同样的，左子树中有一颗高度为h-2的子树，换句话说，左子树中含有一颗结点数至少为f[h-2]的子树。由SBT的性质(b)，可知s[right[t]] ≥f[h-2]。因此我们有s[t]=s[left[t]]+s[right[t]]+1≥f[h-1]+f[h-2]+1。

另外一方面，我们可以构造一颗高度为h，并且结点数正好为f[h]的SBT,称这样的SBT为tree[t]。可以这样来构造tree[h]：

                             含有一个结点的SBT                                    (h=0)

tree[h]=     含有2个结点的任意SBT                             (h=1)

         左子树为tree[h-1],右子树为tree[h-2]的SBT    (h>1)

由f[h]的定义可知f[h] ≤f[h-1]+f[h-2]+1(h>1)。因此f[h]的上下界都为f[h-1]+f[h-2]+1,因此有f[h]=f[h-1]+f[h-2]+1。

b．最坏情况下的高度

事实上f[h]是一个指数函数，通过f[h]的递推可以计算出通项公式。

 

定理：

含有n个结点的SBT在最坏情况下的高度是满足f[h] ≤n的最大的h值。

假设maxh为含有n个结点的SBT的最坏情况下的高度。由上面的定理，有

                                  

于是很明显SBT的高度为O(logn)，是一颗高度平衡的BST！

2．对Maintain操作的分析

通过前面的计算分析我们能够很容易分析出Maintain操作是非常高效的。

首先，有一个非常重要的值来评价一颗BST的好坏：所有结点的平均深度。它是通过所有结点的深度之和SD除以结点个数n计算出来的。一般来说，这个值越小，这颗BST就越好。由于对于一颗BST来说，结点数n是一个常数，因此我们期望SD值越小越好。

现在我们集中来看SBT的SD值，它的重要性在于能够制约Maintain操作的执行时间。回顾先前提到的BST中的旋转操作，有个重要的性质就是：每次执行旋转操作后，SD值总是递减的！

由于SBT树的高度总是O(log n)，因此SD值也总是保持在O（log n）。并且SD仅在插入一个结点到SBT后才增加，因此(T是Maintain操作中执行旋转的次数)

 

Maintain操作的次数等于T加上不需要旋转操作的Maintain操作的次数。由于后者为O(nlogn)+O(T),因此Maintain的平摊分析时间复杂度为：

 

对各个操作时间复杂度的分析

现在我们知道了SBT的高度为O(log n)，并且 Maintain操作的平摊分析时间复杂度为O(1)，因此对于所有的常用操作，时间复杂度都稳定在O(log n)！

     摘要: 目前最快的数独求解程序 - 实现了Knuth的Dancing Links+Algorithm X算法 C++语言: 目前最快的数独求解程序 - 实现了Knuth的Dancing Links+Algorithm X算法 //from: http://code.google.com/p/klsudoku/source/checkout //半瓶墨水修改于 2009 Sept 18 //R...  阅读全文