紫书第三章习题

p57

习题3-1 uva1585

题解:水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;string s;
cin>>n;
while(n--){
cin>>s;
int len=s.length(),ans=0,cnt=0;
for(int i=0;i<len;i++){
if(s[i]=='O') ans+=(++cnt);
else cnt=0;
}
cout<<ans<<endl;
}
}

习题3-2 uva1586

题解:主要是计算CHON各元素的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int c,h,o,n;
int main()
{
cout<<setprecision(3)<<fixed;//保留三位小数
int t;cin>>t;
while(t--){
string s;double sum=0;int c=0,h=0,o=0,n=0;
cin>>s;
int len=s.length();
int temp=0,index=0;
for(int i=0;i<len;i+=temp){
temp=0;index=0;
while(isdigit(s[i+1+temp]))
temp++;
for(int j=i+1;j<=i+temp;j++){
index+=((s[j]-'0')*pow(10,temp-(j-i)));
}
switch(s[i]){
case 'C': c+=(isdigit(s[i+1])?index:1);break;
case 'H': h+=(isdigit(s[i+1])?index:1);break;
case 'O': o+=(isdigit(s[i+1])?index:1);break;
case 'N': n+=(isdigit(s[i+1])?index:1);break;
default: continue;
}
temp++;
}
sum=(c*12.01+h*1.008+o*16.00+n*14.01);
cout<<sum<<endl;
}
}

习题3-3 uva1225

题解:没多想,直接暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int cnt[15];
void ergodic(int a){
while(a>0){
cnt[a%10]++;
a/=10;
}
}
int main()
{
int t,n; cin>>t;
while(t--){
memset(cnt,0,sizeof cnt);
cin>>n;
for(int i=1;i<=n;i++) ergodic(i);
for(int i=0;i<10;i++) {
if(i) cout<<" ";cout<<cnt[i];
}
cout<<endl;
}
return 0;
}

习题3-4 uva455

题解:这道题也是直接暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
string s;
int main() {
int t;
cin>>t;
while(t--) {
cin>>s;
int len=s.length();
for(int k,i=1; i<=len; i++) {
if(len%i) continue;
for(k=i; k<len; k++) {
if(s[k]!=s[k%i]) break;
}
if(k==len) {
cout<<i<<endl; break;
}

}
if(t) cout<<endl;
}
}

习题3-5 uva227

题解:这题主要是格式处理比较麻烦,剩下的就是模拟了,注意是否越界产生非法命令就ok了,
用的getchar()和putchar()函数,第一份代码是我的思路,第二份代码是题解书上的方法
第一份

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
int x,y,cnt=0,flag=0,c;
char mp[9][9];
char s[100];
void print() {
printf("Puzzle #%d:\n",++cnt);
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
putchar(mp[i][j]);
if(j<4) putchar(' ');
}
putchar('\n');
}
}
void printerror() {
printf("Puzzle #%d:\nThis puzzle has no final configuration.\n",++cnt);
}
void init() {
flag=0;
ungetc(c,stdin);//将字符退回到输入流,赋值给下一个读取文件流的函数得到
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
mp[i][j]=getchar();
if(mp[i][j]==' ') {x=j;y=i;}
}
getchar();//别忘了
}
}
void swapp() {
while((c=getchar())!='0') {
if(c=='A') {
if(y==0) {flag=1;break;
} else swap(mp[y][x],mp[y-1][x]); y--;
} else if(c=='B') {
if(y==4) {flag=1;break;
} else swap(mp[y][x],mp[y+1][x]); y++;
} else if(c=='L') {
if(x==0) {flag=1;break;
} else swap(mp[y][x],mp[y][x-1]); x--;
} else if(c=='R') {
if(x==4) {flag=1;break;
} else swap(mp[y][x],mp[y][x+1]); x++;
}
}
if(flag) {
while((c=getchar())!='0');//即使越界了也要将命令接收完
}
getchar();
}
int main() {
while((c=getchar())&&(c!='Z')) {
init();
swapp();
if(cnt>0) putchar('\n');
if(flag) printerror();
else print();
}
}

第二份

1
2


习题3-6 uva232

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int maxn=15;
char mp[maxn][maxn];
int flag[maxn][maxn],vis[maxn][maxn],r,c,ct,cnt=0;
int main() {
while(scanf("%d",&r)==1&&r) {
ct=0;
memset(flag,0,sizeof flag);
scanf("%d",&c);
for(int i=0; i<r; i++) scanf("%s",&mp[i]);
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++)
if(mp[i][j]!='*'&&(i==0||j==0||mp[i][j-1]=='*'||mp[i-1][j]=='*')) flag[i][j]=(++ct);
}
if(cnt) puts("");
printf("puzzle #%d:\nAcross\n",++cnt);
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(flag[i][j]!=0) {
printf("%3d.",flag[i][j]);
while(mp[i][j]!='*'&&j<c) {
putchar(mp[i][j++]);
}
puts("");
}
}
}
printf("Down\n");
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(flag[i][j]!=0) {
int temp=i;
printf("%3d.",flag[temp][j]);
while(mp[temp][j]!='*'&&temp<r) {
flag[temp][j]=0;
putchar(mp[temp++][j]);
}
puts("");
}
}
}

}
return 0;
}

