第一章 手算题和杂题

资料来源：尚硅谷java数据结构，程序设计竞赛挑战教程（蓝桥杯专题组编写），CSDN优秀博客整理。

1.2 杂题

裁纸刀

【题目描述】小蓝有一把裁纸刀，每次可以将一张纸沿一条直线裁成两半。小蓝用一张纸打印出两行三列共6个二维码，至少要裁9次才能把它们裁出来，下图给出了一种裁法。

在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁4次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。如果小蓝要用一张纸打印出20行22列共440个二维码，那么他至少需要裁多少次？

模拟法，模拟裁剪过程。先在四周裁4次裁掉边界，然后裁19次得到20个长条（20行），再将每个长条裁21次得22列，答案是4 + 19 + 21×20 = 443。

分数

【题目描述】1/1 + 1/2 + 1/4 + 1/8 + …，每项是前一项的一半，如果一共有20项，求和是多少，结果用分数表示出来。分子分母要求互质。

#方法一
 1  a,b = 1,0
 2  for i in range(0,20):  
 3      b += a
 4      a *= 2    
 5  print(“%d/%d”%(b,a/2))
#方法二
print(“%d/%d”%(2 ** 20 -1,2 ** 19))      #注意**表示乘方
#方法三
print(str(2 ** 20 -1)+ ‘/’+str(2 ** 19))

付账问题

【题目描述】几个人一起出去吃饭是常有的事。但在结账的时候，常常会出现一些争执。现在有n个人出去吃饭，他们总共消费了S元。其中第i个人带了ai元。幸运的是，所有人带的钱的总数是足够付账的。但现在问题来了：每个人分别要出多少钱呢？为了公平起见，我们希望在总付钱量恰好为S的前提下，最后每个人付的钱的标准差最小。这里约定，每个人支付的钱数可以是任意非负实数（不一定是整数）。你需要输出最小的标准差是多少？标准差的介绍：标准差是多个数与它们平均数差值的平方的平均数的二分之一次方，一般用于刻画这些数之间的“偏差有多大”。形式化地说，设第i个人付的钱为bi元，那么标准差为？

求解的基本步骤如下。①对ai进行从小到大排序。②前一部分人的钱不够，那么就出他们所有的钱。③从总付钱数中扣除前一部分人出的钱，得剩余需要付的钱数为S’，以及后一部分人需要付的钱的平均数avg’。④后一部分人带的钱多，他们多出一些，但是该怎么出？这部分人也分为两类：一类是带的钱比较多的人，但是他的钱少于avg’，那么他的钱还是要全出；另一类是带的钱非常多的人，不管怎么平摊，他的钱都有富余。

 1  from math import *
 2  n, s = map(int,input().split())
 3  a = list(map(int,input().split()))
 4  a.sort()
 5  avg = s/n
 6  sum = 0
 7  for i in range(n):
 8       if a[i]*(n-i) < s:
 9            sum += pow(a[i]-avg,2)
10            s -= a[i]
11       else:
12            cur_avg = s/(n-i);      #更新平均出钱数
13            sum += pow(cur_avg-avg,2)*(n-i)
14            break
15  print(“{:.4f}”.format(sqrt(sum/(n))))

矩形拼接

【输出格式】对于每组数据，输出一个整数代表答案。

【输入样例】22 3 4 1 2 41 2 3 4 5 6

【输出样例】46

【评测用例规模与约定】对于10%的评测用例，1≤T≤5，1≤a1, b1, a2, b2, a3,b3≤10，a1 = a2 = a3；对于30%的评测用例，1≤T≤5，1≤a1, b1, a2, b2, a3,b3≤10；对于60%的评测用例，1≤T≤10，1≤a1, b1, a2, b2, a3, b3≤20；对于所有评测用例，1≤T≤1000，1≤a1,b1, a2, b2, a3, b3≤100。

#第一种检验：完全拼接
def check1(x1,x2,x3):
      if x1>=x2 and x1>=x3:
            # a[2]+a[3]-x2 的意思是该矩形中除了满足x1==x2+x3的另一条边
          if x1==x2+x3 and a[2]+a[3]-x2==a[4]+a[5]-x3:  return True
      if x2>=x1 and x2>=x3:
          if x2==x1+x3 and a[0]+a[1]-x1==a[4]+a[5]-x3:  return True
      if x3>=x1 and x3>=x2:
          if x3==x1+x2 and a[0]+a[1]-x1==a[2]+a[3]-x2:  return True
      return False
