ProjectEuler板刷记录

本文收录一些ProjectEuler中有趣的题目并给出个人题解。

Problem 54

本题并不困难，只是一个简单的模拟，但是如何让代码量减小是一个值得讨论的问题。

首先，我们可以将牌的点数和花色分开存储，我们只关心“所有牌的花色是否均相同”而不关注“每个牌的花色是多少”，所以可以分别排序。

之后，写一个函数level(card, color)来返回手牌的等级（数字越大，等级越高），若两人等级不同则直接判断，否则需要进一步比较具体点数。

这里是减少代码量的关键一步：不必对每一个等级都写一个具体的比较，注意到只有Flush的比较策略是不同的：每次拿剩下的最大手牌比较。

对于剩下的等级，我们只需对每个玩家存储：对每个k，出现过k次的牌的点数是什么。之后，依次比较出现过4次、3次、2次、1次的牌的点数大小即可。

Problem 54 示例代码

Problem 54

with open('0054_poker.txt', 'r') as file:
    content = file.readlines()

ans = 0
def init(str):
    if ord(str[0]) >= ord('2') and ord(str[0]) <= ord('9'):
        return ord(str[0]) - ord('0')
    if str[0] == 'T':
        return 10
    if str[0] == 'J':
        return 11
    if str[0] == 'Q':
        return 12
    if str[0] == 'K':
        return 13
    if str[0] == 'A':
        return 14
    return -1
def level(card, color):
    straight = True
    for k in range(1, 5):
        if card[k] != card[k - 1] + 1:
            straight = False
    if color[0] == color[4]:
        if straight and card[0] == 10:
            return 10
        elif straight:
            return 9
    if card[0] == card[3] or card[1] == card[4]:
        return 8
    if (card[0] == card[2] and card[3] == card[4]) or (card[0] == card[1] and card[2] == card[4]):
        return 7
    if color[0] == color[4]:
        return 6
    if straight:
        return 5
    if card[0] == card[2] or card[1] == card[3] or card[2] == card[4]:
        return 4
    pairs_count = 0
    k = 0
    while k < 4:
        if card[k] == card[k + 1]:
            pairs_count += 1
            k += 1
        k += 1
    if pairs_count == 2:
        return 3
    if pairs_count == 1:
        return 2
    return 1
def beat(Alice, Bob):
    level_Alice = level(Alice[0], Alice[1])
    level_Bob = level(Bob[0], Bob[1])
    if level_Alice != level_Bob:
        return level_Alice > level_Bob
    if level_Alice == 6:
        k = 4
        while True:
            if Alice[0][k] != Bob[0][k]:
                return Alice[0][k] > Bob[0][k]
            k -= 1
    A = [[], [], [], [], []]
    B = [[], [], [], [], []]
    for k in range(2, 15):
        A[Alice[0].count(k)].append(k)
        B[Bob[0].count(k)].append(k)
    for k in range(1, 5):
        A[k].sort(reverse = True)
        B[k].sort(reverse = True)
    k = 4
    while True:
        for i in range(len(A[k])):
            if A[k][i] != B[k][i]:
                return A[k][i] > B[k][i]
        k -= 1
def work(arr):
    global ans
    arr = arr.split()
    Alice = [[init(arr[k]) for k in range(0, 5)], [arr[k][1] for k in range(0, 5)]]
    Bob = [[init(arr[k]) for k in range(5, 10)], [arr[k][1] for k in range(5, 10)]]
    for k in range(0, 2):
        Alice[k].sort()
        Bob[k].sort()
    # print(Alice)
    # print(Bob)
    if beat(Alice, Bob):
        ans += 1
for line in content:
    work(line)
print(ans)

Problem 59

简单有趣的一道题。可以通过字母频率分析猜一猜密钥，如果懒得做的话可以像我一样直接枚举。

得到所有可能的原文章后，我们要筛选出有意义的那一个，当然不能一个一个去看，可以在Sublime Text里搜索几个常见词汇，比如我搜索了the（两侧带空格），直接可以得到密钥是exp，问题就结束了。

Problem 59 代码

得到所有可能的原串

text = []   # 填入所给文件内容
key = [0, 0, 0]
def work():
    id = 0
    T = text.copy()
    for i in range(len(T)):
        T[i] = chr(T[i] ^ key[id])
        id += 1
        if id == 3:
            id = 0
    str = ''
    for c in T:
        str += c
    with open('output.txt', 'a') as f:
        for k in range(0, 3):
            f.write(chr(key[k]))
        f.write('\n')
        f.write(str)
        f.write('\n')
for a in range(ord('a'), ord('z') + 1):
    key[0] = a
    for b in range(ord('a'), ord('z') + 1):
        key[1] = b
        for c in range(ord('a'), ord('z') + 1):
            key[2] = c
            work()

已知密钥求答案

