巴马腕表批发销售联盟

【专题】USACO 竞赛常见问题解答<四>

Embark有方博雅2019-01-14 11:07:20


点击查看:USACO 竞赛常见问题解答<一>


点击查看:USACO 竞赛常见问题解答<二>


点击查看:USACO 竞赛常见问题解答<三>


12

函数和递归 - 刽子手游戏

刽子手游戏其实是一款猜单词游戏,如图所示。游戏规则是这样的:计算机想一个单词让你猜,你每次可以猜一个字母。如果单词里有那个字母,所有该字母会显示出来;如果没有那个字母,则计算机会在一幅“刽子手”画上填一笔。这幅画一共需要7笔就能完成,因此你最多只能错6次。注意,猜一个已经猜过的字母也算错。



在本题中,你的任务是编写一个“裁判”程序,输入单词和玩家的猜测,判断玩家赢了(You win.)、输了(You lose.)还是放弃了(You chickened out.)。每组数据包含3行,第1行是游戏编号(-1为输入结束标记),第2行是计算机想的单词,第3行是玩家的猜测。后两行保证只含小写字母。


样例输入:

1

cheese

chese

2

cheese

abcdefg

3

cheese

abcdefgij

-1

样例输出:

Round 1

You win.

Round 2

You chickened out.

Round 3

You lose.


【分析】


一般而言,程序不是直接从第一行开始写到最后一行结束,而是遵循两种常见的顺序之一:自顶向下和自底向上。什么叫自顶向下呢?简单地说,就是先写框架,再写细节。实际上,之前已经用过这个方法了,就是先写“伪代码”,然后转化成实际的代码。有了“函数”这个工具之后,可以更好地贯彻这个方法:先写主程序,包括对函数的调用,再实现函数本身。自底向上和这个顺序相反,是先写函数,再写主程序。对于编写复杂软件来说,自底向下的构建方式有它独特的优势。但在算法竞赛中,这样做的选手并不多见。


【解答】


#include<stdio.h>

#include<string.h>

#define maxn 100

int left, chance; //还需要猜left个位置,错chance次之后就会输

char s[maxn], s2[maxn]; //答案是字符串s,玩家猜的字母序列是s2

int win, lose; //win=1表示已经赢了;lose=1表示已经输了


