http://acm.pku.edu.cn/JudgeOnline/problem?id=1002
這是一個(gè)字符串處理的問題。通過這道題，我得到3點(diǎn)收獲：一、借用事先定義的map[]數(shù)組來簡化字母與數(shù)字之間的轉(zhuǎn)換；二、設(shè)置兩個(gè)數(shù)組，一個(gè)用來輸入，一個(gè)用來存儲(chǔ)轉(zhuǎn)化以后的。這樣可以方便轉(zhuǎn)化；三、如何輸出這些重復(fù)字符串和對(duì)它們進(jìn)行計(jì)數(shù)。
1
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5
6 int n;
7 char a[100001][20],str[50];
8 char map[] = "2223334445556667777888999";//
9
10 int compare(const void *p,const void *q){
11 return (strcmp((char*)p,(char*)q));
12 }
13 int main()
14 {
15 while(scanf("%d",&n) != EOF){
16 for(int i = 0;i < n;++i){
17 int flag = 0;
18 scanf("%s",str);
19 int j = 0,k = 0;
20 while(k < 8){//
21 if(k == 3){
22 a[i][k++] = '-';
23 continue;
24 }
25 if(str[j] <= 'Z' && str[j] >= 'A'){
26 a[i][k++] = map[str[j++] - 'A'];
27 continue;
28 }
29 else if(str[j] == '-'){
30 j++;
31 continue;
32 }
33 a[i][k++] = str[j++];
34 }
35 a[i][8] = '\0';
36 }
37 qsort(a,n,20,compare);
38 int noduplicates = 1;
39 int p,q;
40 p = 0;
41 while(p < n){//
42 q = p;
43 p++;
44 while(p < n && !strcmp(a[p],a[q]))p++;
45 if(p - q > 1){
46 printf("%s %d\n",a[q],p - q);
47 noduplicates = 0;
48 }
49 }
50 if(noduplicates)printf("No duplicates.\n");
51 }
52
53
54
55 system("pause");
56 return 0;
57 }
58
code
http://acm.pku.edu.cn/JudgeOnline/problem?id=2488
這是一道深搜回溯的題目。我這個(gè)新手初次做深搜，瀏覽了無數(shù)大牛的解題報(bào)告，收獲很大。我原來總以為是要用棧來存儲(chǔ)結(jié)點(diǎn)，卻沒想到回溯如此簡單。
1 #include<stdio.h>
2 #include<stdlib.h>
3 int n;
4 int r,c;
5 int ok;
6 int visit[100][100];
7 int px[50],py[50];
8 int yy[8] = {-1,1,-2,2,-2,2,-1,1};//在這就把輸出字典順序確定了
9 int xx[8] = {-2,-2,-1,-1,1,1,2,2};
10
11 int isok(int x,int y)
12 {
13 return x >= 1 && x <= r && y >= 1 && y <= c;
14 }
15
16 void dfs(int x,int y,int length);
17 int main()
18 {
19 scanf("%d",&n);
20 for(int i =1;i <= n;i++){
21 scanf("%d%d",&c,&r);
22 visit[1][1] = 1;
23 ok = 0;
24 dfs(1,1,1);
25 printf("Scenario #%d:\n",i);
26 if(ok){
27 for(int j = 1;j <= r*c;j++){
28 printf("%c",px[j]+'A'-1);
29 printf("%d",py[j]);
30 }
31 }
32 else printf("impossible");
33 printf("\n\n");
34 }
35 system("pause");
36 return 0;
37
38 }
39 void dfs(int x,int y,int length)
40 {
41 px[length] = x;
42 py[length] = y;
43 if(length == r*c){
44 ok = 1;
45 return;
46 }
47 for(int i = 0;i < 8;i++){
48 int tx = x + xx[i];
49 int ty = y + yy[i];
50 if(isok(tx,ty) && !visit[tx][ty] && !ok){
51 visit[tx][ty] = 1;
52 dfs(tx,ty,length+1);
53 visit[tx][ty] = 0;//巧妙，也是必須的
54 }
55 }
56 }
57
code
http://acm.pku.edu.cn/JudgeOnline/problem?id=3488
這道題是一道關(guān)于字符串轉(zhuǎn)換的問題，沒有包括復(fù)雜的算法，應(yīng)該是一道水題，可是我卻在這道題上花費(fèi)了一些時(shí)間，原因是Sample Input中的兩個(gè)輸入數(shù)據(jù)應(yīng)該是同一類數(shù)據(jù)，我一開始卻認(rèn)為是兩種不同的輸入。后來才知道是同一類輸入。第二個(gè)只是第一個(gè)的特殊情況罷了。還是不熟悉，還得多練習(xí)啊。
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 char matrix[1001][1001];
5 int n;
6 char result[1003];
7 int main()
8 {
9 while(scanf("%d",&n) != EOF){
10 for(int i = 0;i < n;i++){
11 scanf("%s",&matrix[i][0]);
12 }
13 int t = 0;
14 int len = strlen(matrix[0]);
15 for(int j = 0;j < len;j++){
16 for(int i = 0;i < n;i++)
17 result[t++] = matrix[i][j];
18 }
19 for(int i = t-1;i >= 0;i--){
20 if(result[i] == '_'){
21 printf(" ");
22 continue;
23 }
24 if(result[i] == '\\'){
25 printf("\n");
26 continue;
27 }
28 printf("%c",result[i]);
29 }
30 printf("\n\n");
31 }
32 system("pause");
33 return 0;
34 }
35
code
http://acm.pku.edu.cn/JudgeOnline/problem?id=3414又是一道廣搜題，可這次卻有個(gè)不一樣的地方，除了求出最短步數(shù)外，還要輸出最短路徑出來。在原來結(jié)點(diǎn)的基礎(chǔ)上，增加pre和flag兩個(gè)變量，分別記錄父結(jié)點(diǎn)在隊(duì)列中的位置和進(jìn)行哪種操作。記錄最短路徑讓我費(fèi)了一些周折。看來這里還是不很熟悉，以后得多加練習(xí)和思考c
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int a,b,c;
5 typedef struct node{
6 int liter1,liter2,step,pre,flag;
7 }Node;
8 typedef struct queue{
9 Node q[11000];
10 int front,rear;
11 }Queue;
12 Queue Q;
13 int path[11000],j;
14 int visit[101][101];
15 void bfs();
16 int main()
17 {
18 while(scanf("%d%d%d",&a,&b,&c) != EOF)
19 bfs();
20 system("pause");
21 return 0;
22 }
23
24 void bfs()
25 {
26 Node pot;
27 Node lx,lc;
28 memset(visit,0,sizeof(visit));
29 pot.liter1 = 0;
30 pot.liter2 = 0;
31 pot.step = 0;
32 pot.pre = -1;
33 Q.front = Q.rear = 1;
34 Q.q[Q.rear++] = pot;
35 visit[0][0] = 1;
36 while(Q.front != Q.rear){
37 lc = Q.q[Q.front++];
38 if(lc.liter1 == c || lc.liter2 == c)break;
39 for(int i = 1;i < 7;i++){
40 if(i == 1){
41 lx.liter1 = a;
42 lx.liter2 = lc.liter2;
43 lx.step = lc.step + 1;
44 lx.pre = Q.front-1;
45 lx.flag = i;
46 if(visit[lx.liter1][lx.liter2] == 0){
47 visit[lx.liter1][lx.liter2] = 1;
48 Q.q[Q.rear++] = lx;
49 }
50 }
51 if(i == 2){
52 lx.liter1 = lc.liter1;
53 lx.liter2 = b;
54 lx.step = lc.step + 1;
55 lx.pre = Q.front-1;
56 lx.flag = i;
57 if(visit[lx.liter1][lx.liter2] == 0){
58 visit[lx.liter1][lx.liter2] = 1;
59 Q.q[Q.rear++] = lx;
60 }
61 }
62 if(i == 3){
63 lx.liter1 = 0;
64 lx.liter2 = lc.liter2;
65 lx.step = lc.step + 1;
66 lx.pre = Q.front-1;
67 lx.flag = i;
68 if(visit[lx.liter1][lx.liter2] == 0){
69 visit[lx.liter1][lx.liter2] = 1;
70 Q.q[Q.rear++] = lx;
71 }
72 }
73 if(i == 4){
74 lx.liter1 = lc.liter1;
75 lx.liter2 = 0;
76 lx.step = lc.step + 1;
77 lx.pre = Q.front-1;
78 lx.flag = i;
79 if(visit[lx.liter1][lx.liter2] == 0){
80 visit[lx.liter1][lx.liter2] = 1;
81 Q.q[Q.rear++] = lx;
82 }
83 }
84 if(i == 5){//2 to 1
85 if(lc.liter1 + lc.liter2 > a){
86 lx.liter1 = a;
87 lx.liter2 = lc.liter1 + lc.liter2 - a;
88 }
89 else{
90 lx.liter1 = lc.liter1 + lc.liter2;
91 lx.liter2 = 0;
92 }
93 lx.step = lc.step + 1;
94 lx.pre = Q.front-1;
95 lx.flag = i;
96
97 if(visit[lx.liter1][lx.liter2] == 0){
98 visit[lx.liter1][lx.liter2] = 1;
99 Q.q[Q.rear++] = lx;
100 }
101 }
102 if(i == 6){//1 to 2
103 if(lc.liter1 + lc.liter2 > b){
104 lx.liter1 = lc.liter1 + lc.liter2 - b;
105 lx.liter2 = b;
106 }
107 else{
108 lx.liter1 = 0;
109 lx.liter2 = lc.liter1 + lc.liter2;
110 }
111 lx.step = lc.step + 1;
112 lx.pre = Q.front-1;
113 lx.flag = i;
114
115 if(visit[lx.liter1][lx.liter2] == 0){
116 visit[lx.liter1][lx.liter2] = 1;
117 Q.q[Q.rear++] = lx;
118 }
119 }
120 }
121 }
122 if(Q.front == Q.rear){
123 printf("impossible\n");
124 return;
125 }
126 j = 0;
127 for(int i = Q.front-1;i>=0;){
128 path[j++] = i;
129 i = Q.q[i].pre;
130 }
131 printf("%d\n",Q.q[Q.front-1].step);
132 for(int i = j-1;i>= 0;i--){
133 switch(Q.q[path[i]].flag){
134 case 1:printf("FILL(1)\n");break;
135 case 2:printf("FILL(2)\n");break;
136 case 3:printf("DROP(1)\n");break;
137 case 4:printf("DROP(2)\n");break;
138 case 5:printf("POUR(2,1)\n");break;
139 case 6:printf("POUR(1,2)\n");break;
140 }
141 }
142
143 }
code
http://acm.pku.edu.cn/JudgeOnline/problem?id=3087這道題目在網(wǎng)上的一些分類中把它分在BFS的范圍，可是只需用程序模擬出題目中說明的過程，就可以直接得出結(jié)果了c
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int n,m;
5 char s1[101],s2[101],s[201];
6 int process();
7 int main()
8 {
9 scanf("%d",&n);
10 int i = 1;
11 while(n--){
12 scanf("%d %s %s %s",&m,s1,s2,s);
13 printf("%d %d\n",i++,process());
14 }
15 system("pause");
16 return 0;
17 }
18
19 int process()
20 {
21 int i;
22 int step = 1;
23 char cmp[201],p1[101],p2[101];
24 strcpy(p1,s1);
25 strcpy(p2,s2);
26 int a = 2;
27 while(1){
28 for(i = 0;i < m;i++){
29 cmp[i*2] = p2[i];
30 }
31 for(i = 0;i < m;i++){
32 cmp[i*2+1] = p1[i];
33 }
34 cmp[2*m] = '\0';
35 if(!strcmp(cmp,s))return step;
36 for(i = 0;i < m;i++){
37 p1[i] = cmp[i];
38 p2[i] = cmp[i+m];
39 }
40 p1[m] = '\0';
41 p2[m] = '\0';
42 if(!strcmp(p1,s1) && !strcmp(p2,s2))break;
43 step++;
44 }
45 return -1;
46 }
47
ode
摘要: POJ3126（http://acm.pku.edu.cn/JudgeOnline/problem?id=3126）是一道很經(jīng)典的廣搜題。我在網(wǎng)上看到有多種不同的搜索思路，所以自己也把這些不同的方法一一試了遍。方法1：從隊(duì)列中取出的節(jié)點(diǎn)數(shù)據(jù)，分個(gè)十百千四種情況，利用i循環(huán)，推出下一節(jié)點(diǎn)，再使其入隊(duì)cCode highlighting produced by Actipro CodeHighligh...
閱讀全文
這是一個(gè)樹的遍歷轉(zhuǎn)換問題，已知樹的前序遍歷和中序遍歷，求出樹的后序遍歷。一開始的想法是先利用前序遍歷和中序遍歷，構(gòu)造出二叉樹，再對(duì)這個(gè)二叉樹進(jìn)行后序遍歷輸出但
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
是后來在網(wǎng)上看到一些大牛的作法：直接利用遞歸，就可以后序輸出結(jié)果這
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
是太巧妙了，可以省略掉建樹這一步。這道題的代碼雖然不長，也可以因此減少幾乎一半的代碼。我還得好好體會(huì)體會(huì)。
這道題目是利用廣度優(yōu)先搜索的算法我
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
用的是C，隊(duì)列得自己寫，如果是C++的話，可以直接調(diào)用Queue庫，減少很多代碼。
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時(shí)遇到過一個(gè)問題，當(dāng)對(duì)字典字符串排序時(shí)不能用qsort,因?yàn)樗粚?duì)各個(gè)字符串首字母進(jìn)行排序，比如：輸入Sample Input 中的tarp,trap,用aptr查時(shí)結(jié)果卻是trap在前面。但是如果是用C++則可直接調(diào)用sort對(duì)字典進(jìn)行排序。沒辦法，只有自己編了，19~27行，用了一般的排序方法，兩個(gè)for循環(huán)，時(shí)間達(dá)到了O（n^2）,但是竟然是0MS，AC。我想可能是因?yàn)轭}目把字典字符串?dāng)?shù)限制在100以內(nèi)吧，數(shù)量不大。
POJ 2418這個(gè)題目要求輸入多個(gè)字符串，按
alphabetical（字母大小）順序輸出，并且統(tǒng)計(jì)每種字符串出現(xiàn)的百分比。其中重要的一點(diǎn)就是對(duì)字符串進(jìn)行排序，這時(shí)我們考慮用BST（二叉搜索樹）來存儲(chǔ)數(shù)據(jù)，然后按中序輸出，至于百分比在存儲(chǔ)數(shù)據(jù)時(shí)附加上就行了。BST是一個(gè)很高效的算法，插入時(shí)的時(shí)間復(fù)雜度是線性的。 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 char a[31];
5 typedef struct nod{
6 char b[31];
7 int num;
8 struct nod *lchild,*rchild;
9 }node;
10 node *bt;
11 int count = 0;
12 void Insert();
13 void print(node *p);
14 int main()
15 {
16 bt = NULL;
17 while(strcmp(gets(a),"##")){
18 count++;
19 Insert();
20 }
21 print(bt);
22 system("pause");
23 return 0;
24 }
25 void Insert()
26 {
27 node *p = bt;
28 node *q = NULL;//q在這里有2個(gè)作用 ，太巧妙了
29 int flag = 0;
30 while(p != NULL){
31 if(!strcmp(a,p->b)){
32 p->num++;
33 return;
34 }
35 q = p;
36 p = strcmp(a,p->b) > 0?p->rchild:p->lchild;
37 flag = 1;
38 }
39 if(q == NULL){//q的第1個(gè)作用：判斷是否為空樹
40 bt = (node *)malloc(sizeof(struct nod));
41 strcpy(bt->b,a);
42 bt->num = 1;
43 bt->lchild = NULL;
44 bt->rchild = NULL;
45 }
46 else{
47 if(flag){
48 p = (node *)malloc(sizeof(struct nod));
49 strcpy(p->b,a);
50 p->num = 1;
51 p->lchild = NULL;
52 p->rchild = NULL;
53 }
54 if(strcmp(q->b,a) > 0){//q的第2個(gè)作用：記錄p結(jié)點(diǎn)，以便能使插入的結(jié)點(diǎn)連接到樹中
55 q->lchild = p;
56 }
57 else{
58 q->rchild = p;
59 }
60 }
61 }
62 void print(node *p)
63 {
64 if(p != NULL){
65 print(p->lchild);
66 printf("%s %.4f\n",p->b,100.0*p->num/count);//注意這里*100.0
67 print(p->rchild);
68 }
69 }
70