#第一种检验：不完全拼接
def check2(x1,x2,x3):
      if x1>=x2 and x1>=x3:
            #该条件保证了能拼成一条边
          if x1==x2+x3:    return True
      if x2>=x1 and x2>=x3:
          if x2==x1+x3:    return True
      if x3>=x1 and x3>=x2:
          if x3==x1+x2:    return True
      return False

T = int(input())
for t in range(T):
      a=list(map(int,input().split()))
      ans=8
      for i in range(0,2):              #第1个矩形
          for j in range(2,4):          #第2个矩形
              for k in range(4,6):      #第3个矩形
                  x1,x2,x3 = a[i],a[j],a[k]
                  if x1==x2 and x2==x3:          ans = min(ans,4)
                  if check1(x1,x2,x3):           ans = min(ans,4)
                  if x1==x2 or x1==x3 or x2==x3: ans = min(ans,6)
                  if check2(x1,x2,x3):           ans = min(ans,6)
      print(ans)

蜂巢

【题目描述】蜂巢由大量的六边形拼接而成，定义蜂巢中的方向：0表示正西方向，1表示西偏北60°，2表示东偏北60°，3表示正东，4表示东偏南60°，5表示西偏南60°。对于给定的一点O，以O为原点定义坐标系，如果一个点A由O点先向d方向走p步再向(d + 2) mod 6方向（d的顺时针120°方向）走q步到达，则这个点的坐标定义为(d, p, q)。在蜂巢中，一个点的坐标可能有多种。下图是点B(0, 5, 3)和点C(2, 3, 2)的示意图。

给定点(d1, p1, q1)和点(d2, p2, q2)，请问它们之间最少走多少步可以到达？

【输入格式】输入一行，包含6个整数d1、p1、q1、d2、p2、q2，表示两个点的坐标，相邻两个整数之间使用一个空格分隔。

【输出格式】输出一行，包含一个整数，表示两点之间最少走多少步可以到达。

【输入样例】0 5 3 2 3 2

【输出样例】7

【评测用例规模与约定】对于25%的评测用例，p1, p2≤103；对于50%的评测用例，p1, p2≤105；对于75% 的评测用例，p1, p2≤107；对于所有评测用例，0≤d1, d2≤5，0≤q1 < p1≤109，0≤q2 < p2≤109。

本题是一道构造题，考点有两个：坐标转换、距离计算。蜂巢有6个方向，虽然看起来比较复杂，但实际上走步非常简单，例如样例中从点B走到点C，点C在点B的右下方，点B只要一直向右向下走，且不超过点C所在的行和列，一定存在从点B走到点C的最少步数。

本题的难点是对坐标的处理。如果是简单的直角坐标系，就很容易计算。本题的蜂巢由多个是六边形的蜂室组成，每个蜂室的中心点是否能转为直角坐标？把蜂室的中心点用图2.4所示的直角坐标表示。

中心点为O，对应的6个蜂室的中心点坐标分别为(−2, 0)、(−1, 1)、(1, 1)、(2,0)、(1, −1)、(−1, −1)，在下面的代码中用xdir[]、ydir[]表示。先计算得到起点坐标(x1, y1)、终点坐标(x2, y2)。如何计算起点到终点的步数？蜂室中心点坐标的距离不能直接用曼哈顿距离（两点之间的距离=|x1-x2|+|y1-y2|）计算。读者如果已经做了这一题，可能是用各种复杂的判断来计算的。下面给出一个简单巧妙的方法。坐标之差的绝对值dx = |x1−x2|、dy = |y1−y2|，有以下结论。

(1)若dx≥dy，则最少步数是(dx+dy)/2，即先横着走，再斜着走。

(2)若dx < dy，一直斜着走就行，最少步数是dy。下面是解题代码。

xdir = [-2,-1,1,2, 1,-1]
ydir = [ 0, 1,1,0,-1,-1]
def walk(d, q,x,y):
    x += xdir[d]*q
    y += ydir[d]*q
    return x,y
d1,p1,q1,d2,p2,q2 = map(int,input().split())
x1, y1 = walk(d1,p1,0,0)
x1, y1 = walk((d1 + 2) % 6, q1,x1,y1)
x2, y2 = walk(d2,p2,0,0)
x2, y2 = walk((d2 + 2) % 6, q2,x2,y2)
dx,dy = abs(x1 - x2), abs(y1 - y2);
if (dx >= dy): print((dx+dy)//2)     #先横着走，再斜着走
else:          print(dy)  

以下是蓝桥杯官网中的杂题
链接是https://www.lanqiao.cn/problems/97/learning/，题号97。

​

​