紫书习题 第三章

发表于 | 分类于 |
字数统计: 3,156 字

我自己做的紫书第三章部分习题的整合。

例3-1 TEX Quotes

题目链接

简单模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
void init(){
    
}
void solve(){
    char c;
    int flag=0;
    while((c=getchar())!=EOF){
        if(c!='"')putchar(c);
        else{
            if(flag)putchar('\''),putchar('\''),flag=0;
            else putchar('`'),putchar('`'),flag=1;
        }
    }
}
int main(){、
    init();
    solve();
    return 0;
}

例3-2 UVa10082 WERTYU

题目链接

模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
char s[]="`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./'";
void init(){
    
}
void solve(){
    char c;
    while((c=getchar())!=EOF){
        int ind;
        if(isspace(c))putchar(c);
        else{
            for(ind=0;s[ind]!=c;ind++);
            putchar(s[ind-1]);
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}

例3-3 UVa401 Palindromes

题目链接

常量数组技巧！

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
char rev_al[]="A   3  HIL JM O   2TUVWXY5",rev_num[]="1SE Z  8 ";
char ask(char c){
    if(isalpha(c))return rev_al[c-'A'];
    if(isdigit(c))return rev_num[c-'1'];
}
void init(){
    
}
void solve(){
    char s[30];
    while(scanf("%s",s)==1){
        int len=strlen(s),f1=1,f2=1;
        for(int i=0;i<(len+1)/2;i++)
            if(s[i]!=s[len-i-1]){f1=0;break;}
        for(int i=0;i<(len+1)/2;i++)
            if(s[len-i-1]!=ask(s[i])){f2=0;break;}
        if(f1&&f2)printf("%s -- is a mirrored palindrome.\n",s);
        if((!f1)&&f2)printf("%s -- is a mirrored string.\n",s);
        if(f1&&(!f2))printf("%s -- is a regular palindrome.\n",s);
        if((!f1)&&(!f2))printf("%s -- is not a palindrome.\n",s);
        putchar('\n');
    }
}
int main(){
    init();
    solve();
    return 0;
}

例3-4 UVa340 Master-Mind Hints

题目链接

模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int n,numa[1005],numb[1005],co[10],ca[10],cb[10];
void init(){
    memset(co,0,sizeof(co));
    for(int i=0;i<n;i++)
        numa[i]=read(),co[numa[i]]++;
}
void solve(){
    for(;;){
        memset(cb,0,sizeof(cb));
        memcpy(ca,co,sizeof(co));
        int ans1=0,ans2=0;
        for(int i=0;i<n;i++){
            numb[i]=read(),cb[numb[i]]++;
            if(numa[i]==numb[i])ans1++,ca[numa[i]]--,cb[numb[i]]--;
        }
        if(!numb[0])break;
        for(int i=1;i<=9;i++)
            ans2+=min(ca[i],cb[i]);
        printf("    (%d,%d)\n",ans1,ans2);
    }
}
int main(){
    for(int T=1;;T++){
        n=read();
        if(!n)break;
        printf("Game %d:\n",T);
        init();
        solve();
    }
    return 0;
}

例3-5 UVa1583 Digit Generator

题目链接

模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int tab[100005]={0};
void init(){
    for(int i=1;i<=100000;i++){
        int tmp=i,tot=i;
        while(tmp)tot+=tmp%10,tmp/=10;
        if(tot<=100000&&!tab[tot])tab[tot]=i;
    }
}
void solve(){
    for(int n=read();n;n--)printf("%d\n",tab[read()]);
}
int main(){
    init();
    solve();
    return 0;
}

例3-6 UVa1584 Circular Sequence

题目链接

模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
char s[1005];
int len;
void init(){
    scanf("%s",s);
    len=strlen(s),memcpy(s+len,s,sizeof(char)*len);
}
void solve(){
    int ans=0;
    for(int t=1;t<len;t++){
        int flag=1;
        for(int j=0;j<len;j++)
            if(s[t+j]<s[ans+j]){flag=0;break;}
            else if(s[t+j]>s[ans+j])break;
        if(!flag)ans=t;
    }
    for(int i=0;i<len;i++)
        putchar(s[i+ans]);
    putchar('\n');
}
int main(){
    for(int T=read();T;T--){
        init();
        solve();
    }
    return 0;
}

3-1 UVa1585 Score

题目链接

模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
char s[100];
void init(){
    scanf("%s",s);
}
void solve(){
    int len=strlen(s),tot=0,sc=0;
    for(int i=0;i<len;i++){
        if(s[i]=='O')tot++,sc+=tot;
        else tot=0;
    }
    printf("%d\n",sc);
}
int main(){
    for(int T=read();T;T--){
        init();
        solve();
    }
    return 0;
}

3-2 UVa1586 Score

题目链接

模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
char s[100];
double mass[26];
void init(){
    scanf("%s",s);
}
void solve(){
    double ans=0.0;
    int len=strlen(s),tot=0,ind=0;
    for(int i=0;i<len;i++){
        if(isalpha(s[i])){
            if(ind&&!tot)tot=1;
            ans+=tot*mass[ind],tot=0,ind=s[i]-'A';
        }else 
            tot=tot*10+s[i]-'0';
    }
    if(ind&&!tot)tot=1;
    ans+=tot*mass[ind];
    printf("%.3lf\n",ans);
}
int main(){
    mass[0]=0;
    mass[2]=12.010,mass[7]=1.008,mass[14]=16.000,mass[13]=14.010;
    for(int T=read();T;T--){
        init();
        solve();
    }
    return 0;
}

3-3 UVa1225 Digit Counting

题目链接

模拟

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int T,tab[10005]={0},ans[22][11],cnt[11]={0},maxn=0;
void init(){
    T=read();
    for(int i=0;i<T;i++){
        int t=read();
        tab[t]=i+1,maxn=max(maxn,t);
    }
}
void solve(){
    for(int i=1;i<=maxn;i++){
        int tmp=i;
        while(tmp)cnt[tmp%10]++,tmp/=10;
        if(tab[i]){
            int ind=tab[i];
            for(int j=0;j<10;j++)ans[ind][j]=cnt[j];
        }
    }
    for(int i=1;i<=T;i++){
        for(int j=0;j<9;j++)printf("%d ",ans[i][j]);
        printf("%d\n",ans[i][9]);
    }
}
int main(){
    init();
    solve();
    return 0;
}

3-4 UVA455 Periodic Strings

题目链接

这题有多种做法，这里选的是最容易想到的一种。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
char s[1005];
int main(){
    int N=read(),flag=0;
    while(N--){
        scanf("%s",s);
        int len=strlen(s),ans=len;
        for(int i=1;i<len;i++)
            if(len%i==0){
                int fl=1;
                for(int j=i;j<len;j++)
                    if(s[j]!=s[j%i]){fl=0;break;}
                if(fl){ans=i;break;}
            }
        if(!flag)flag=1;
        else putchar('\n');
        printf("%d\n",ans);
    };
    return 0;
}

3-5 UVa227 Puzzle

题目链接

这题神坑

  1. 有可能拼图里面有字母Z
  2. 最后一行的空行不能有，不然无限WA
    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #include <cctype>
    #define INF 2000000000
    using namespace std;
    typedef long long ll;
    int read(){
        int f=1,x=0;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
        while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
        return f*x; 
    }
    char puz[7][7],list[100005],tmp[100005];
    int len,x,y;
    bool readPuzzle(){
        char c[10];
        for(int i=0;i<5;i++){
            fgets(c,10,stdin);
            if(c[0]=='Z'&&strlen(c)<5)return false;
            for(int j=0;j<5;j++)
                if(isalpha(c[j]))puz[i][j]=c[j];
                else if(c[j]==' ')puz[(x=i)][(y=j)]=c[j];
        }
        return true;
    }
    bool move(int id){
        if(list[id]=='A'){
            if(!x)return false;
            swap(puz[x-1][y],puz[x][y]),x--;
            return true;
        }
        if(list[id]=='B'){
            if(x==4)return false;
            swap(puz[x+1][y],puz[x][y]),x++;
            return true;
        }
        if(list[id]=='L'){
            if(!y)return false;
            swap(puz[x][y],puz[x][y-1]),y--;
            return true;
        }
        if(list[id]=='R'){
            if(y==4)return false;
            swap(puz[x][y+1],puz[x][y]),y++;
            return true;
        }
        return false;
    }
    void solve(){
        int flag=1;
        for(int _flag=1;_flag;){
            fgets(list,100000,stdin);
            int len=strlen(list);
            for(int i=0;i<len;i++){
                //printf("%c",list[i]);
                if(isalpha(list[i])){
                    if(!move(i)&&flag){
                        printf("This puzzle has no final configuration.\n");
                        flag=0;
                    }
                }else if(list[i]=='0'){
                    _flag=0;
                    break;
                }else if(!isspace(list[i])){
                    if(flag)
                        printf("This puzzle has no final configuration.\n"),flag=0;
                }
            }
        }
        if(flag){
            for(int i=0;i<5;i++){
                for(int j=0;j<4;j++)
                    printf("%c ",puz[i][j]);
                printf("%c\n",puz[i][4]);
            }
        }
    }
    int main(){
        int T=1;
        while(readPuzzle()){
            if(T!=1)putchar('\n');
            printf("Puzzle #%d:\n",T++);
            solve();
            memset(puz,0,sizeof(puz));
        }
        return 0;
    }

3-8 UVa202 Repeating Decimals

题目链接

模拟
只要除出来了一样的余数就停止
因为除数不是很大，所以余数不算多，可以完成

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int m,n,vis[3005]={0},lis[3105];
void init(){
    printf("%d/%d = %d.",m,n,m/n);
    m%=n;
}
void solve(){
    int ans=1,pace=1;
    memset(vis,0,sizeof(vis));
    for(;m;pace++){
        if(vis[m])break;
        vis[m]=pace,m*=10;
        lis[pace]=m/n,m%=n;
    }
    if(!m){
        for(int i=1;i<pace;i++)
            printf("%d",lis[i]);
        printf("(0)\n");
    }else {
        for(int i=1;i<vis[m];i++)
            printf("%d",lis[i]);
        printf("(");
        if(pace<=50){
            for(int i=vis[m];i<pace;i++)
                printf("%d",lis[i]);
            printf(")\n");
        }else{
            for(int i=vis[m];i<=50;i++)
                printf("%d",lis[i]);
            printf("...)\n");
        }
        ans=pace-vis[m];
    }
    printf("   %d = number of digits in repeating cycle\n\n",ans);
}
int main(){
    while(scanf("%d%d",&m,&n)==2){
        init();
        solve();
    }
    return 0;
}

3-10 UVa1587 Box

题目链接
保证构成一个长方体需要：

  1. 有3组相同的面
  2. 有3组长宽高

判断即可。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
pair<int,int> p[7];
int a[19];
void init(){
    for(int i=1;i<6;i++)
        scanf("%d%d",&p[i].first,&p[i].second);
    for(int i=0;i<6;i++){
        if(p[i].first<p[i].second)
            swap(p[i].first,p[i].second);
        a[i<<1]=p[i].first,a[i<<1|1]=p[i].second;
    }
    sort(a,a+12);
    sort(p,p+6);
}
void solve(){
    int ans=1;
    for(int i=0;i<6;i+=2)
        if(p[i].first!=p[i+1].first||p[i].second!=p[i+1].second){
            ans=0;break;
        }
    for(int i=0;i<12;i+=4)
        if(a[i]!=a[i+1]||a[i]!=a[i+2]||a[i]!=a[i+3]){
            ans=0;break;
        }
    if(!ans)printf("IM");
    printf("POSSIBLE\n");
}
int main(){
    while(scanf("%d%d",&p[0].first,&p[0].second)==2){
        init();
        solve();
    }
    return 0;
}

3-12 UVa11809 Floating-Point Numbers

题目链接

数字都很大，用数字的对数比较。
事先对不同M和E打个表，然后比即可。

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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
double tab[11][50],eps=1e-6;//M E
void init(){
    double t=0.5,u=0.5;
    for(int i=0;i<=9;i++){
        for(int j=1;j<=30;j++){
            double k=(double)((1<<j)-1);
            tab[i][j]=k*log(2.0)+log(t);
        }
        u*=0.5,t+=u;
    }
}
void solve(){
    char s[50];
    while(scanf("%s",s)==1){
        if(strlen(s)==3)break;
        s[17]=' ';
        double t,u,g;
        sscanf(s,"%lf%lf",&t,&u);
        g=u*log(10.0)+log(t);
        for(int i=0;i<=9;i++)
            for(int j=1;j<=30;j++)
                if(g-tab[i][j]<eps&&g-tab[i][j]>-eps){
                    printf("%d %d\n",i,j);
                    break;
                }
    }
}
int main(){
    init();
    solve();
    return 0;
}