2016 ACM/ICPC Asia Regional Dalian Online

2016年9月14日1,0370

1002 Different GCD Subarray Query

问长为n的序列,m个询问,问区间[L,R]所有子段的不同gcd值个数

考虑固定左端点,随着右端点的移动,gcd至多衰减log次(每次至少折半)

从n开始添加询问的左端点,用树状数组维护每个gcd右端点的最小值

1007 Friends and Enemies

n个人,每个人可以用m种颜色中的一部分染色自己的项链

两个人是朋友当且仅当他们拥有相同的颜色

敌人不拥有任何相同的颜色

问对于任意一种关系情况,m种颜色是否足够

用连边表现朋友关系,n/2个点中每个点a向其余的n/2个点连边

可以证明,至少需要n*n/4种颜色,而且这是最差的情况

1008 Function

问长为n的序列,m个询问,问的值

一个数a取模小于等于其的数b,其值才会变化

从l开始,每次用二分+ST表寻找最近的小于当前模数的下一个数

1009 Sparse Graph

容易证明,从S能到达的点,最远点的距离不会超过 \(T=\sqrt{2m}\) 次

循环T次,第i次标记距离为i的结点,即每次查看原图上未标记的点是否与所有已标记的点连边

复杂度\(m\sqrt{2m}\)