Johnnx-acmore

这是一个字符串处理的问题。通过这道题，我得到3点收获：一、借用事先定义的map[]数组来简化字母与数字之间的转换；二、设置两个数组，一个用来输入，一个用来存储转化以后的。这样可以方便转化；三、如何输出这些重复字符串和对它们进行计数。code

这是一道深搜回溯的题目。我这个新手初次做深搜，浏览了无数大牛的解题报告，收获很大。我原来总以为是要用栈来存储结点，却没想到回溯如此简单。code

这道题是一道关于字符串转换的问题，没有包括复杂的算法，应该是一道水题，可是我却在这道题上花费了一些时间，原因是Sample Input中的两个输入数据应该是同一类数据，我一开始却认为是两种不同的输入。后来才知道是同一类输入。第二个只是第一个的特殊情况罢了。还是不熟悉，还得多练习啊。code

又是一道广搜题，可这次却有个不一样的地方，除了求出最短步数外，还要输出最短路径出来。在原来结点的基础上，增加pre和flag两个变量，分别记录父结点在队列中的位置和进行哪种操作。记录最短路径让我费了一些周折。看来这里还是不很熟悉，以后得多加练习和思考ccode

这道题目在网上的一些分类中把它分在BFS的范围，可是只需用程序模拟出题目中说明的过程，就可以直接得出结果了code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef struct node{
 5     char e;
 6     struct node *l,*r;
 7 }*tree;
 8 tree t;
 9 char s1[27],s2[27];
10 tree create(int pa,int pb,int ia,int ib);
11 void postorder(tree T);
12 int main()
13 {
14     int len;
15     while(scanf("%s%s",s1,s2) != EOF){
16         len = strlen(s1);
17         t = create(0,len-1,0,len-1);
18         postorder(t);
19         printf("\n");
20     }
21     system("pause");
22     return 0;
23 }
24 tree create(int pa,int pb,int ia,int ib)
25 {
26     int i;
27     tree T;
28     if(pa <= pb && ia <= ib){
29         T = (tree)malloc(sizeof(struct node));
30         T->e = s1[pa];
31         for(i = ia;i <= ib;i++){
32             if(s1[pa] == s2[i])break;
33         }
34         int len1 = i - ia;
35         T->l = create(pa+1,pa+len1,ia,i-1);
36         T->r = create(pa+len1+1,pb,i+1,ib);
37     }
38     else
39         T = NULL;
40     return T;
41 }
42 void postorder(tree T)
43 {
44     if(T != NULL){
45         postorder(T->l);
46         postorder(T->r);
47         printf("%c",T->e);
48     }
49 }
50 

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 char s1[27],s2[27];
 5 void createprint(int pa,int pb,int ia,int ib);
 6 int main()
 7 {
 8     int len;
 9     while(scanf("%s%s",s1,s2) != EOF){
10         len = strlen(s1);
11         createprint(0,len-1,0,len-1);
12         printf("\n");
13     }
14     system("pause");
15     return 0;
16 }
17 void createprint(int pa,int pb,int ia,int ib)
18 {
19     int i;
20     if(pa == pb){
21         printf("%c",s1[pa]);
22         return;
23     }
24     if(pa > pb || ia > ib)return;
25     for(i = ia;i <= ib;i++)
26         if(s1[pa] == s2[i])break;
27     int len1 = i - ia;
28     createprint(pa+1,pa+len1,ia,i-1);
29     createprint(pa+len1+1,pb,i+1,ib);
30     printf("%c",s1[pa]);
31 }
32 

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef struct node{
 5     int x,step;
 6 }Node;
 7 struct queue{
 8     Node array[100001];
 9     int front,rear;
10 }Queue;
11 int N,K;
12 int visit[100001];
13 void enqueue(Node data);
14 Node dequeue();
15 int judge();
16 int bfs();
17 int main()
18 {
19     while(scanf("%d %d",&N,&K) != EOF){
20         Queue.front = Queue.rear = 0;
21         memset(visit,0,sizeof(visit));
22         if(N == K)printf("0\n");
23         else
24             printf("%d\n",bfs());
25     }
26     system("pause");
27     return 0;
28 }
29 
30 void enqueue(Node data)
31 {
32     Queue.array[Queue.rear].x = data.x;
33     Queue.array[Queue.rear].step = data.step;
34     Queue.rear++;
35 }
36 Node dequeue()
37 {
38     Node data;
39     data.x = Queue.array[Queue.front].x;
40     data.step = Queue.array[Queue.front].step;
41     Queue.front++;
42     return data;
43 }
44 int judge()
45 {
46     if(Queue.front == Queue.rear)return 0;
47     return 1;
48 }
49 
50 int bfs()
51 {
52     Node lc,lx;
53     lx.x = N;
54     lx.step = 0;
55     visit[N] = 1;
56     enqueue(lx);
57     while(judge()){
58         lc = dequeue();
59         for(int i = 0;i < 3;i++){
60             if(i == 0){
61                 lx.x = lc.x-1;
62                 lx.step = lc.step+1;
63                 if(lx.x == K)return lx.step;
64                 else if(!visit[lx.x] && lx.x >= 0 && lx.x < 100001){
65                     visit[lx.x] = 1;
66                     enqueue(lx);
67                 }
68             }
69             if(i == 1){
70                 lx.x = lc.x+1;
71                 lx.step = lc.step+1;
72                 if(lx.x == K)return lx.step;
73                 else if(!visit[lx.x] && lx.x >= 0 && lx.x < 100001){
74                     visit[lx.x] = 1;
75                     enqueue(lx);
76                 }
77             }
78             if(i == 2){
79                 lx.x = lc.x*2;
80                 lx.step = lc.step+1;
81                 if(lx.x == K)return lx.step;
82                 else if(!visit[lx.x] && lx.x >= 0 && lx.x < 100001){
83                     visit[lx.x] = 1;
84                     enqueue(lx);
85                 }
86             }
87         }
88     }
89 }
90 

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 char a[101][7],s[7];
 5 int compare(const void *p,const void *q)
 6 {
 7     return (*(char *)p - *(char *)q);
 8 }
 9 int check(char p[7],char q[7]);
