Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

例题4:1-3 古老的密码、刽子手的游戏，救济金发放

2019/09/15 ACM竞赛入门 C
Word count: 1,434 | Reading time: 7min

例题4-1 古老的密码

  • 因为字母可以重排,所以顺序不重要,而又同时因为可以映射,所以字母具体是什么不重要==>只要统计排序后的结果相同就行了
  • RE(Runtime error)错法加一: 题号提交错误
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
#include <stdio.h>
#include <string.h>

void Bubblesort(int *cnt)//冒泡排序,从大到小顺序
{
    int i,j;
    int min=cnt[0];
    for (i = 0; i <26; ++i)
    {
       for ( j = i+1; j < 26; ++j)
       {
           if (cnt[i] < cnt[j])
           {
               min = cnt[i];
               cnt[i]=cnt[j];
               cnt[j] = min;
           }
       }
    }
}

int main()
{
    char s[2][105];	//存放猜测字符串的
    int cnt[2][27]; //存放字母出现次数
    int nlen[2];	//字符串的长度
    while(scanf("%s%s",s[0],s[1])!= EOF)
    {
        memset(cnt,0,sizeof(cnt));
        int i;
        for ( i = 0; i < 2; ++i)
        {
            nlen[i]= strlen(s[i]);
            int j;
            for ( j = 0; j < nlen[i]; ++j)
                cnt[i][s[i][j]-'A'] ++;
            Bubblesort(cnt[i]);
        }
        
        int k;
        for ( k = 0; k < 26; ++k)
        {
            if (cnt[0][k] != cnt[1][k])
            {
                printf("NO\n");
                break;
            }
        }
        if (k==26) printf("YES\n" );	//如果26个字母出现次数比完全相等,则可以说相同.
    }
    return 0;
}

例题4-2 刽子手的游戏

  • 注意全局变量是否使用的问题,全局变量尽量少用…但维护内容较多的情况下,可以考虑
  • 采用"自顶向下"的顺序
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 <stdio.h>
#include <string.h>
#define maxn 100
char ans[maxn],gue[maxn];
int left,chance;
int win,lose;
void guess(char ch)
{
	int bad=1;
	int i;
	for ( i = 0; i < strlen(ans); ++i)		//判断ch字母是否在字符串中
	{
		if (ans[i]==ch)
		{
			ans[i] = ' ';
			bad =0;
			left--;							//如果在的话,还剩未猜中字母数-1,机会不变
		}
	}
    	if (bad) chance--;					//如果不在的话机会-1
		if(!chance) lose=1;
		if(!left) win=1;
}

int main()
{
	int rnd;
	while(scanf("%d%s%s",&rnd,ans,gue)==3 && rnd !=-1)
	{
		printf("Round %d\n",rnd);
		win = lose =0;
		left= strlen(ans);
		chance = 7;
		int i;
		int anslen=strlen(gue);
		for( i=0;i< anslen;i++) { guess(gue[i]); if(win || lose) break;}
			if(win) printf("You win.\n");
			else if(lose) printf("You lose.\n");
			else printf("You chickened out.\n");
	}
	return 0;
}
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
#include <stdio.h>
#include <string.h>

char a[1000],g[1000];//储存字符串 
int abook[26],gbook[26];//标记26个字母出现频率 
int main(){
    int k;
    int alen,glen;
    int i;
    int j;
    int suc,fau;
    int acount;
    while(scanf("%d",&k)==1&&k!=-1){
        scanf("%s%s",a,g);
        memset(abook,0,sizeof(abook));
        memset(gbook,0,sizeof(gbook));
        alen=strlen(a);
        glen=strlen(g);
        for(i=0;i<alen;i++)//统计答案字母频率 
            abook[a[i]-'a']++;
        
        acount=0;
        for(i=0;i<26;i++)
            if(abook[i])//统计答案的字母组成个数（扣除雷同字母） 
                acount++;
        
        suc=0;//猜对次数
        fau=0;//猜错次数
        for(i=0;i<glen;i++){//以猜测字母为基准进行扫描 
            j=g[i]-'a';
            if(abook[j]==0){//答案无此字母，猜测错误 
                fau++;
                if(fau==7)//彻底失败 
                    break;
            }else if(abook[j]!=0){//猜中字母 
                suc++;
                abook[j]=0;//将此字母从答案中剔除出去，此句比较关键!(再猜无效) 
                if(suc==acount)//成功 
                    break;
            }
        }
        
        printf("Round %d\n",k);
        if(fau>=7)//猜错7次及以上 
            printf("You lose.\n");
        else if(suc==acount)//全部猜对 
            printf("You win.\n");
        else
            printf("You chickened out.\n");   
    }
    return 0;
}

