好好做題,天天AC,又用了幾天時間,把 Volume 1的字符串給做完了,還是像以前一樣,把每一道題都回顧一下,以便自己的回顧和提高,同時也方便大家互相交流。。。。。
字符串的題都不算難,一般自己就可以看出做得對不對,下面是我做的那9道水題……
第一題:401 - Palindromes
大致題意:給你個字符串,判斷是不是鏡像和回文。
題目分析:回文不難,一個頭,一個尾,往中間掃就好了……鏡像的話,題目中有定義(什麼2和S,3和E啦……),我開了個數組來處理的,不知道有沒有更好的方法……歡迎指教
代碼: 1 #include <stdio.h> 2 #include <stdlib.h>
3 #include <string.h>
4 const int maxlen=50;
5 char a[maxlen],jingxiang[maxlen];
6 int lena;
7 bool ishuiwen ()
8 {
9 int i,j;
10 for (i=0,j=lena-1;i<j;i++,j--){
11 if (a[j]!=a[i]) return false;
12 }
13 return true;
14 }
15 bool isjingxiang ()
16 {
17 int i,j;
18 for (i=0,j=lena-1;i<=j;i++,j--){
19 if (a[i]<='9' && '1'<=a[i])
20 {
21 if (a[j] != jingxiang[a[i]-'1'+26])
22 { return false; }
23 }
24 else
25 {
26 if (a[j] != jingxiang[a[i]-'A'])
27 { return false; }
28 }
29 }
30 return true;
31 }
32 void csh ()
33 {
34 memset(jingxiang,0,sizeof(jingxiang));
35 jingxiang[0]='A';jingxiang[4]='3';jingxiang[7]='H';jingxiang[8]='I';
36 jingxiang[9]='L';jingxiang[11]='J';jingxiang[12]='M';jingxiang[14]='O';
37 jingxiang[18]='2';jingxiang[19]='T';jingxiang[20]='U';jingxiang[21]='V';
38 jingxiang[22]='W';jingxiang[23]='X';jingxiang[24]='Y';jingxiang[25]='5';
39 jingxiang[26]='1';jingxiang[27]='S';jingxiang[28]='E';jingxiang[30]='Z';jingxiang[33]='8';
40 }
41 int main()
42 {
43 int i;
44 while (gets(a)){
45 lena=strlen(a);
46 csh();
47 if (ishuiwen() && isjingxiang())
48 printf("%s -- is a mirrored palindrome.\n\n",a);
49 else if (ishuiwen())
50 printf("%s -- is a regular palindrome.\n\n",a);
51 else if (isjingxiang())
52 printf("%s -- is a mirrored string.\n\n",a);
53 else printf("%s -- is not a palindrome.\n\n",a);
54 }
55 return 0;
56 }心得體會:自己想出來用一個數組來做查詢表,不知道是不是好的方法,希望大家給點建議;還有,判斷是否鏡像時,中間那個也要判斷,我一開始中間那個沒判斷,WA了好幾次……
第二題:10010 - Where's Waldorf?
大致題意:在一個字符串矩陣裡找一個字符串,允許橫,豎,斜著查找……
題目分析:我編了8個字符串匹配函數……囧o(╯□╰)o,一個一個找出來的。。。。。。有沒有好方法啊???跪求……
代碼:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h> //不是格式問題?!!!!!
4 const int maxlen=100;
5 char a[maxlen][maxlen],b[maxlen];
6 int T,m,n,lenb;
7 bool f1 (int i,int j)
8 { int k=0;
9 if (n-j<lenb) return false;
10 for (;k<lenb;k++,j++){
11 if ( a[i][j] != b[k] ) return false;
12 }
13 return true;
14 }
15 bool f2 (int i,int j)
16 { int k=0,flage;
17 flage= (i+1)<(n-j) ? (i+1):(n-j);
18 if (flage<lenb) return false;
19 for (;k<lenb;i--,j++,k++){
20 if ( a[i][j] != b[k] ) return false;
21 }
22 return true;
23 }
24 bool f3 (int i,int j)
25 { int k=0;
26 if (i+1<lenb) return false;
27 for (;k<lenb;i--,k++){
28 if ( a[i][j] != b[k] ) return false;
29 }
30 return true;
31 }
32 bool f4 (int i,int j)
33 { int k=0,flage;
34 flage=(i+1)<(j+1) ? (i+1):(j+1);
35 if (flage<lenb) return false;
36 for (;k<lenb;i--,j--,k++){
37 if ( a[i][j] != b[k] ) return false;
38 }
39 return true;
40 }
41 bool f5 (int i,int j)
42 { int k=0;
43 if (j+1<lenb) return false;
44 for (;k<lenb;j--,k++){
45 if ( a[i][j] != b[k]) return false;
46 }
47 return true;
48 }
49 bool f6 (int i,int j)
50 { int k=0,flage;
51 flage=(m-i)<(j+1)?(m-i):(j+1);
52 if (flage<lenb) return false;
53 for (;k<lenb;i++,j--,k++){
54 if ( a[i][j] != b[k] ) return false;
55 }
56 return true;
57 }
58 bool f7 (int i,int j)
59 { int k=0;
60 if (m-i<lenb) return false;
61 for (;k<lenb;k++,i++){
62 if ( a[i][j] != b[k] ) return false;
63 }
64 return true;
65 }
66 bool f8 (int i,int j)
67 { int k=0,flage;
68 flage=(m-i)<(n-j)?(m-i):(n-j);
69 if (flage<lenb) return false;
70 for (;k<lenb;i++,j++,k++){
71 if ( a[i][j] != b[k] ) return false;
72 }
73 return true;
74 }
75 void bigtosmalljz ()
76 { int i,j;
77 for (i=0;i<m;i++){
78 for (j=0;j<n;j++){
79 if ('A'<=a[i][j] && a[i][j]<='Z')
80 { a[i][j]=a[i][j]-'A'+'a'; }
81 }
82 }
83 }
84 void bigtosmallmb()
85 { int i;
86 for (i=0;i<lenb;i++){
87 if ('A'<=b[i] && b[i]<='Z')
88 { b[i]=b[i]-'A'+'a'; }
89 }
90 }
91 void cl ()
92 { int i,j;
93 for (i=0;i<m;i++){
94 for (j=0;j<n;j++){
95 if (a[i][j] == b[0]){
96 if( f1(i,j) || f2(i,j) || f3(i,j) || f4(i,j) || f5(i,j) || f6(i,j) || f7(i,j) || f8(i,j) )
97 { printf("%d %d\n",i+1,j+1); return; }
98 }
99 }
100 }
101 }
102 int main()
103 { int i,j,k;
104 scanf("%d",&T);
105 for (i=0;i<T;i++){
106 scanf("%d %d",&m,&n);
107 getchar();
108 for (j=0;j<m;j++){
109 gets(a[j]);
110 }
111 bigtosmalljz();
112 scanf("%d",&k);
113 getchar();
114 for (j=0;j<k;j++){
115 gets(b);
116 lenb=strlen(b);
117 bigtosmallmb();
118 cl();
119 }
120 if (i<T-1)
121 { printf("\n"); }
122 }
123 return 0;
124 }
125 心得體會:代碼敲多了……不知道能不能簡化,還有,對於多組測試數據,中間要輸出一個換行,最後一個則不要(我經常吃這個虧)
第三題:10361 - Automatic Poetry
大致題意:把兩個<>裡的字符串互換即可……
題目分析:找“<”“>”,記錄下位置,處理就是了……
代碼:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include<string.h>
4 const int maxlen=120;
5 int p1,p2,p3,p4,p5;
6 char a[maxlen],s1[maxlen],s2[maxlen],s3[maxlen],s4[maxlen],b[maxlen];
7 void findp ()
8 { //找《》《》.在那///////////////////////////////////////
9 int i;
10 for (i=0;;i++){
11 if (a[i]=='<')
12 { p1=i; break; }
13 }
14 for (i=i+1;;i++){
15 if (a[i]=='>')
16 { p2=i; break; }
17 }
18 for(i=i+1;;i++){
19 if (a[i]=='<')
20 { p3=i; break; }
21 }
22 for(i=i+1;;i++){
23 if (a[i]=='>')
24 { p4=i; break; }
25 }
26 for (i=0;;i++){
27 if (b[i]=='.')
28 { p5=i; break; }
29 }
30 }
31 void getstr ()
32 { //得到四個字符創串
33 int i,j;
34 for (i=p1+1,j=0;i<p2;i++,j++){
35 s1[j]=a[i];
36 } s1[j]='\0';
37 for (i=p2+1,j=0;a[i]!=' ' && a[i]!='\0';i++,j++){
38 s2[j]=a[i];
39 } s2[j]='\0';
40 for (i=p3+1,j=0;i<p4;i++,j++){
41 s3[j]=a[i];
42 } s3[j]='\0';
43 for (i=p4+1,j=0;a[i]!='\0' && a[i]!=' ';j++,i++){
44 s4[j]=a[i];
45 } s4[j]='\0';
46 }
47 void zuheforb ()
48 { int i,j;
49 for (i=p3+1;i<p4;i++,p5++){
50 b[p5]=a[i];
51 }
52 for (i=p2+1;i<p3;i++,p5++){
53 b[p5]=a[i];
54 }
55 for (i=p1+1;i<p2;i++,p5++){
56 b[p5]=a[i];
57 }
58 for (i=p4+1;a[i]!='\0';i++,p5++){
59 b[p5]=a[i];
60 } b[p5]='\0';
61 }
62 void shuchua ()
63 { int i,j;
64 for (i=0;a[i]!='\0';i++){
65 if (a[i]!='<' && a[i]!='>')
66 { printf("%c",a[i]); }
67 } printf("\n");
68 }
69 int main()
70 {
71 int i,t;
72 scanf("%d",&t);
73 getchar();
74 for (i=0;i<t;i++){
75 gets(a);
76 gets(b);
77 findp();
78 getstr();
79 zuheforb();
80 shuchua();
81 puts(b);
82 }
83 ////////////////////////////////
84 //system("pause");
85 return 0;
86 }
87 心得體會:自己敲的代碼太丑了……~~~~(>_<)~~~~
第四題: 537 - Artificial Intelligence?
大致題意:知道P,I,U中的兩個,求另一個……
題目分析:關鍵是要找到P,I,U,以及讀取其中的值……我是通過“=”作為媒介的,讀數字時要注意小數點後的處理,還有要注意單位,m(豪,0.001),M(百萬,1000000),k(千,1000)
代碼:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 const int maxlen=99999;
5 char a[maxlen];
6 int p1,p2,lena,t,i;
7 double x=0,y=0,res;
8 char m,n;
9 void defuhao ()
10 { m=a[p1-1]; n=a[p2-1]; }
11 double deshuzi (int p)
12 {
13 int flag=0;
14 p++;
15 long double num=0,jinzhi=0.1;
16 while (1){
17 if ('0'<=a[p] && a[p]<='9')
18 { num=num*10+(a[p]-'0'); p++; }
19 else if (a[p] == '.')
20 { p++; flag=1; break; }
21 else break;
22 }
23 if (flag == 1){
24 while (1){
25 if ('0'<=a[p] && a[p]<='9')
26 { num=num+jinzhi*(a[p]-'0'); p++; jinzhi*=0.1; }
27 else break;
28 }
29 }
30 if (a[p]=='m' )
31 { num*=0.001; }
32 else if (a[p]=='M')
33 { num*=1000000; }
34 else if (a[p]=='k')
35 { num*=1000; }
36 return num;
37 }
38 void zhaodenghao ()
39 {
40 int i,count=0;
41 for (i=0;i<lena;i++){
42 if (a[i] == '='){
43 if (count == 0)
44 { p1=i; count++; }
45 else
46 { p2=i; break; }
47 }
48 }
49 }
50 void jisuan ()
51 {
52 if ((m=='I' && n=='U') || (m=='U' && n=='I'))
53 { res=x*y; printf("Problem #%d\nP=%.2lfW\n",i+1,res); }
54 else if ((m=='I' && n=='P'))
55 { res=y/x; printf("Problem #%d\nU=%.2lfV\n",i+1,res); }
56 else if ((m=='P' && n=='I'))
57 { res=x/y; printf("Problem #%d\nU=%.2lfV\n",i+1,res); }
58 else if ((m=='P' && n=='U'))
59 { res=x/y; printf("Problem #%d\nI=%.2lfA\n",i+1,res); }
60 else if ((m=='U' && n=='P'))
61 { res=y/x; printf("Problem #%d\nI=%.2lfA\n",i+1,res); }
62 }
63 int main()
64 {
65
66 scanf("%d",&t);
67 getchar();
68 for (i=0;i<t;i++){
69 gets(a);
70 lena=strlen(a);
71 zhaodenghao();
72 defuhao ();
73 x=deshuzi(p1); //x->m y->n; x,y是數字
74 y=deshuzi(p2);
75 // printf("%c=%lf,%c=%lf\n",m,x,n,y);
76 jisuan();
77 // if (t-i-1)
78 printf("\n");
79 }
80 // system("pause");
81 return 0;
82 }
83 心得體會:不知道有沒有一個自帶的字符串函數可以直接從字符串中讀整數和小數的。。。。求~~~~~~~~~~
第五題:409 - Excuses, Excuses!
大致題意:給你一些敏感詞,還有幾個句子,在那幾個句子中找敏感詞最多的句子……
題目分析:就是字符串匹配啦……還有重復也算,輸出時別忘了回車……
代碼:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 const int maxlen=100;
5 char keyword[25][maxlen],excus[25][maxlen],excus1[25][maxlen];
6 int count[25];
7 void bigtosmall (int i)
8 {
9 int j,len;
10 len=strlen(excus1[i]);
11 for (j=0;j<len;j++){
12 if ('A'<=excus1[i][j] && excus1[i][j]<='Z')
13 { excus[i][j]=excus1[i][j]-'A'+'a'; }
14 else excus[i][j]=excus1[i][j];
15 }
16 }
17 int pipei (int i,int j)
18 {
19 int p,t,q,leni,lenj,res=0;
20 leni=strlen(excus[i]);
21 lenj=strlen(keyword[j]);
22 for (p=0;p<=leni-lenj;p++){
23 t=p;
24 for (q=0;q<lenj;q++,t++){
25 if (excus[i][t] != keyword[j][q])
26 { break; }
27 }
28 if (q == lenj )
29 { //左右都不是字母!!!!!!! !!!!!!!!!!!!!!!!!!!!!啊!!!!!!!!!!!!!!!!!!!!!!!!!
30 if ((p == 0 || ('a'>=excus[i][p-1] || excus[i][p-1]>='z')) && ( excus[i][p+lenj]>='z' || excus[i][p+lenj]<='a') )
31 res++;
32 }//對於home 和homework的情況……
33 }
34 return res;
35
36 }
37 int main()
38 {
39 int m,n,i,j,max,jishu=1,res;
40 while (scanf("%d %d",&m,&n)!=EOF){
41 getchar();
42 max=0;
43 memset(count,0,sizeof(count));
44 for (i=0;i<m;i++){
45 gets(keyword[i]);
46 }
47 for(i=0;i<n;i++){
48 gets(excus1[i]);
49 bigtosmall(i);
50 }
51 for (i=0;i<n;i++){
52 for (j=0;j<m;j++){
53 res=pipei(i,j);
54 if (res)
55 { count[i]+=res; }
56 }
57 }
58 max=count[0];
59 for (i=0;i<n;i++){
60 if(max<count[i])
61 { max=count[i]; }
62 }
63 printf("Excuse Set #%d\n",jishu);
64 jishu++;
65 for (i=0;i<n;i++){
66 if (count[i] == max)
67 { printf("%s\n",excus1[i]); }
68 }
69 printf("\n");
70 }
71 //////////////////////////////
72
73 return 0;
74 }
75 心得體會:WA了好長時間,對於關鍵詞為home 而句子中有homework的情況沒做討論,導致錯誤……各種WA……
第六題:10878 - Decode the tape
大致題意:很簡單的解碼……空格代表零,“O”代表1,由二進制的ASC 2碼,再輸出字符就好了……
題目分析:掃一遍,輸出……我一次性就AC了……高興一下,O(∩_∩)O~呵呵……
代碼:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 const int maxlen=2000;
5 char a[15],b[maxlen];
6 bool isjieshu ()
7 {
8 int i;
9 for (i=0;i<10;i++){
10 if (a[i]!='_')
11 { return false; }
12 }
13 return true;
14 }
15 int erjingzhi ()
16 {
17 int i,jingzhi=1,n,sum=0;
18 for (i=9;i>0;i--){
19 if (a[i]=='.') continue;
20 if (a[i]=='o')
21 { sum=sum+jingzhi; }
22 jingzhi=jingzhi*2;
23 }
24 return sum;
25 }
26 int main()
27 {
28 int count1=2,count2=0;
29 while (gets(a)){
30 if (isjieshu())
31 { count1--; if (count1 == 0) {break;} continue; }
32 b[count2]=erjingzhi();
33 count2++;
34 }
35 printf("%s",b);
36 ///////////////////////////////
37 system("pause");
38 return 0;
39 }
40 心得體會:注意觀察就是了
第七題:10815 - Andy's First Dictionary
大致題意:給一些句子,從中分割出單詞,再按字典序排列……
題目分析:排序費了點腦筋,一開始不會的,後來發覺特白癡,再說C都有現成的函數供調用了……對了,還要去重復單詞……還要說的一點就是UVa OJ尼瑪坑爹啊!!!明明說了not exceed 5000,結果我開到2萬都不夠大,告訴我說RE,我靠,你妹的!!!!擦哦……
代碼:
1 //這題也太黑了吧……我開那麼大才過!!!
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5 const int maxhan=5500;
6 const int maxlie=2500;
7 const int maxnum=31000; //5500不夠!!!21000都不夠!!!!
8 char a[maxhan][maxlie];
9 char wordlist[maxnum][900];
10 int countjuzi,countdanci=0;
11 void chuli ()
12 {
13 int i,j,leni;
14 for (i=0;i<countjuzi;i++){//對每個句子而言
15 leni=strlen(a[i]);
16 for (j=0;j<leni;j++){//對於句子中的每個字符
17 if (a[i][j]<'a' || a[i][j]>'z')
18 { a[i][j]=' '; }
19 }
20 }
21 }
22 void fenge ()
23 {
24 int i,j;
25 char *p;
26 for (i=0;i<countjuzi;i++){ //對每個句子
27 p=strtok(a[i]," ");
28 while (p != NULL){
29 strcpy (wordlist[countdanci],p);
30 countdanci++;
31 p=strtok(NULL," ");
32 }
33 }
34 }
35 void shuchu ()
36 {
37 int i,j;
38 for (i=0;i<countdanci;i++){
39 if (wordlist[i][0] != '\0')
40 { puts(wordlist[i]); }
41 }
42 }
43 void strsmall (char a[])
44 {
45 int i,len;
46 len=strlen(a);
47 for (i=0;i<len;i++){
48 if ('A'<=a[i] && a[i]<='Z')
49 { a[i]=a[i]-'A'+'a'; }
50 }
51 }
52 void paixu (int s,int e)
53 {
54 char x[maxlie];
55 strcpy(x,wordlist[s]);
56 int l=s,r=e;
57 if (l>=r) return;
58 while (l<r){
59 while (l<r && strcmp(wordlist[r],x)>=0) r--;
60 strcpy(wordlist[l],wordlist[r]);
61 while (l<r && strcmp(wordlist[l],x)<=0) l++;
62 strcpy(wordlist[r],wordlist[l]);
63 }
64 strcpy(wordlist[r],x);
65 paixu(s,r-1);
66 paixu(r+1,e);
67 }
68 void qucf ()
69 {
70 int i,j;
71 for (i=0;i<countdanci;i++){
72 if (wordlist[i][0]!='\0'){
73 for (j=i+1;j<countdanci;j++){
74 if (strcmp(wordlist[i],wordlist[j]) == 0)
75 { wordlist[j][0]='\0'; }
76 }
77 }
78 }
79 }
80 int main()
81 {
82 int i=0;//countjuzi多少個句子
83 while (gets(a[i])){
84 strsmall(a[i]);//變小寫
85 i++;
86 }
87 countjuzi=i;
88 chuli ();
89 fenge ();
90 paixu (0,countdanci-1);
91 qucf ();
92 shuchu ();
93 system("pause");
94 return 0;
95 }
96 心得體會:學會了字符串排序,一開始看到5000,想用冒泡混過去的……結果TLE後來發現數據量高達2,3萬……尼瑪啊……上塊排啊……有木有。。。
第八題:644 - Immediate Decodability
大致題意:就是看有沒有字符串是其他字符串的前綴……(我想到了哈夫曼樹?最優樹?不知道……)
題目分析:反正數據量不到10個,一個一個暴力比較就是了……
代碼:
1 //史上最丑代碼!!!!!!!!!!
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5 const int maxlen=12;
6 char a[maxlen][maxlen];
7 int main()
8 {
9 int count=0,i,j,lenmin,flag=0,leni,lenj,count1=0;
10 while (gets(a[0])){
11 flag=0;
12 for (count=1;;count++){
13 gets(a[count]);
14 if (a[count][0] == '9' && a[count][1] == '\0')
15 { count1++; break; }
16 }
17 for (i=0;i<count-1;i++){
18 leni=strlen(a[i]);
19 for (j=i+1;j<count;j++){
20 lenj=strlen(a[j]);
21 lenmin= leni > lenj ? lenj : leni;
22 if (strncmp (a[i],a[j],lenmin) == 0)
23 { flag=1; printf("Set %d is not immediately decodable\n",count1); break; }
24 }
25 if (flag) break;
26 }
27 if (!flag) printf("Set %d is immediately decodable\n",count1);
28 }
29 return 0;
30 }
31 心得體會:代碼很丑,沒用結構化,模塊化編程……還有一個小插曲……我已開始immediately打錯了,老是WA,糾結了半天才發現的。。。
第九題:10115 - Automatic Editing
大致題意:給你幾個字符串替換規則,再給你個字符串,要你按規則從第一個到最後一個,對目標字符串進行替換,最後輸出結果……
題目分析:主要是編字符串匹配函數和字符串插入函數……
代碼:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 char before[15][100],after[15][100],juzi[300];
5 int i,lenjuzi,lenafter,lenbefore,where;
6 /////////////////////////////////////////////////////////////////////
7 int pipei ()
8 { int j,k,l,flag;
9 lenjuzi=strlen(juzi);
10 lenbefore=strlen(before[i]);
11 lenafter=strlen(after[i]);
12 //求長度要放到裡面來,因為改變後,長度也變了……
13 for (j=0;j<=lenjuzi-lenbefore;j++){
14 l=j; flag=1;
15 for (k=0;k<lenbefore;k++,l++){
16 if ( juzi[l]!=before[i][k] )
17 { flag=0; break; }
18 }
19 if (flag) { return j;}
20 }
21 return -1;
22 }
23 void strins ()
24 { int s,e,j,k;
25 if(lenafter>lenbefore)
26 { s=lenjuzi+1; e=lenjuzi+lenafter-lenbefore+1;//加一啥意思啊???
27 for (;s>=where+lenbefore;s--,e--){
28 juzi[e]=juzi[s];
29 }
30 }
31 else
32 { s=where+lenafter; e=where+lenbefore;
33 for (;e<=lenjuzi;s++,e++){
34 juzi[s]=juzi[e];
35 }
36 }
37 for (j=0;j<lenafter;j++,where++){
38 juzi[where]=after[i][j];
39 }
40 }
41 ///////////////////////////////////////////////////////////////////
42 int main()
43 { int t;
44
45 while (1){
46 scanf("%d",&t);
47 getchar ();
48 if (!t) break;
49 for (i=0;i<t;i++){
50 gets(before[i]);
51 gets(after[i]);
52 }
53 gets(juzi);
54 for (i=0;i<t;i++){
55
56 while ( (where=pipei())>-1 ){
57 // printf("pipeizai %d,%d\n",where,i);
58 strins();
59 continue;
60 }
61 }
62 puts(juzi);
63 }
64 //////////////////////////////////
65 // system("pause");
66 return 0;
67 }
68 心得體會:注意debug,自己試幾組測試數據……
最後:幾道題都不難……卻耗費了我好幾天,以後要加快進度提高自己了,不然老是拖隊友的後腿!!!
作者“菜鳥的AC之路”