团队天梯赛练习题题解 L1-071~L1-080 (TODO)
前情提要，Python题解思路基本写在代码，新老博客夹杂写出的，风格不统一也正常
两个人思路不一样也很正常，两种思路都可以的，不一定只有这种实现
L1-071 前世档案 (20 分)
网络世界中时常会遇到这类滑稽的算命小程序，实现原理很简单，随便设计几个问题，根据玩家对每个问题的回答选择一条判断树中的路径（如下图所示），结论就是路径终点对应的那个结点。
现在我们把结论从左到右顺序编号，编号从 1 开始。这里假设回答都是简单的“是”或“否”，又假设回答“是”对应向左的路径，回答“否”对应向右的路径。给定玩家的一系列回答，请你返回其得到的结论的编号。
输入格式：
输入第一行给出两个正整数：N（≤30）为玩家做一次测试要回答的问题数量；M（≤100）为玩家人数。
随后 M 行，每行顺次给出玩家的 N 个回答。这里用 y 代表“是”，用 n 代表“否”。
输出格式：
对每个玩家，在一行中输出其对应的结论的编号。
输入样例：
3 4
yny
nyy
nyn
yyn输出样例：
3
5
6
2作者：陈越
单位：浙江大学
代码长度限制：16 KB
时间限制：400 ms
内存限制：64 MB
PotremZ’s Solution
-
本题可以转换为在一棵二叉树上移动，输出最底层的结点号即可；
-
可以直接套用二叉树编号，这样 最后一层的结点号 即为答案；
PotremZ の C++ 解決策
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
string s;
int dfs(int x,int o){
if(x==n) return o;
if(s[x]=='y') dfs(x+1,o<<1);
else dfs(x+1,o<<1|1);
}
int main(){
scanf("%d %d",&n,&m);
while(m--){
cin>>s;
printf("%d\n",dfs(0,1)-(int)pow(2,n)+1);
}
return 0;
}winterl の Python 解決策
def calculate_index(ways):
# 看明白了吧？这就是一个二叉树查询叶子元素的序列
# 只要按照这个写一个求二叉树访问就完了
result = 1
for way in ways:
if way == "y": # 左子树
result = result << 1
else: # 右子树
result = result << 1 | 1
return result
height, count_of_players = map(int, input().split())
# 这又是一个类似 B+ 树的布局
# 我们只需要对叶子进行索引，可以推出
# 高度为 n 的完全二叉树有 2**(n + 1) - 1 个节点
# 去掉底层叶子节点，有 2**n - 1 个节点
# 所以我们直接减去就好了
offset = (1 << height) - 1
for _ in range(count_of_players):
index = calculate_index(input())
print(index - offset)L1-072 刮刮彩票 (20 分)
“刮刮彩票”是一款网络游戏里面的一个小游戏。如图所示：
每次游戏玩家会拿到一张彩票，上面会有 个数字，分别为数字 到数字 ，数字各不重复，并以 的“九宫格”形式排布在彩票上。
在游戏开始时能看见一个位置上的数字，其他位置上的数字均不可见。你可以选择三个位置的数字刮开，这样玩家就能看见四个位置上的数字了。最后玩家再从 横、 竖、 斜共 个方向中挑选一个方向，方向上三个数字的和可根据下列表格进行兑奖，获得对应数额的金币。
| 数字合计 | 获得金币 | 数字合计 | 获得金币 |
|---|---|---|---|
| 6 | 10,000 | 16 | 72 |
| 7 | 36 | 17 | 180 |
| 8 | 720 | 18 | 119 |
| 9 | 360 | 19 | 36 |
| 10 | 80 | 20 | 306 |
| 11 | 252 | 21 | 1,080 |
| 12 | 108 | 22 | 144 |
| 13 | 72 | 23 | 1,800 |
| 14 | 54 | 24 | 3,600 |
| 15 | 180 |
现在请你写出一个模拟程序，模拟玩家的游戏过程。
输入格式
输入第一部分给出一张合法的彩票，即用 3 行 3 列给出 0 至 9 的数字。0 表示的是这个位置上的数字初始时就能看见了，而不是彩票上的数字为 0。
第二部给出玩家刮开的三个位置，分为三行，每行按格式 x y 给出玩家刮开的位置的行号和列号（题目中定义左上角的位置为第 1 行、第 1 列。）。数据保证玩家不会重复刮开已刮开的数字。
最后一部分给出玩家选择的方向，即一个整数： 1 至 3 表示选择横向的第一行、第二行、第三行，4 至 6 表示纵向的第一列、第二列、第三列，7、8分别表示左上到右下的主对角线和右上到左下的副对角线。
输出格式
对于每一个刮开的操作，在一行中输出玩家能看到的数字。最后对于选择的方向，在一行中输出玩家获得的金币数量。
输入样例
1 2 3
4 5 6
7 8 0
1 1
2 2
2 3
7输出样例
1
5
6
180作者：DAI, Longao
单位：杭州百腾教育科技有限公司
代码长度限制：16 KB
时间限制：400 ms
内存限制：64 MB
PotremZ の C++ 解決策
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mp[4][4],num,ans,px,py,C[25]={0,0,0,0,0,0,10000,36,720,360,80,252,108,72,54,180,72,180,119,36,306,1080,144,1800,3600};
bool vis[10];
int main(){
for(int i=1;i<=3;++i)
for(int j=1;j<=3;++j){
scanf("%d",&mp[i][j]);
if(mp[i][j]==0) px=i,py=j;
vis[mp[i][j]]=1;
}
for(int i=1;i<=9;++i) if(!vis[i]) mp[px][py]=i;
for(int x,y,i=1;i<=3;++i){
scanf("%d %d",&x,&y);
printf("%d\n",mp[x][y]);
}
scanf("%d",&num);
if(1<=num && num<=3) ans=mp[num][1]+mp[num][2]+mp[num][3];
if(4<=num && num<=6) ans=mp[1][num-3]+mp[2][num-3]+mp[3][num-3];
if(num==7) ans=mp[1][1]+mp[2][2]+mp[3][3];
if(num==8) ans=mp[1][3]+mp[2][2]+mp[3][1];
printf("%d",C[ans]);
return 0;
}winterl の Python 解決策
# 打个奖池表
PRICE = {
6: 10000,
7: 36,
8: 720,
9: 360,
10: 80,
11: 252,
12: 108,
13: 72,
14: 54,
15: 180,
16: 72,
17: 180,
18: 119,
19: 36,
20: 306,
21: 1080,
22: 144,
23: 1800,
24: 3600,
}
grid = [list(map(int, input().split())) for _ in range(3)]
# 1..=9 的和 减去输入的数的和 可以求出 0 位置的数
value = sum(range(1, 10)) - sum([sum(line) for line in grid])
# 还原这个数
for x in range(3):
for y in range(3):
if grid[x][y] == 0:
grid[x][y] = value
# 开始刮刮乐
for _ in range(3):
x, y = map(int, input().split())
# 转换成 0 索引，刮开并打印
print(grid[x - 1][y - 1])
# 出奖
option = int(input())
if option < 4: # 行
print(PRICE[sum(grid[option - 1])])
elif option < 7: # 列
print(PRICE[sum([grid[index][option - 4] for index in range(3)])])
elif option == 7: # 左上->右下
print(PRICE[sum([grid[index][index] for index in range(3)])])
else: # 右上->左下
print(PRICE[sum([grid[2 - index][index] for index in range(3)])])