¶A
¶题意
给定n个数$a_i$,求$gcd{(lcm(a_i,a_j))}$
¶做法
考虑gcd和lcm的本质,gcd就是所有数个质因子幂次取min,而lcm是取max所以答案就是各质因子幂次的次大值(不会维护)考虑a[i]对答案的贡献,就是$lcm(a_i, sufgcd_{i+1})$sufgcd为后缀gcd最后各个数贡献取gcd即可
¶B
¶题意
给定n个数$a_i$,每次操作可以选定一个连续子段,并把所有数变为中位数(第$\lfloor \frac{n+1}{2}\rfloor$大的数),问能否通过若干次操作使整个数列所有数都是k
¶做法
1.如果没有k,无解2.n=1,看是不是k3.如果有一段连续的k(>=2),则一定有解,因为每次都可以至少向左右延拓一步.考虑到两个>=k的数可以把一个<k的数变成>=k.而一个=k数可以把一个>k的数变成k只要存在两个>=k的数的位置差<2则一定有解(首先变成3个>=k的数,然后不断延拓即可)
¶C
¶题意
一个黑白格,在每一秒,若一个格子与上下左右的格子颜色不同,它的颜色不改变,否则改变.问某个格子t秒后的颜色
¶做法
如果该格子与四周某格子颜色相同,那么它就一直会改变,否则它会保持不变x秒后,再一直改变,x为距离该格子最近的一直改变的格子的曼哈顿距离,多源bfs预处理即可.