void guess(char ch) { … }


 int main() {

    int rnd;

    while(scanf("%d%s%s", &rnd, s, s2) == 3 && rnd != -1) {

        printf("Round %d\n", rnd);

        win = lose = 0; //求解一组新数据之前要初始化

        left = strlen(s);

        chance = 7;

        for(int i = 0; i < strlen(s2); i++) {

           guess(s2[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;

}


13

函数和递归 - 救济金发放

n(n<20)个人站成一圈,逆时针编号为1~n。有两个官员,A从1开始逆时针数,B从n开始顺时针数。在每一轮中,官员A数k个就停下来,官员B数m个就停下来(注意有可能两个官员停在同一个人上)。接下来被官员选中的人(1个或者2个)离开队伍。


输入n,k,m输出每轮里被选中的人的编号(如果有两个人,先输出被A选中的)。例如,n=10,k=4,m=3,输出为4 8, 9 5, 3 1, 2 6, 10, 7。注意:输出的每个数应当恰好占3列。


【分析】


仍然采用自顶向下的方法编写程序。用一个大小为0的数组表示人站成的圈。为了避免

人走之后移动数组元素,用0表示离开队伍的人,数数时跳过即可。


#include<stdio.h>

#define maxn 25

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

//逆时针走t步,步长是d(-1表示顺时针走),返回新位置

int go(int p, int d, int t) { … }

int main() {

while(scanf("%d%d%d", &n, &k, &m) == 3 && n) {

for(int i = 1; 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("%3d", p1); left--;

if(p2 != p1) { printf("%3d", p2); left--; }

a[p1] = a[p2] = 0;

if(left) printf(",");

}

printf("\n");

}

return 0;

}


14

函数和递归 - 踪电子表格中的单元格

有一个r行c列(1≤r,c≤50)的电子表格,行从上到下编号为1~r,列从左到右编号为1~c。如图(a)所示,如果先删除第1、5行,然后删除第3, 6, 7, 9列,结果如图(b)所示


接下来在第2、3、5行前各插入一个空行,然后在第3列前插入一个空列,会得到如图所示结果。



你的任务是模拟这样的n个操作。具体来说一共有5种操作:


EX r1 c1 r2 c2交换单元格(r1,c1),(r2,c2)。

<command> A x1 x2 … xA 插入或删除A行或列(DC-删除列,DR-删除行,IC-插入列,IR-插入行,1≤A≤10)。


在插入/删除指令后,各个x值不同,且顺序任意。接下来是q个查询,每个查询格式为“r c”,表示查询原始表格的单元格(r,c)。对于每个查询,输出操作执行完后该单元格的新位置。输入保证在任意时刻行列数均不超过50。


【分析】


最直接的思路就是首先模拟操作,算出最后的电子表格,然后在每次查询时直接在电子表格中找到所求的单元格。


【解答】


#include<stdio.h>

#include<string.h>

#define maxd 100

#define BIG 10000

int r, c, n, d[maxd][maxd], d2[maxd][maxd], ans[maxd][maxd], cols[maxd];

void copy(char type, int p, int q) {

if(type == 'R') {

for(int i = 1; i <= c; i++)

d[p][i] = d2[q][i];

} else {

for(int i = 1; i <= r; i++)

d[i][p] = d2[i][q];

}

}

void del(char type) {

memcpy(d2, d, sizeof(d));

int cnt = type == 'R' ? r : c, cnt2 = 0;

for(int i = 1; i <= cnt; i++) {

if(!cols[i]) copy(type, ++cnt2, i);

}

if(type == 'R') r = cnt2; else c = cnt2;

}

void ins(char type) {

memcpy(d2, d, sizeof(d));

int cnt = type == 'R' ? r : c, cnt2 = 0;

for(int i = 1; i <= cnt; i++) {

if(cols[i]) copy(type, ++cnt2, 0);

copy(type, ++cnt2, i);

}

if(type == 'R') r = cnt2; else c = cnt2;

}

int main() {

int r1, c1, r2, c2, q, kase = 0;

char cmd[10];

memset(d, 0, sizeof(d));

while(scanf("%d%d%d", &r, &c, &n) == 3 && r) {

int r0 = r, c0 = c;

for(int i = 1; i <= r; i++)

for(int j = 1; j <= c; j++)

d[i][j] = i*BIG + j;

while(n--) {

scanf("%s", cmd);

if(cmd[0] == 'E') {

scanf("%d%d%d%d", &r1, &c1, &r2, &c2);

int t = d[r1][c1]; d[r1][c1] = d[r2][c2]; d[r2][c2] = t;

} else {

int a, x;

scanf("%d", &a);

memset(cols, 0, sizeof(cols));

for(int i = 0; i < a; i++) { scanf("%d", &x); cols[x] = 1; }

if(cmd[0] == 'D') del(cmd[1]); else ins(cmd[1]);

}

}

memset(ans, 0, sizeof(ans));

for(int i = 1; i <= r; i++)

for(int j = 1; j <= c; j++) {

ans[d[i][j]/BIG][d[i][j]%BIG] = i*BIG+j;

}

if(kase > 0) printf("\n");

printf("Spreadsheet #%d\n", ++kase);

scanf("%d", &q);

while(q--) {

scanf("%d%d", &r1, &c1);

printf("Cell data in (%d,%d) ", r1, c1);

if(ans[r1][c1] == 0) printf("GONE\n");

else printf("moved to (%d,%d)\n", ans[r1][c1]/BIG, ans[r1][c1]%BIG);

}

}

return 0;

}


有方USACO冠军营

零基础通关USACO

我们为你提供

计算机编程基础

历年真题的实战



如果您有任何关于比赛问题,欢迎咨询有方小科!

Copyright © 巴马腕表批发销售联盟@2017