题目大意
给定两个序列A,BA,BA,B,进行两种操作
1. 选定连续子序列[l,r][l,r][l,r],满足条件a_l = a_{l+1} \dost = a_r,长度为mmm,使其合并为 m×a[l]m \times a[l]m×a[l]
2. 选定数字aia_iai ,满足条件ai%m=0a_i \% m = 0ai %m=0 ,拆分为mmm个ai/ma_i / mai /m。
求解是否可以使序列A,BA,BA,B相同。
思路解析
进行反向思考,从答案出发,若A,BA,BA,B序列能够变为相同,那么相同的两个序列若一直执行拆分的操作,最后得到的序列A1,B1A_1,B_1A1 ,B1 也必然会相同,反之不能。
因此可以得出对应的模拟思路,不停的执行拆分操作,直到不可以在拆分的时候,根据两个序列的拆解序列A1,B1A_1,B_1A1 ,B1 是否相同输出YES 或 NO即可。
共有两种模拟方式
1. 采用字符串,从前往后依次拆分,累加到字符串当中进行判断
2. 采用pair, 将拆分的序列分段,最后判断两个pair数组是否相等
标程采用pair的方式进行判断。
时间复杂度
O(n)O(n)O(n)
代码演示