KK

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
typedef unsigned long U32;
typedef struct _snode {
    U32 key;
    float g,f;
}snode;
#define MAX_OPEN 0x3FFFF
#define MAX_CLOSE 0xFFFFF
snode OPEN[2][MAX_OPEN+1];
int tail[2];
int CLOSE[MAX_CLOSE+1];
int length;
int numof1;
U32 board[20][20]={
0,0x3,0x7,0xF,0x1F,0x3F,0x7F,0xFF,0x1FF,0x3FF,0x7FF,0xFFF,0x1FFF,0x3FFF,0x7FFF,0xFFFF,0x1FFFF,0x3FFFF,0x7FFFF,0xFFFFF,
0,0,0x6,0xE,0x1E,0x3E,0x7E,0xFE,0x1FE,0x3FE,0x7FE,0xFFE,0x1FFE,0x3FFE,0x7FFE,0xFFFE,0x1FFFE,0x3FFFE,0x7FFFE,0xFFFFE,
0,0,0,0xC,0x1C,0x3C,0x7C,0xFC,0x1FC,0x3FC,0x7FC,0xFFC,0x1FFC,0x3FFC,0x7FFC,0xFFFC,0x1FFFC,0x3FFFC,0x7FFFC,0xFFFFC,
0,0,0,0,0x18,0x38,0x78,0xF8,0x1F8,0x3F8,0x7F8,0xFF8,0x1FF8,0x3FF8,0x7FF8,0xFFF8,0x1FFF8,0x3FFF8,0x7FFF8,0xFFFF8,
0,0,0,0,0,0x30,0x70,0xF0,0x1F0,0x3F0,0x7F0,0xFF0,0x1FF0,0x3FF0,0x7FF0,0xFFF0,0x1FFF0,0x3FFF0,0x7FFF0,0xFFFF0,
0,0,0,0,0,0,0x60,0xE0,0x1E0,0x3E0,0x7E0,0xFE0,0x1FE0,0x3FE0,0x7FE0,0xFFE0,0x1FFE0,0x3FFE0,0x7FFE0,0xFFFE0,
0,0,0,0,0,0,0,0xC0,0x1C0,0x3C0,0x7C0,0xFC0,0x1FC0,0x3FC0,0x7FC0,0xFFC0,0x1FFC0,0x3FFC0,0x7FFC0,0xFFFC0,
0,0,0,0,0,0,0,0,0x180,0x380,0x780,0xF80,0x1F80,0x3F80,0x7F80,0xFF80,0x1FF80,0x3FF80,0x7FF80,0xFFF80,
0,0,0,0,0,0,0,0,0,0x300,0x700,0xF00,0x1F00,0x3F00,0x7F00,0xFF00,0x1FF00,0x3FF00,0x7FF00,0xFFF00,
0,0,0,0,0,0,0,0,0,0,0x600,0xE00,0x1E00,0x3E00,0x7E00,0xFE00,0x1FE00,0x3FE00,0x7FE00,0xFFE00,
0,0,0,0,0,0,0,0,0,0,0,0xC00,0x1C00,0x3C00,0x7C00,0xFC00,0x1FC00,0x3FC00,0x7FC00,0xFFC00,
0,0,0,0,0,0,0,0,0,0,0,0,0x1800,0x3800,0x7800,0xF800,0x1F800,0x3F800,0x7F800,0xFF800,
0,0,0,0,0,0,0,0,0,0,0,0,0,0x3000,0x7000,0xF000,0x1F000,0x3F000,0x7F000,0xFF000,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x6000,0xE000,0x1E000,0x3E000,0x7E000,0xFE000,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xC000,0x1C000,0x3C000,0x7C000,0xFC000,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x18000,0x38000,0x78000,0xF8000,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x30000,0x70000,0xF0000,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x60000,0xE0000,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xC0000,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//像不像一把刀？^o^
};
U32 Bit32[32]={
0x1,0x2,0x4,0x8,
0x10,0x20,0x40,0x80,
0x100,0x200,0x400,0x800,
0x1000,0x2000,0x4000,0x8000,
0x10000,0x20000,0x40000,0x80000,
0x100000,0x200000,0x400000,0x800000,
0x1000000,0x2000000,0x4000000,0x8000000,
0x10000000,0x20000000,0x40000000,0x80000000
};
int Get01String(FILE *fin,U32 &str)
{
    char c;
    int count=0,num=0;
    str=0x0;
    while(1)
    {
        c=getc(fin);
        if(c==EOF)
            return 0;
        if(c!='\n')
        {
            str=str<<1;
            if(c=='1')
            {
                str=str | 0x1;
                ++num;
            }
            ++count;
            break;
        }
    }
    while(1)
    {
        c=getc(fin);
        if(c==EOF)
            return 0;
        if(c=='\n')
            break;
        str=str<<1;
        if(c=='1')
        {
            str=str | 0x1;
            ++num;
        }
        ++count;
    }
    if(num>(count/2))
    {
        str=str ^ ((0x1 << count) - 0x1);
        numof1=count-num;
    }
    else
    {
        numof1=num;
    }
    return length=count;
}
void PrintU32(U32 n)
{
    while(n)
    {
        if(n & 0x80000000)
            printf("1");
        else
            printf("0");
        n=n << 1;
    }
    printf("\n");
}
inline void GetCArr(const snode &s,int *goal)
{
    int i,j,t1=0,t2=0;
    for(i=0;i<length;++i)
    {
        if(s.key & Bit32[i])
        {
            if(t1==0)//first time got 1
            {
                goal[t2]=1;
                t1=1;
            }
            else
            {
                goal[t2]++;
            }
        }
        else
        {
            if(t1==1)//first time got 0
            {
                //printf("%d,",goal[t2]);
                t2++;
            }
            t1=0;
        }
    }
    //printf("\n");
    //sort
    for(i=0;i<10;++i)
    {
        for(j=i+1;j<10;++j)
        {
            if(goal[i]<goal[j])
            {
                int tmp=goal[i];
                goal[i]=goal[j];
                goal[j]=tmp;
            }
        }
    }
}