10 int main()
11 {
12     char c[7];
13     int i,j,flag,n;
14     i = 0;
15     while(scanf("%s",&a[i]) && strcmp(a[i],"XXXXXX")){
16         i++;
17     }
18     n = i;
19     for(i = 0;i < n-1;i++){
20         for(j = i;j < n;j++){
21             if(strcmp(a[i],a[j]) > 0){
22                 strcpy(c,a[i]);
23                 strcpy(a[i],a[j]);
24                 strcpy(a[j],c);
25             }
26         }
27     }
28     while(scanf("%s",s) && strcmp(s,"XXXXXX")){
29         flag = 1;
30         for(j = 0;j < n;j++){
31             if(check(s,a[j])){
32                 flag = 0;
33                 printf("%s\n",a[j]);
34             }
35         }
36         if(flag){
37             printf("NOT A VALID WORD\n");
38         }
39         printf("******\n");
40     }
41     system("pause");
42     return 0;
43 }
44 int check(char p[7],char q[7])
45 {
46     char c[7];
47     int len1,len2;
48     int i;
49     len1 = strlen(p);
50     len2 = strlen(q);
51     if(len1 != len2)
52     return 0;
53     strcpy(c,q);
54     qsort(c,len2,sizeof(char),compare);
55     qsort(p,len1,sizeof(char),compare);
56     for(i = 0;i < len1;i++){
57         if(c[i] != p[i]){
58            return 0;
59         }
60     } 
61     return 1;
62 }
63 我在做1318时遇到过一个问题，当对字典字符串排序时不能用qsort,因为它只对各个字符串首字母进行排序，比如：输入Sample Input 中的tarp,trap,用aptr查时结果却是trap在前面。但是如果是用C++则可直接调用sort对字典进行排序。没办法，只有自己编了，19~27行，用了一般的排序方法，两个for循环，时间达到了O（n^2）,但是竟然是0MS，AC。我想可能是因为题目把字典字符串数限制在100以内吧，数量不大。