华为OD机试分享（6-25）

第一题：正方形的数量
给定N个坐标，问这些坐标能够组成的正方形的数量（垂直的向量内积为0）
思路是写一个判断，对四个坐标进行全排列，然后没个坐标求四个边是否相等以及四个边两两内积为0
再对所有的坐标进行组合，输出正方形的数量。逻辑没问题，就是超时了，只过了34%

from itertools import permutations,combinations  def judgesquers(arr): # arr是一个二维数组    y = permutations(arr, 4)
      flag = 0    for i in y:
        k = list(i)
        AB = [k[1][0] - k[0][0], k[1][1] - k[0][1]]
        BC = [k[2][0] - k[1][0], k[2][1] - k[1][1]]
        CD = [k[3][0] - k[2][0], k[3][1] - k[2][1]]
        DA = [k[3][0] - k[0][0], k[3][1] - k[0][1]]
        o = AB[0]**2 + AB[1]**2    p = BC[0]**2 + BC[1]**2    q = CD[0]**2 + CD[1]**2    r = DA[0]**2 + DA[1]**2    t = AB[0]*BC[0] + AB[1]*BC[1]
        u = BC[0]*CD[0] + BC[1]*CD[1]
        v = CD[0]*DA[0] + CD[1]*DA[1]
        w = AB[0]*DA[0] + AB[1]*DA[1]     if o == p == q == r and t == u == v == w == 0:
            flag += 1    
      break  else:
            flag += 0     if flag == 1:  return True  else:  return False   def squercount():
    n = int(input())
    res = []  while n:     try:
          s = input()  if s != "":
            res.append(list(map(int, s.split())))  except EOFError:  break  if len(res) < 4:  print(0)  else:
        t = combinations(res,4)
        cnt = 0    for j in t:
            x = list(j)  if judgesquers(x):
                cnt += 1    print(cnt)

第二题：黑板上N个数需要涂色，要求每种颜色最小的整数可以被同种颜色其他整数整除，问最少需要几种颜色，这个比较简单，100%通过

def func(): n = int(input())
    res = list(map(int, input().split()))
    res.sort()
    cnt = 1    while res:
        start = res.pop(0)
        tmp = res.copy()  for i in range(len(tmp)):  if tmp[i] % start == 0:
                res.remove(tmp[i])  if len(res) > 0:
                cnt += 1 print(cnt)

第三题：解密犯罪时间

警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如 “HH:MM” 表示的时刻。

根据警察和线人的约定，为了隐蔽，该时间是修改过的，解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。每个出现数字都可以被无限次使用。"
"输入描述:
形如HH:SS的字符串，表示原始输入
输出描述:
形如HH:SS的字符串，表示推理出来的犯罪时间
示例1
输入              输出
18:52            18:55
说明
利用数字1, 8, 5, 2构造出来的最近时刻是18:55，是3分钟之后。结果不是18:51因为这个时刻是23小时59分钟之后。
示例2
输入            输出
23:59          22:22
说明
利用数字2, 3, 5, 9构造出来的最近时刻是22:22。答案一定是第二天的某一时刻，所以选择可构造的最小时刻为犯罪时间。
备注:
1，可以保证线人给定的字符串一定是合法的。例如，“01:35” 和 “11:08” 是合法的，“1:35” 和 “11:8” 是不合法的。

2，最近的时刻有可能在第二天

考试的时候没啥思路，就想着把时间和分钟列举来，本来以为能通过个20%就不错了，没想到随便列举了下通过了55%的用例，也算是意外，代码很丑，就不贴了

#华为od#