float hFunction(snode &s,int *goal)
{
    int CArr[10];
    int deltac=0;
    memset(CArr,0,sizeof(CArr));
    GetCArr(s,CArr);
#define ABS(a) ((a)<0?-(a):(a))
    for(int i=0;i<10;++i)
        deltac+=ABS(CArr[i]-goal[i]);
    if(numof1<deltac)
        return (float)deltac/((numof1 << 1)-deltac);
    return (float)deltac/numof1;
}

int MySearch(U32 a,U32 b)
{
    int i,j,k,s;
    int goal[2][10];
    snode curt;
    memset(CLOSE,-1,sizeof(CLOSE));
    memset(goal,0,sizeof(goal));

    curt.key=a;
    GetCArr(curt,goal[1]);
    curt.key=b;
    GetCArr(curt,goal[0]);

    curt.g=0;

    curt.key=a;
    curt.f=hFunction(curt,goal[0]);
    OPEN[0][0]=curt;
    tail[0]=1;

    curt.key=b;
    curt.f=hFunction(curt,goal[1]);
    OPEN[1][0]=curt;
    tail[1]=1;

    int t=0;

    while(tail[t]>0 && tail[t]<=MAX_OPEN)
    {
        //select s
        for(s=0,i=1;i<tail[t];++i)
        {
            if(OPEN[t][s].f>OPEN[t][i].f)
                s=i;
        }
        curt=OPEN[t][s];

        //PrintU32(curt.key);
        //printf("g=%f,f=%f\n",curt.g,curt.f);

        if(CLOSE[curt.key & MAX_CLOSE]==-1)
        {//扩展该结点

            CLOSE[curt.key & MAX_CLOSE]=(int)curt.g;
            int oldtail=tail[t];
            for(i=0;i<length;++i)
            {
                for(j=i+1;j<length;++j)
                {
                    U32 tmp=(curt.key & board[i][j]) >> i;
                    U32 revs=0x0;
                    //reverse tmp
                    for(k=0;k<=j-i;++k)
                    {
                        revs=revs << 1;
                        if(tmp & 0x1)
                            revs=revs | 0x1;
                        tmp=tmp >> 1;
                    }
                    revs=revs << i;
                    snode child;
                    child.key=(curt.key & (~board[i][j])) | revs;
                    if(CLOSE[child.key & MAX_CLOSE]>=0)
                        continue;


                    for(k=oldtail;k<tail[t];++k)
                    {
                        if(child.key==OPEN[t][k].key)
                            break;
                    }
                    if(k!=tail[t])
                        continue;

                    child.g=curt.g+1;

                    int rt=t ^ 0x1;
                    for(k=0;k<tail[rt];++k)
                    {
                        if(child.key==OPEN[rt][k].key)
                            return (int)(child.g+OPEN[rt][k].g);
                    }

                    child.f=child.g+hFunction(child,goal[t]);

                    OPEN[t][tail[t]]=child;
                    tail[t]++;
                    //tail[t]=(tail[t]+1) & MAX_OPEN;
                    //PrintU32(child.key);
                }
            }
        }
        tail[t]--;
        OPEN[t][s]=OPEN[t][tail[t]];

        t=t ^ 0x1;
    }
    return 0;
}