text = []   # 填入所给文件内容
key = [ord('e'), ord('x'), ord('p')]
id = 0
for i in range(len(text)):
    text[i] = text[i] ^ key[id]
    id += 1
    if id == 3:
        id = 0
ans = 0
for x in text:
    ans += x
print(ans)

Problem 60

本题是前60道题中难度最大的一道，但是也比较常规。

考虑转化到图论上。如果两个素数的拼接仍然是素数，就在它们之间连边，要求的就是数字和最小的 子图。这种东西就直接爆搜，远远跑不满五次方的上界，可以在 秒内跑出结果，如果用某些工程库的求 子图模板可以更快，但没必要。

本题中如果没有提前建好图，而是在爆搜过程中不断调用isprime会巨慢无比，什么东西都跑不出来，笔者最开始就是因为这个卡住了。

Problem 60 示例代码

Problem 60

import math
import time
import sympy
START = time.time()

N = int(1e6) + 10
d = [0] * N
primes = []
def Sieve(n):
    d[1] = 1
    for i in range(2, n + 1):
        if d[i] == 0:
            d[i] = i
            primes.append(i)
        for x in primes:
            if x * i > n:
                break
            d[x * i] = x
            if(i % x == 0):
                break
Sieve(int(1e4))
def check(a, b):
    return sympy.isprime(int(str(a) + str(b))) and sympy.isprime(int(str(b) + str(a)))
edges = [[] for _ in range(len(primes))]
for i in range(len(primes)):
    for j in range(i + 1, len(primes)):
        if check(primes[i], primes[j]):
            edges[i].append(j)
            edges[j].append(i)
print('Total nodes:', len(primes))

ans = int(1e18)
val = [0, 0, 0, 0, 0]
def dfs(dep):
    global ans, val
    if dep == 5:
        S = 0
        for k in range(5):
            S += primes[val[k]]
        print(val)
        ans = min(ans, S)
        print(ans)
        return
    for i in range(len(primes)):
        if primes[i] == 5:
            continue
        if dep != 0 and i <= val[dep - 1]:
            continue
        val[dep] = i
        flag = True
        for j in range(0, dep):
            if not edges[i].count(val[j]):
                flag = False
                break
        if flag:
            dfs(dep + 1)
dfs(0)
print('Result =', ans)

END = time.time()
print(f"耗时:{END - START:.4f}秒")

Problem 64

以连分数为背景的一道题，正好来学习一下相关内容。

定理：所有循环连分数都是二次无理数，且任何一个二次无理数都可以写成循环连分数的形式。

证明：先证明所有循环连分数都是二次无理数。对于一般的循环连分数 ，设 ，则

其中 和 都是分式线性变换，于是得到

右侧的复合仍然是一个分式线性变换，不妨设

则得到关于 的方程 ，因此循环连分数都是整系数二次方程的解，又因为无线连分数都是无理数，因此循环连分数表示了二次无理数。

接下来，我们证明任意二次无理数都可以写成循环连分数，这是对于本题重要的一步，因为我们可以通过这个过程得到计算连分数形式的算法。

首先，二次无理数总可以表示成 的形式，其中 都是整数且 。证明很容易，可以通分为

令 ，， 即可。

为什么要写成这样的形式？因为它的所有余项都有类似的形式：

其中 ， 是整数并且 。其中，条件 保证了所有余项的分子中， 前面的系数都是 。

数学归纳求 ， 的形式：设 ，那么 。

设 也有类似形式，带入得到

对比系数可得

实际应用时，可以用更简便的

根据 ，所以 和 确实都是整数，即 确实具有要求的形式。

到此，我们已经得到了求二次无理数的连分数形式的算法，下面证明余项只能取到有限多个值，因此必然存在循环节。

已经求得余项为

对于无理数，总有 ，同时，其共轭

因为 并且

因此对充分大的 ，必然有 ，因此

得到

，因此 只能取有限个值，进一步由递推公式， 也只能取有限个值，证毕。

代码就根据上面的递推写就行了，没什么难度。这里直接用了OI-wiki的实现。

Problem 64 代码

Problem 64

# Return the continued fraction and minimal positive period
#   of a quadratic irrational (x + y * sqrt(n)) / z.
import math
def quadratic_irrational(x, y, z, n):
    p = x * z
    d = n * y * y * z * z
    q = z * z
    dd = math.floor(math.sqrt(n)) * y * z
    i = 0
    a = []
    used = dict()
    while (p, q) not in used:
        a.append((p + dd) // q)
        used[p, q] = i
        p = a[-1] * q - p
        q = (d - p * p) // q
        i += 1
    return a, i - used[p, q]

ans = 0
for k in range(1, 10000 + 1):
    if int(math.sqrt(k)) ** 2 == k:
        continue
    if quadratic_irrational(0, 1, 1, k)[1] % 2 == 1:
        ans += 1
print(ans)