例题4-3 救济金发放

  • 圆圈如何轮回==>本质上是要求,大于n变成1,小于1变成n…实现1.越界后归正。2.(xxx)%n,
  • 领过设为1,没领过(初始)设为1
较为简洁、清晰的做法
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
#include <stdio.h>
#include <string.h>

int book[100];//领过的标记1，没领过的标记0 
int main(){
    int n,k,m;
    int kcount,mcount;
    int ki,mi;
    int kout,mout;
    int first;
    int ncount;
    while(scanf("%d%d%d",&n,&k,&m)==3&&n&&k&&m){
        memset(book,0,sizeof(book));
        ncount=0;
        
        ki=0;
        mi=n+1;
        first=1;
        while(ncount!=n){//n个人全被处理完毕//处理手法有些类似快速排序
            kcount=0;
            mcount=0;
            //每数一个人,都要判断是不是该越过他.只有0(未领过,才计数)
            while(kcount!=k){//k系列处理 
                ki++;
                if(ki>n)//ki越界处理 
                    ki=1;
                if(book[ki]==0)//未被选中计数  ki为当前值 
                    kcount++;
                
            }
            while(mcount!=m){//m系列处理 
                mi--;
                if(mi<1)//mi越界处理 
                    mi=n; 
                if(book[mi]==0)//未被选中计数 mi为当前值 
                    mcount++;
        }
            book[ki]=1;//不用担心ki==mi(重复设置为1不影响)
            book[mi]=1; 
            
            if(first){//打印处理
                first=0;
                if(ki!=mi){
                    printf("%3d%3d",ki,mi);
                    ncount+=2;
                }
                else{
                    printf("%3d",ki); 
                    ncount++;
                }
            }else{
                if(ki!=mi){
                    printf(",%3d%3d",ki,mi);
                    ncount+=2;
                }
                else{
                    printf(",%3d",ki);
                    ncount++;
                }
            }
        }
        printf("\n");
    }
    return 0;
}
书上做法
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
#include <stdio.h>
#include <string.h>

#define maxn 25

int n,k,m,a[maxn];

int go(int p,int d,int t)
{
    while(t--)	//每数一个人都要判断他是否已经领过
    do{
        p = (n+p+d)%n;
    }while(!a[p]);	//==0,领过
    return p;
}

int main()
{
    while(scanf("%d,%d,%d",&n,&k,&m)==3 && n)
    {
        for (int i = 0; i < n; ++i) a[i]=i;
        int left =n;
        int p1 =n,p2=1;
        while(left)
        {
            p1= go(p1,-1,k);
            p2= go(p2,1,m);
            printf("%d",p1);left--;
            if(p1!=p2) printf(" %d",p2);
            a[p1]=a[p2]=0;				//领了设置为0
            if(left) printf(",");		//注意输出格式
        }
        printf("\n");
    }
    return 0;
}

Author: Mrli

Link: https://nymrli.top/2018/09/01/例题4-1-3-古老的密码、刽子手的游戏，救济金发放/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
开学小蓝车180天免费卡NextPost >
WampSever配置本地环境，解决打开打开本地网站问题
CATALOG
  1. 1. 例题4-1 古老的密码
  2. 2. 例题4-2 刽子手的游戏
  3. 3. 例题4-3 救济金发放
    1. 3.1. 较为简洁、清晰的做法
    2. 3.2. 书上做法