void CreateTestData(int n,int m)
{//n串长(2<=n<=20)，m串中1的个数(1<=m<n)
    char str[128];
    int i,p;
    for(i=0;i<n;++i)
        str[i]='0';
    str[n]='\0';
    for(i=0;i<m;++i)
    {
        p=rand()%n;
        while(str[p]=='1')
            p=rand()%n;
        str[p]='1';
    }
    printf("%s\n",str);
}
int main(void)
{
    
    U32 a,b;

    while(1)
    {
        if(0==Get01String(stdin,a))
            break;
        if(0==Get01String(stdin,b))
            break;
        if(0==numof1)
            printf("0\n");
        else
            printf("%d\n",MySearch(a,b));
        /*
        PrintU32(a);
        PrintU32(b);
        printf("Length=%d\nNum of 1 =%d\n",length,numof1);
        
        int CArr[10];
        snode tmp;
        tmp.key=a;
        memset(CArr,0,sizeof(CArr));
        GetCArr(tmp,CArr);
        tmp.key=b;
        printf("h=%d\n",hFunction(tmp,CArr));
        */
    }
    
    /*
    int n,m;
    srand(time(0));
    while(1)
    {
        scanf("%d%d",&n,&m);
        if(n==0)
            break;
        CreateTestData(n,m);
    }
    */

    return 0;
}

怎么回事

#include<stdio.h>
int min =99;
int num2[20];
void change(int a[],int n,int point,int tie,int now);
main()
{
      char a[21];
      char b[21];
      int num1[20];
    
      int i,j=0 ;
      scanf("%s",a);
      scanf("%s",b);
      for(i = 0; i<20;i++)
      {
      if( a[i] == '0' || a[i] == '1' )
      {
               num1[j] = (int)a[i]-48;
               num2[j] = (int)b[i]-48;
               j++;
       }
       else break;
      }
      change(num1,j,-1,0,0);
        printf("%d",min);
        getch();
}
void diandao(int num[],int now,int tie)
{
     int i;
     int j;

     for( i = 0; i < (tie-now+1)/2;i++)
     {
          j= num[i+now];
          num[i+ now] = num[tie-i];
          num[tie-i] = j;
     }
     return ;
}
void change(int a[],int n,int point,int tie,int now)
{
           int num[20];
           int i;
           point++;
                  
             for(i = 0;i < n; i++)
             {
                 num[i] = a[i] ;
             }
             if( tie > now)
             {
                 diandao(num,now,tie);
                 now++; 
             }
              
             for( i = now;i < n;i++)
             {
                    if( now == n-1)
                     {
               
                       if(point < min)
                       min = point;
                       return;
                      }
                     else
                     if(num[i] == num2[i])
                     {
                          now++;
                     }
                    else
                    break;
             }   
               
             if( now == n-1)
             {
               
               if(point < min)
               min = point;
               return;
             }
            
             for( i = now;i < n; i++)
             {
                if( num[now] == num2[i] )
                change(num,n,point,i,now);
             }
          return;
}

想不出好办法

盛大

第一题:

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define MAX 1048760

char *q[184800];
int head=0,rear=0;
int arrived[MAX][2];
int len;
int BFS(char *,char *);
int Atoi(char *);
char* reverse(char *,int a,int b);

int main()
{
    char a[21],b[21];
    int ans;
    memset((void*)arrived,0,sizeof(arrived));
    scanf("%s%s",a,b);
    len=strlen(a);
    ans=BFS(a,b);
    printf("%d\n",ans);
    return 0;
}