习题3-7 uva1368

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
char mp[55][1010];
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++) scanf("%s",&mp[i]);
int ans=0;
string s="ACGT";
for(int j=0; j<m; j++)
{
int a[4];
memset(a,0,sizeof a);
for(int i=0; i<n; i++)
{
if(mp[i][j]=='A') a[0]++;
if(mp[i][j]=='C') a[1]++;
if(mp[i][j]=='G') a[2]++;
if(mp[i][j]=='T') a[3]++;
}
int Max=0,index;
for(int i=0; i<4; i++)
if(a[i]>Max) Max=a[i],index=i;
cout<<s[index];
sort(a,a+4);
ans+=(a[0]+a[1]+a[2]);

}
cout<<endl<<ans<<endl;
}
return 0;
}

习题3-8 uva202

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
抽屉原理
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+10;
int vis[maxn];//标记
int merchant[maxn];//商
int Remainder[maxn];//余数
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)==2){
memset(vis,0,sizeof vis);
int cnt=0,temp=a;
merchant[cnt++]=a/b;
a%=b;
while(!vis[a]){
vis[a]=cnt;
Remainder[cnt]=a;
merchant[cnt++]=10*a/b;
a=(10*a%b);
}
printf("%d/%d = %d.",temp,b,merchant[0]);
for(int i=1;i<cnt&&i<=50;i++){
if(Remainder[i]==a)
printf("(");
printf("%d",merchant[i]);
}
if(cnt>50) printf("...");
printf(")\n");
printf(" %d = number of digits in repeating cycle\n\n",cnt-vis[a]);
}
return 0;
}

习题3-9 uva10340

题解:水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s,t;
while(cin>>s>>t){
int lens=s.length(),lent=t.length(),flag=1;
for(int j=0,i=0;i<lent;i++){
if(s[j]==t[i]) {j++;}
if(i==lent-1&&j!=lens) flag=0;
if(j==lens) break;
}
cout<<((flag)?"Yes\n":"No\n");
}
return 0;
}

习题3-10 uva1587

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
struct edge {
int x,y;
} a[6];
bool cmp(edge a,edge b) {
return a.x==b.x ? (a.y > b.y) : (a.x > b.x);
}
int main() {
int w,h;
while(scanf("%d%d",&w,&h)==2) {
if(w<h) swap(w,h);
a[0].x=w;
a[0].y=h;
int flag=1;
for(int i=1; i<6; i++) {
scanf("%d%d",&w,&h);
if(w<h) swap(w,h);
a[i].x=w;
a[i].y=h;
}
sort(a,a+6,cmp);
for(int i=0; i<6; i+=2) {
if((a[i].x!=a[i+1].x)||(a[i].y!=a[i+1].y)) {
flag=0;
break;
}
}
if(a[0].x!=a[2].x || a[0].y!= a[4].x || a[2].y!=a[4].y) flag=0;
if(flag) printf("POSSIBLE\n");
else printf("IMPOSSIBLE\n");
}
return 0;
}

习题3-11 uva1588

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
我天,这个题用一个循环居然差点绕晕
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
char s1[110],s2[110];
while(scanf("%s%s",&s1,&s2)==2){
int len1=strlen(s1),len2=strlen(s2);
int ans=len1+len2;
for(int i=-len2;i<len1;i++){//遍历第二个开始的起点
int ok=1;
for(int j=0;j<len1&&ok;j++){//固定第一个
if(i<=j&&i+len2>=j){
ok=((s1[j]-'0'+s2[j-i]-'0')<=3);
}
}
if(ok) ans=min(ans,max(len1,i+len2)-min(i,0));
}
printf("%d\n",ans);
}
return 0;
}

习题3-12 uva11809

题解:数学题(浮点数)
先根据浮点数原理写出最大值v关于尾数M和阶数E的关系式,两边同时取log10化简
v=(1-1/2^(M+1))2^(2^E-1)=A10^B
lgv=lg(2^(M+1)-1)-(M+1)lg2+(2^E-1)lg2=lgA+B
遍历所有可能的M,根据上面的公式求出E,然后再用E和M求出lgv与输入的值比较,如果两数之差≤1e-6则输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
const double EPS=1e-6;
using namespace std;
int main() {
char line[100];
double A,B,lg2=log10(2);
while(scanf("%s",&line)==1&&strcmp(line,"0e0")) {
*strchr(line,'e')=' ';//将line数组中的第一个'e'替换成' '
sscanf(line,"%lf%lf",&A,&B);//sscanf函数
double v=log10(A)+B;
for(int M=1; M<=10; M++) {
int E=round(log10((v+M*lg2-log10(pow(2,M)-1))/lg2+1)/lg2);
if(fabs(((1<<E)-1)*lg2+log10(pow(2,M)-1)-M*lg2-v)<=EPS) {
printf("%d %d\n",M-1,E);
}
}
}
return 0;
}

到此把紫书第三章的习题做完了,还是有收获的,虽然花了很长时间,课比较多,所以都是晚上肝出来的。。