【竞赛经历】CSDN第41期竞赛题解

1 前言

  本次的竞赛主要是最后一题，对于完全不懂珠算的人来说还是有点困难的，仅理解题目的意思就花了很多时间，最后侥幸拿了第一个前三。。。

2 题解

  本次竞赛分为编程题部分和非编程题部分，其中非编程题部分比较简单。

2.1 非编程题部分：

这道题我一开始的理解是，算盘可以记录计算的中间过程，同时可以辅助计算，这样就能充分利用人脑的计算能力，但是题目来源的那本书上好像不是这么理解的，chat-gpt也认为不对，那基本实锤了。

这道题应该没啥疑问

这个不知道得问度娘，关键词：机械计算机，1642

这道题答案有问题，后续官方给更正了。算是一道相对简单的心算题，关键是记住常见的2的n次方，如2^7=128, 2^10=1024等

2.2 第1道编程题：数制转换

• 题目：

  由于人类长了十根手指，所以人类的计数最常用的数制就是十进制。 但是，计算机中最常用的进制是二进制，因为二进制可以用比较少的物理状态来表示。 可是二进制只有0和1两个数字，很容易写得很长，所以也经常使用八进制或十六进制。
  八进制的数使用0到7八个数字来表示，逢八进一。 十六进制的数除了0到9这十个数字以外，还使用A到F这六个字母（A到F分别代表十进制的10到15）一共十六个符号来表示，逢十六进一。 请把输入的数字转换为十进制。 如果数字中只有0和1，那么就认为是二进制。 如果数字中只有0到7，那么就认为是八进制。 如果数字中有不止0到7，那么就认为是十六进制。 如果出现了0到9、A到F（不区分大小写）之外的字母，那么就请输出“NaN”

• 分析：

  在python当中数制转换非常简单int(n, 2)即表示将n转换为二进制表示。另外就是需要判断当前数的进制，这个可以将数字转换为字符串，然后判断ASCII最大的字符所在区段，从而判断进制。

• 代码：

b = input()
a = '0123456789abcdefABCDEF'
t = all((x in a) for x in b ) #b中的全部字符在a中输出True，否则False
if not t:print('NaN')
else:c = max(list(ord(x) for x in b))
if c <= ord('1'):print(int(b, 2))
elif ord('1') < c <= ord('7'):print(int(b, 8))
elif ord('8') <= c <= ord('f'):print(int(b, 16))

2.3 第2道编程题：珠算指令生成器

• 题目：

  现代人做两个数的加减法运算，是非常简单的事情：只要在计算器上按出第一个数，再按一下“+”或“-”键，再按出第二个数，最后按一下“=”键，就能够看到运算的结果了。但古代人没有计算器，还好古代中国有算盘这种工具。 CSDN的zjg55543同学在博客里给出了珠算加减法用到的口诀表：珠心算口诀表_zjg555543的博客-CSDN博客。

  请你尝试把根据输入数的加减运算生成相应的珠算指令序列，每个指令对应于一句或若干句口诀，并该口诀之前输出其所应用的位置和该口诀所涉及的拨珠次数。

  个位记为位置0、十位记为位置1、百位记为位置2，以此类推。同样地，十分位记为位置-1，百分位记为位置-2，以此类推。

  有的口诀只需要拨动一次上珠或下珠，如“一上一”和“五下五”等。有的则需要拨动一次上珠和一次下珠，如“六上六”、“九下九”、“三下五去二”和“八退一还五去三”（“进一”或“退一”是从相邻高位进一或退一，并不需要在该位执行这一口诀时实际拨珠）等。

  最后，输出总拨珠次数。

• 分析：
    个人觉得遇到这种复杂的问题，一定要先想清楚逻辑，然后转换为多个函数，想清楚每个函数的输入输出，然后再整合起来。
    当然，在分析过程当中，如果有想不清楚的一定要用笔记录一下，在纸上推演。
    回到这道题，首先要理解珠算口诀，各个数字代表的含义以及为什么要先下再去，为什么要先退再还，它们各自针对的是哪一位。
    理解珠算口诀之后，再来分析一下：

  • 我们需要将每个数字都拆分成一个字符列表，每一位对应一个数，然后分别去做加减，同时要更新一个总的状态。
  • 对于每一位在计算时，会有一个原数和一个加数，原数保证是正的（题目中给出的说明），加数可正可负。需要根据原数和加数，一方面算出进位和计算完毕之后的取值以及这一位对应的口令，一方面还要计算这一位需要拨动算珠的次数（一般就是1或者2）
  • 如果有连续进位或者连续退位，要考虑。可以用while循环判断更新的进位变量。

• 代码：