int BFS(char *a,char *b)
{
    int i,j,k,l;
    int dest=Atoi(b);
    int start=Atoi(a);
    q[head]=(char *)malloc(len+1);
    strcpy(q[head],a);
    arrived[start][0]=1;
    while(head<=rear&&arrived[dest][0]==0){
        l=Atoi(q[head]);
        for(i=0;i<len;i++){
            for(j=i;q[head][i]==q[head][j];j++);
            for(;j<len;j++){
                q[++rear]=(char *)malloc(len+1);
                strcpy(q[rear],reverse(q[head],i,j));
                k=Atoi(q[rear]);
                if(arrived[k][0]==0){
                    arrived[k][0]=1;
                    arrived[k][1]=arrived[l][1]+1;
                }
                else
                    free(q[rear--]);
            }
        }
        head++;
    }
    return arrived[dest][1];
}

char* reverse(char *s,int a,int b)
{
    char *ss=(char *)malloc(len+1);
    int i,j;
    for(i=0;i<a;i++)
        ss[i]=s[i];
    for(i=a;i<=b;i++)
        ss[i]=s[a+b-i];
    for(i=b+1;i<len;i++)
        ss[i]=s[i];
    ss[len]='\0';
    return ss;
}

int Atoi(char *a)
{
    int len=strlen(a);
    int i,value=0;
    for(i=0;i<len;i++)
        value+=(int)pow(2,i)*(a[i]-'0');
    return value;
}

第二题:
有三个函数,请加上相应的函数头,初次比赛,请多关照

#define MAX 10000000
int Least(int a[],int n)
{
    int b[MAX][2],c[MAX];
    int i,count=0,j;
    memset((void*)c,0,sizeof(c));
    for(i=0;i<n;i++){
        b[i][0]=a[i];
        b[i][1]=i;
    }
    quicksort(b,0,n-1);
    for(i=0;i<n;i++)
        if(c[i]==0){
            c[i]=1;
            j=i;
            while(c[b[j][1]]==0){
                j=b[j][1];
                c[j]=1;
            }
            count++;
        }
    return n-count;
}

int quicksort(int base[MAX][2],int left,int right)
{
    int i,last;
    if(left>=right)
        return 0;
    last=left;
    swap(base,left,(left+right)/2);
    for(i=left+1;i<=right;i++)
        if(base[i][0]<base[left][0])
            swap(base,++last,i);
    swap(base,left,last);
    quicksort(base,left,last-1);
    quicksort(base,last+1,right);
    return 0;
}

void swap(int base[MAX][2],int num1,int num2)
{
    long temp;
    temp=base[num2][0];
    base[num2][0]=base[num1][0];
    base[num1][0]=temp;
    temp=base[num2][1];
    base[num2][1]=base[num1][1];
    base[num1][1]=temp;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int Reverse(char *str1,char *str2)
{
    int max=0,maxpre,count;
    int i,j;
    int **lcs;
    int len;
    len=strlen(str1);
    lcs=(int **)malloc((len)*sizeof(int));
    if(lcs==NULL)
    {
        printf("Out of space!\n");
        exit(1);
    }
    for(i=0;i<len;i++)
    {
        *(lcs+i)=(int *)malloc((len)*sizeof(int));
        if(*(lcs+i)==NULL)
        {
            printf("Memory allocate failed!\n");
            exit(1);
        }
    }
    for(j=0;j<len;j++)
        if(str1[0]==str2[j])
            lcs[0][j]=1;
        else
            lcs[0][j]=0;
    count=1;
    maxpre=1;
    for(i=1;i<len;i++)
    {
        max=0;
        for(j=0;j<len-1;j++)
        {
            if(str1[i]==str2[j])
            {
                lcs[i][j]=lcs[i-1][j+1]+1;
                max=max<lcs[i][j]?lcs[i][j]:max;
            }
            else
                lcs[i][j]=0;                
        }
        if(str1[i]==str2[j])
            lcs[i][j]=1;
        else
            lcs[i][j]=0;
        if(max>=maxpre)
                maxpre=max;
        else 
        {
            maxpre=1;
            count++;
        }        
    }
    return count;
}

main()
{
    char str1[21]="";
    char str2[21]="";
    int res=0;
    scanf("%s",str1);
    scanf("%s",str2);
    res=Reverse(str2,str1);
    printf("Result=%d\n",res);

}