1696C. Fishingprince Plays With Array【思维题 + 中间状态 + 优化存储】

分析

给一个list，里面的数如果是m的倍数可以拆成m个x // m，同样的如果遇到m个一样的x，可以缩成mx
问a能不能经过若干这两个操作变成b
思维点：a和b如果能同时扩展成c，那么必定有a - > c -> b（因为缩和放是相对的）
因此我们把a和b扩展即可，但是如果无脑扩展会爆memory
于是我们记录相同的连续的个数即可，用一个二维的表示，然后看看[-1]的num和目前是否相同即可
是的话加到[-1]否则的话append([num, cnt])

ac code

import sys
input = sys.stdin.readline


def expand(lst, m):
    c = []
    for num in lst:
        cnt = 1
        while num % m == 0:
            num //= m
            cnt *= m
        if len(c) == 0:
            c.append([num, cnt])
        elif c[-1][0] == num:
            c[-1][1] += cnt
        else:
            c.append([num, cnt])
    return c

for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    k = int(input())
    b = list(map(int, input().split()))

    # op1 and op2 are reversible
    # if a and b can both expand to c(mid state)
    # then a -> c -> b

    a = expand(a, m)
    b = expand(b, m)
    #print(a)
    #print(b)

    if a == b:
        print('Yes')
    else:
        print('No')

总结

思维题 + a变成b 我们考虑能不能a和b都变成c 然后允许的操作是具有可逆性的 + 优化存储（记录连续出现的相同的个数）