import sys
s = []
ss = []
while True:line = sys.stdin.readline()if not line: breaks.append(line)for item in s:if item != '\n':ss.append(item.strip())
# 以上可以作为一个有输入EOF的python代码n = 0
def num2status (s:str):# 将一个数字转换成一个字符list，便于后续分析# "-13.2" -> [0,-2,-3,-1,0,0,0]flag = s[0]=="-"s = s.replace("-","")a, b = (s+".").split(".")[:2]s = a.rjust(8,"0") + b.ljust(3,"0")r = [ -i if flag else i for i in map(int,s[::-1]) ]return rdef toggleCnt(n1, n2):'''对于某一位上,数字的变化输出需要拨动的次数'''if(max(n1,n2) < 5): return 1elif(n1<5 and n2>=5): return 2elif(n1>=5 and n2>=5): return 1elif(n1>=5 and n2<5): return 2dic1 = { #加法口令1: ['一上一', '一下五去四', '一去九进一', ''],2: ['二上二', '二下五去三', '二去八进一', ''],3: ['三上三', '三下五去二', '三去七进一', ''],4: ['四上四', '四下五去一', '四去六进一', ''],5: ['五上五', '五上五', '五去五进一', ''],6: ['六上六', '六上六', '六去四进一', '六上一去五进一'],7: ['七上七', '七上七', '七去三进一', '七上二去五进一'],8: ['八上八', '八上八', '八去二进一', '八上三去五进一'],9: ['九上九', '九上九', '九去一进一', '九上四去五进一']
}
dic2 = { #减法口令1: [ "一下一", "一上四去五", "一退一还九", "" ],2: [ "二下二", "二上三去五", "二退一还八", "" ],3: [ "三下三", "三上二去五", "三退一还七", "" ],4: [ "四下四", "四上一去五", "四退一还六", "" ],5: [ "五下五", "", "五退一还五", "" ],6: [ "六下六", "", "六退一还四", "六退一还五去一" ],7: [ "七下七", "", "七退一还三", "七退一还五去二" ],8: [ "八下八", "", "八退一还二", "八退一还五去三" ],9: [ "九下九", "", "九退一还一", "九退一还五去四" ],
}
def addOrSub(x, y):'''根据当前数(x)和加数(y, 可正可负)，来输出口令'''if y<0:op='-'y=-yelse:op='+'if op == '-':s = x-yif s<0: #退位减s += 10z = -1if y>5:if x<=y-6:q = dic2[y][2]else:q = dic2[y][3]else:q = dic2[y][2]else:z = 0if x>=5:q = dic2[y][1]else:q = dic2[y][0]else:s = (x+y)%10 #当前位结果z = (x+y)//10 #进位q = ''if(z>0):if(x<5):q = dic1[y][2]else:q = dic1[y][3]else:if(s < 5):q = dic1[y][0]elif(s >= 5):q = dic1[y][1]return s,z,q # 位值 进位  口令state = [0]*(3+8)
# 遍历每个字符串
for s in ss:
# 遍历字符串的每一位，从后往前
for idx in range(3+8):b = num2status(s)[idx]if b==0: continuer = b# 当有进位时，往前遍历while r:c, r, q = addOrSub(state[idx], r)# 位置、拨动次数、口令x = toggleCnt(state[idx],c)n+=xprint (idx-3, toggleCnt(state[idx],c), q)state[idx] = cidx += 1print(n)

• 后续：
    当时这个代码提交之后，准确率只有1/3（好像大家都是这个分数？不太清楚为啥），后来复盘发现应该是其中的addOrSub函数写得不够全面，对于很多情况考虑存在问题，于是想了一个最直接的办法，把所有情况直接列出来！然后再按照原位数字和加数来查找口令。代码如下：

table = (" - S1   S2   S3   S4   S5   S6     S7     S8     S9     T1H1   T1H2   T1H3   T1H4   T1H5 T1H6 T1H7 T1H8 T1H9 \n" # 0" - S1   S2   S3   X5Q1 S5   S6     S7     S8     Q1J1   T1H1   T1H2   T1H3   T1H5Q1 T1H5 T1H6 T1H7 T1H8 X1   \n" # 1" - S1   S2   X5Q2 X5Q1 S5   S6     S7     Q2J1   Q1J1   T1H1   T1H2   T1H5Q2 T1H5Q1 T1H5 T1H6 T1H7 X2   X1   \n" # 2" - S1   X5Q3 X5Q2 X5Q1 S5   S6     Q3J1   Q2J1   Q1J1   T1H1   T1H5Q3 T1H5Q2 T1H5Q1 T1H5 T1H6 X3   X2   X1   \n" # 3" - X5Q4 X5Q3 X5Q2 X5Q1 S5   Q4J1   Q3J1   Q2J1   Q1J1   T1H5Q4 T1H5Q3 T1H5Q2 T1H5Q1 T1H5 X4   X3   X2   X1   \n" # 4" - S1   S2   S3   S4   Q5J1 S1Q5J1 S2Q5J1 S3Q5J1 S4Q5J1 T1H1   T1H2   T1H3   T1H4   X5   S1Q5 S2Q5 S3Q5 S4Q5 \n" # 5" - S1   S2   S3   Q6J1 Q5J1 S1Q5J1 S2Q5J1 S3Q5J1 Q1J1   T1H1   T1H2   T1H3   X6     X5   S1Q5 S2Q5 S3Q5 X1   \n" # 6" - S1   S2   Q7J1 Q6J1 Q5J1 S1Q5J1 S2Q5J1 Q2J1   Q1J1   T1H1   T1H2   X7     X6     X5   S1Q5 S2Q5 X2   X1   \n" # 7" - S1   Q8J1 Q7J1 Q6J1 Q5J1 S1Q5J1 Q3J1   Q2J1   Q1J1   T1H1   X8     X7     X6     X5   S1Q5 X3   X2   X1   \n" # 8" - Q9J1 Q8J1 Q7J1 Q6J1 Q5J1 Q4J1   Q3J1   Q2J1   Q1J1   X9     X8     X7     X6     X5   X4   X3   X2   X1   \n" # 9# 0 +1   +2   +3   +4   +5   +6     +7     +8     +9     -9     -8     -7     -6     -5   -4   -3   -2   -1
)abbr = {"0": "〇", "1": "一", "2": "二", "3": "三", "4": "四", "5": "五", "6": "六", "7": "七", "8": "八", "9": "九","S": "上", "X": "下", "Q": "去", "J": "进", "T": "退", "H": "还",
}table = [ [ (str(abs(b))+j).translate(str.maketrans(abbr))for b,j in zip(list(range(0,10))+list(range(-9,0)),i.split()) ]for i in table.split("\n")[:-1] ]def addOrSub (a:int, b:int):cc = a + bc = cc%10; r = 1 if cc>9 else -1 if cc<0 else 0; q = table[a][b]return c, r, q