NOIP集训-10.31总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
其实还是比较水的..
--------------------------------------------------------------------
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
--------------------------------------------------------------------
评论 (0)
