最后一题不会 没看懂题目 就一直没写 ， 其他的基本都会了
习题 3- 1 得分 uva1585
题意 输入一个 O 和 X 的串，每个O的分数为连续出现的O个数，X不算分
例 OOXXOXXOOO 得分 1+2+0+0+1+0+0+1+2+3=10
设个标志位就好了
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> int main(){ int t; char ss[89];scanf("%d",&t); while(t--){ scanf("%s",ss); int len = strlen(ss); int sum =0, cnt =0,flag=1; for(int i=0 ; i < len ; i++) { if( ss[i] == 'O') { if(!flag) cnt =0; flag =1 ;cnt++; sum += cnt; // printf("i=%d cnt=%d sum=%d\n",i,cnt,sum ); } else flag =0; }printf("%d\n", sum); }return 0; }
习题3-2 分子量 uva1586
计算 分子式的相对分子质量 C，H，O，N， 12.01 ，1.008，16.00，14.01
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> int main(){ char s[1000];int t; scanf("%d",&t); while(t--){ getchar();scanf("%s",s);int len = strlen(s); double sum = 0, qua = 0;int m =0,n=0; for(int i =0 ; i < len ; i++) { if(s[i] == 'C')qua = 12.01; if(s[i] == 'H')qua = 1.008; if(s[i] == 'O')qua = 16.00; if(s[i] == 'N')qua = 14.01; if( isdigit(s[i]) ) { if( m > 0 )m = m*10+ s[i]-'0'; else m= s[i]-'0'; n = 1; } if( i == len-1 || isalpha(s[i+1]) ) { if(n == 0)m=1; sum += qua*m; m = 0;n=0; //printf("xxxx i=%d m= %d qua*m=%lf sum= %lf\n",i, m,qua*m,sum); } } if(len == 1)sum = qua; printf("%.3lf\n", sum); }return 0; }/* Sample Input 4 C C6H5OH NH2CH2COOH C12H22O11 Sample Output 12.010 94.108 75.070 342.296 */
习题3-3 数数字 uva1225
输入n， 计算123.....n,中 0~9 的出现次数
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> int main(){ int n ,t,a[11];char ch,s[10000+5]; scanf("%d",&t); while( t--){ scanf("%d",&n); for(int i=0; i < 11;i++)a[i] = 0; int len = strlen(s); for(int i =1 ; i <= n ; i++) { int x= i,y= i; while( x > 0){y= x%10;x/=10;a[y]++;} } for(int i = 0 ;i < 10; i++){ if(i < 9)printf("%d ", a[i]); else printf("%d\n",a[i]); } } return 0; }
习题3-4 周期串 uva455
输入一个字符串 ， 输出其最小周期
#include <iostream>//PE #include <cstring> #include <cstdio> #include <cmath> int main() { //freopen("uva455output.txt","w",stdout); int n,t,a[11];char ch,s[100]; scanf("%d",&t);while(t--) { getchar();scanf("%s",s);int j,i; int len = strlen(s);int flag = 1; for( j = 1; j <= len ;j++) { if( len%j == 0) { flag = 1; for( i = j ; i < len ; i++) { if( s[i] != s[i%j] ) { flag = 0;break; } } if( flag ) break; } }printf("%d\n",flag?j:len );if(t) printf("\n"); //if(t >= 1)printf("\n\n"); }return 0; }
习题3-5 谜题 uva227
一个5*5的网格 ，有一个为空，输入指令ABLR 上下左右 表示将空格移动的方向
输出 最后网格 ， 这里当输入指令时，可以用个定义两个string的字符串，判断字符串结尾是否是0， 否的话 直接用 += 接在备用字符串后就好
，enmmmmmmmmmm 很舒服
/* Sample Input TRGSJ XDOKI M VLN WPABE UQHCF ARRBBL0 ABCDE FGHIJ KLMNO PQRS TUVWX AAA LLLL0 ABCDE FGHIJ KLMNO PQRS TUVWX AAAAABBRRRLL0 Z Sample Output Puzzle #1: T R G S J X O K L I M D V B N W P A E U Q H C F Puzzle #2: A B C D F G H I E K L M N J P Q R S O T U V W X Puzzle #3: This puzzle has no final configuration. */ #include<iostream> #include<cstring> #include<string> #include<cstdio> using namespace std; char puzzle[10][10]; int r0,c0;//记录空格的位置 void read(int row, string str) { for(int j=0;j<5;j++){ puzzle[row][j] = str[j]; if(str[j]==' ') { r0 = row; c0 = j;} } } bool move_p(char turn) { int t;int x = r0,y = c0; if(turn == 'A') x--; else if(turn == 'B') x++; else if(turn == 'L') y--; else if(turn == 'R') y++; if(x>=0 && x<=4 && y>=0 && y<=4){ puzzle[r0][c0] = puzzle[x][y]; puzzle[x][y] = ' '; r0 = x; c0 =y; }else return false; return true; } int main() { //freopen("227.txt","r",stdin); string str,order; int icase = 0; while(1) { if(icase!=0) cin.get(); getline(cin,str); if(str[0]=='Z') break; if(icase!=0) cout<<endl;//不同样例之间换行 read(0,str); for(int i = 1; i < 5; i++) {getline(cin,str);read(i,str);} int ok,len; order.clear(); while(1) { string temp; cin>>temp; order += temp; len = temp.length(); if(temp[len-1]=='0') break; else continue; } ok = 1;len = order.length(); for(int i = 0; i < len-1; i++) if(move_p(order[i])) continue; else { ok = 0; break;} cout<<"Puzzle #"<<++icase<<":"<<endl; if(ok) { int i,j; for(i = 0; i < 5; i++){ for(j = 0; j < 4; j++) cout<<puzzle[i][j]<<" "; cout<<puzzle[i][j]<<endl; } }else cout<<"This puzzle has no final configuration."<<endl; } return 0; }
习题3-6 纵横字谜的答案 uva232
输入一个 r 行 c列的网格 ，黑格为 * ，将所有横向单词按编号 输出 ，再按顺序将所有竖向单词按顺序输出
顺序 竖的我还是不太懂 （雾）
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef struct _node { int id; char str[12]; }node; node data[101]; char maps[12][12]; int size[12][12]; int cmp(node a, node b) { return a.id < b.id; } int main() { int row,column,times = 1; while (cin >> row && row) { cin >> column; for (int i = 0; i < row; ++ i) cin >> maps[i]; int id = 1; for (int i = 0; i < row; ++ i) for (int j = 0; j < column; ++ j) if (maps[i][j] != '*' && (!i || !j || maps[i-1][j] == '*' || maps[i][j-1] == '*')) size[i][j] = id ++; else size[i][j] = 0; if (times > 1) printf("\n"); printf("puzzle #%d:\n",times ++); printf("Across\n"); for (int i = 0; i < row; ++ i) { int move = 0; while (move < column) { if (size[i][move]) { printf("%3d.",size[i][move]); int save = 0; while (move < column && maps[i][move] != '*') printf("%c",maps[i][move ++]); printf("\n"); }else move ++; } } printf("Down\n"); int count = 0; for (int i = 0; i < column; ++ i) { int move = 0; while (move < row) { if (size[move][i]) { data[count].id = size[move][i]; int save = 0; while (move < row && maps[move][i] != '*') data[count].str[save ++] = maps[move ++][i]; data[count ++].str[save ++] = 0; }else move ++; } } sort(data, data+count, cmp); for (int i = 0; i < count; ++ i) printf("%3d.%s\n",data[i].id, data[i].str); } return 0; }
习题3-7 DNA序列 uva1368
输入几行相同长度的DNA序列 ， 按每列出现次数最多的输出 ，如有多解 输出字典序最小的
#include<algorithm> #include <iostream> #include <sstream> #include <cstdlib> #include <cstring> #include <cstdio> #include <vector> #include <ctime> #include <set> #include <map> using namespace std; int pd[100]; char dna[75][1005],ss[]="ACGT",s[1005]; int main(){ int n,m,t,q;scanf("%d",&t); while(t--){memset(s,0,sizeof(s)); scanf("%d%d",&n,&m);int sum = 0; for(int i = 1; i <= n; i++)scanf("%s",dna[i]); for(int j = 0; j < m; j++) { memset(pd,0,sizeof(pd)); for(int i = 1; i <= n; i++)pd[dna[i][j]]++; int max = 0,x; for(int k = 0; k < 4; k++) if(pd[ss[k]] > max) max = pd[ss[k]],s[j] = ss[k]; sum += max; }puts(s); printf("%d\n",n*m-sum); }return 0; }
习题3-8 循环小数 uva202
输入 a b， 输出 a/b 的循环小数表示以及循环节长度
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> //#include <algorithm> using namespace std; const int maxn = 3003; int n,m,count,r[maxn],s[maxn],u[maxn]; int main() { while(scanf("%d%d",&n,&m) == 2 && m) { count = 0; memset(r,0,sizeof(r)); memset(u,0,sizeof(u)); r[count++] = n/m; printf("%d/%d = %d.", n, m, r[0]); n %= m; while( n && !u[n]) { u[n] = count;// r商，s余，u判断余数是否出现过 s[count] = n; r[count ++] = 10*n/m; n = n*10%m; } for (int i = 1; i < count && i <= 50; i++) { if (n && s[i] == n) printf("("); printf("%d", r[i]); } if (!n) printf("(0"); if (count > 50) printf("..."); printf(")\n"); printf(" %d = number of digits in repeating cycle\n\n",n?count-u[n]:1); } return 0; } /* 计算分数的循环节。 分析：数论，组合。 n除以m的余数只能是0~m-1，根据抽屉原则，当计算m+1次时至少存在一个余数相同， 即为循环节；存储余数和除数，输出即可。 Sample Input 76 25 5 43 1 397 Sample Output 76/25 = 3.04(0) 1 = number of digits in repeating cycle 5/43 = 0.(116279069767441860465) 21 = number of digits in repeating cycle 1/397 = 0.(00251889168765743073047858942065491183879093198992...) 99 = number of digits in repeating cycle */
习题3-9 子序列 uva10340
输入字符串s 和 t ，如果t 中删除字符后能得到 s ，输出Yes ，否则 No
//两个字符串 输入s 和 t ，判断是否可以删除若干字符从t得到 s /* Sample Input sequence subsequence person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter Sample Output Yes No Yes No */ #include<cstdio> #include<cstdlib> #include<cctype> #include<cstring> //char s[1010000000000],t[1010000000000];10^12 int main(){ char s[1010000000], t[1010000000];//10^9 while(scanf("%s%s", s , t) != EOF){ int len1 = strlen(s);//for(int i = 0; i < len1; i++)s[i] = tolower(s[i]); int len2 = strlen(t);//for(int i = 0; i < len2; i++)t[i] = tolower(t[i]); //printf("s=%s t=%s\n",s, t); int cnt= 0;int j = 0; for( int i = 0; i < len2; i++) { if( t[i] == s[j]) { cnt++,j++; if( cnt == len1)break; } } if(cnt >= len1 )printf("Yes\n"); else printf("No\n"); } return 0; }
习题3-10 盒子 uva1587
输入6 个矩形的长和宽， 能否组成 长方体
/*//输入六个矩形的长与宽 问是否可以组成长方体 #include<cstdio> #include<cstdlib> #include<cctype> #include<cstring> #include<iostream> using namespace std; const int maxn = 1e6+2; int a[maxn],b[maxn],k,d;; int main(){ while(scanf("%d%d",&k,&d)!=EOF){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); if(k < d)swap(k,d); a[k]++;b[d]++; for( int i = 1; i < 6; i++) { scanf("%d%d",&k,&d);if(k < d)swap(k,d);a[k]++;b[d]++; } int n = 0,flag = 0,aa=0,bb=0,cnt=0; for(int i = 0; i < 10002; i++) { if(a[i]/6 == 1 && b[i]/6 == 1){printf("POSSIBLE\n");break;} if((a[i] > 0 && a[i]%2 != 0)||(b[i] > 0 && b[i]%2 != 0)) {printf("IMPOSSIBLE\n");break;} if((a[i]/6 == 1 && b[i]/2 == 1 )||(a[i]/2 == 1 && b[i]/6 == 1)){aa = 2;} if(a[i]%4 == 0 || b[i]%4 == 0){bb = 1;cnt++;} if(aa == 2 && bb == 1){printf("POSSIBLE\n");break;} if(a[i]/2 == 1 && b[i]/2 == 1){n = 1;} if(n == 1 && cnt == 2){printf("POSSIBLE\n");break;} } printf("n= %d flag = %d\n", n , flag); } return 0; } Sample Input 1345 2584 2584 683 2584 1345 683 1345 683 1345 2584 683 1234 4567 1234 4567 4567 4321 4322 4567 4321 1234 4321 1234 Sample Output POSSIBLE IMPOSSIBLE */ #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; struct NODE { int h, w; bool operator < (const NODE& rha) const{ if(h == rha.h) return w < rha.w; return h < rha.h; } }a[10]; bool ok() { /* if(a[0].h != a[1].h || a[0].w != a[1].w) return false; if(a[2].h != a[3].h || a[2].w != a[3].w) return false; if(a[4].h != a[5].h || a[4].w != a[5].w) return false; if(a[1].h != a[2].h) return false; if(a[1].w != a[4].h) return false; if(a[3].w != a[4].w) return false; */ if(a[0].h != a[3].h || a[2].w != a[3].w) return false; if(a[1].w != a[5].h || a[4].h != a[5].h) return false; if(a[2].w != a[5].w || a[4].w != a[5].w) return false; return true; } int main() { while(scanf("%d%d", &a[0].h, &a[0].w) != EOF) { if(a[0].h > a[0].w) swap(a[0].h, a[0].w); for(int i = 1; i < 6; ++i) { scanf("%d%d", &a[i].h, &a[i].w); if(a[i].h > a[i].w) swap(a[i].h, a[i].w); } sort(a, a+6); /* for(int i = 0; i < 6; ++i) { printf(" a[%d] = %d %d", i,a[i].h, a[i].w); }printf("\n");*/ if(ok()) puts("POSSIBLE"); else puts("IMPOSSIBLE"); } return 0; }
习题3-11 换地档装置 uva1588
输入两个1 2 组成的串， 计算可重叠的部分（加起来小于4） 两者长度相加减去可重叠的即可
#include<iostream> #include <cstring> #include <cstdio> int n,ma,len1,len2; char s1[100005],s2[1000005]; int repr(char s1[],char s2[]){ int flag = 0,fff = 0,cnt; int len1 = strlen(s1); int len2 = strlen(s2); for(int i = 0; i < len1; i++) { flag = 0;cnt = 0; if(fff) break; for(int j = 0; j < len2, i+j < len1; j++) { int t = s1[i+j]+s2[j] - 2*'0'; if(t > 3) {flag = 1; cnt = 0;break;} cnt++; if(j == len2-1 && !flag){fff = 1;break;} if(i+j == len1-1 && cnt > ma )ma = cnt; } } if(fff)ma = len2; return ma; } int main(){ while(scanf("%s%s",s1,s2) == 2){ ma = 0; int xx = strlen(s1)+strlen(s2); int xxx = std::max(repr(s1,s2),repr(s2,s1)); //printf("xx=%d xxx= %d\n",xx, xxx); xxx = xx-xxx; //freopen("uva1588r.txt","r",stdin); //freopen("uva1588.txt","w",stdout); //printf("flag = %d fff = %d\n", flag , fff); printf("%d\n", xxx); } return 0; } /* Sample Input 2112112112 2212112 12121212 21212121 2211221122 21212 Sample Output 10 8 15 */
习题3-12 浮点数 uva1809
enmmmmmmmmm 还是不会， 会了再补
// enmmmmmmmmmmm 不会