NOIP集训-10.31总结

其实还是比较水的..
--------------------------------------------------------------------
 
Prime:SuperOjP981
互质的点连边,发现只需要求几个完全子图,使得总个数最小且所有点都属于某一个子图
显然是NPC问题,考虑搜索
每一次枚举把哪个点加入当前集合,或者选一个点来开始一个新的集合
对于第二问,枚举最大的大小,搜索的时候限制一下集合的大小就好
搜索的时候不去重的话只有60分,不要问我怎么知道的...
--------------------------------------------------------------------
Isfind:SuperOjP982
数据特水,我的暴力跑得比标算还快
 
一个O(询问字符个数 * lb(n))的算法:
对于每一次询问,显然对于每一个字符,要找到其在原序列中出现的某个位置,使得它比前一个字符出现的位置靠后
显然对于每一个字符,越靠前越好,因此我们可以预处理出每种字符在原序列中出现的位置,
每一次询问它的某一个出现位置,使得这个位置在前一个字符的出现位置之后,并且最小,可以二分查找
 
一个O(n*26)的算法:
预处理出对于每一个位置,每个字符下一次出现的位置
对于某一个询问的某一个字符,只需要求出它在上一个字符的出现位置出的下一次出现位置,
用之前预处理出的信息推即可
--------------------------------------------------------------------
Divide:SuperOjP983
每个数a[i]有贡献的部分就是gcd(a[i],p)
因此令a[i] = gcd(a[i],p)
这样,原序列中的数就只有p的约数个数种
考虑枚举j(O(n)),并枚举a[i]的值(O(p的约数个数))(可以预处理出来j之前值为这么多的数的个数),
只需要求出j后面有多少个数和a[j]*a[i]乘起来是p的倍数
令p' = p/gcd(a[i],p)
令p'' = p'/gcd(a[j],p')
也就是说这个数是p''的倍数,p''是p的约数,可以预处理出j这个位置的这个值
时间复杂度O(n*p的约数个数),打表发现p的约数个数不会超过300
--------------------------------------------------------------------