codeforces刷题记录——初三上

Codeforces Round #430 (Div. 2)

CF843C:这题我们考虑第一个节点,那么结果就是:要么什么都不删除(可以$O(n)$求解),可以只删除第一个(也是$O(n)$)求解$Large _{注意到,不要忘记把vis[1]赋值成true,不然会往父亲走!}$,要么是不修改第一个节点。注意到,既然不修改第一个节点,那么最后的$gcd$必然是1的因子!那么我们可以$O(sqrt(n))$来枚举所有可能的$Ans$,然后判断是否需要修改一个以上。

CF843D:这题只需要对所有的$x$求一个前缀$xor$,然后在一棵$trie$树上贪心。注意要记录这个以下的种类。

Codeforces Round #431 (Div. 2)

CF849B:注意到,只有2个前缀,如果存在,那么1和2不是同一组,1和3也不是同一组,那么2和3一定是同一组。同理,可以得到1和2,2和3,1和3其中必然有一组是其中一个等差数列的开头,那么O(3)枚举,然后O(n)判断即可。

CF849C:注意到,数字先后是无关的,只需要逐个添加就行了,所以就是找到满足一些$sum _nn*(n-1)div 2$的n,然后输出。然后位数是不用考虑的,其实长度(&码量)很短。

CF172D:给定a,n,求[a,a+n-1]所有数的贡献总和。一个数的贡献是其除掉所有平方因子后的部分。

​ 考虑用类似筛法的除去所有的因子,然后暴力求解。

CF451E:有$n$种颜色的❀,第$i$种❀有$f_i$朵。求选出$s$朵❀的不同方案数。$n<=20,s<=1e14,f_i<=1e12$

CF448E:给出一个x,k,每次操作都会将x分解因数,得到新的序列,然后每次再分解序列中的每一个数,按照每一个数分解因数从小到大排,整体顺序不做调整。(如果躲过1e5个,只输出1e5个)$x<=1e12, k<=1e18$

​ 考虑每次递归处理。每次到k次,然后$cnt++$,直到完了或者到了1e5个。

CF216E:给定一个进制k和一位数b。以及长度为n的序列(均小于k)求这个序列存在多少子序列,能通过变换变为d?这里的变换指的是,每次将k进制数x的每一位相加(k进制加法)得到一个新的数x’,直到最后得到一个一位数。$b<k<=1e9, n<=100000$