結果

問題 No.910 素数部分列
ユーザー gew1fw
提出日時 2025-06-12 21:27:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,344 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 81,936 KB
実行使用メモリ 90,280 KB
最終ジャッジ日時 2025-06-12 21:28:32
合計ジャッジ時間 4,156 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 16 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    
    # 预处理所有的两位数素数，其中每个字符只能是1、3、5、7、9
    two_digit_primes = [
        11, 13, 17, 19,
        31, 37,
        53, 59,
        71, 73, 79,
        97
    ]
    
    # 将每个素数转换为字符串，并记录所有可能的素数字符串
    prime_strs = set()
    for p in two_digit_primes:
        prime_strs.add(str(p))
    
    used = [False] * n  # 记录字符是否已经被使用
    
    # 首先处理长度为1的素数
    count = 0
    for i in range(n):
        c = s[i]
        if c in {'3', '5', '7'}:
            used[i] = True
            count += 1
    
    # 然后处理长度为2的素数
    # 我们需要找到尽可能多的互不重叠的长度为2的素数子序列
    # 这里我们采用贪心策略：尽可能提前选择素数
    
    # 将未使用的字符的位置记录下来
    available = []
    for i in range(n):
        if not used[i]:
            available.append(i)
    
    # 现在，我们遍历available中的位置，寻找可以组成两位数的素数
    # 我们需要检查每一个可能的两位数组合是否在prime_strs中
    # 为了避免重复使用字符，我们记录已经使用的索引
    used_available = [False] * len(available)
    two_digit_count = 0
    
    # 我们将available中的位置作为可能的起点，寻找可以组成素数的子序列
    # 这里我们采用双指针的方法，尝试找到尽可能多的素数
    i = 0
    while i < len(available):
        if used_available[i]:
            i += 1
            continue
        # 查找j > i，使得s[available[i]] + s[available[j]] 在prime_strs中
        for j in range(i+1, len(available)):
            if used_available[j]:
                continue
            num = s[available[i]] + s[available[j]]
            if num in prime_strs:
                # 选中这个素数
                used_available[i] = True
                used_available[j] = True
                two_digit_count += 1
                i = j + 1
                break
        else:
            # 没有找到可以与i组成素数的j，i前进
            i += 1
    
    total = count + two_digit_count
    print(total)

if __name__ == "__main__":
    main()
0