CF 题单&题解

长期更新

主要偏向于题单,题解可能写的不会非常详细

比较明显的一道贪心题，可以看出，往前面的点走是比往后面的点走更优的，所以只需要先往前走，如果还有时间在往后走

直接考虑每一个时刻能够到达的温度范围即可

因为题目中说了同一个点可以走多次，所以只需要考虑最短距离和 $k$ 奇偶性即可

且最短距离有且只可能有三种情况

1. $a\rightarrow b$

2. $a\rightarrow x\rightarrow y\rightarrow b$

3. $a\rightarrow y\rightarrow x \rightarrow b$

因为是异或,所以可以直接考虑每一位,判断每一位出现的 $1$ 的次数的奇偶性

若第 $i$ 位为 $1$ 那么 $b_i+b_j\in [2^k,2^{k+1}-1]$ ,考虑进位, $b_i+b_j\in [2^{k+1}+2^k,2^{k+2}-2]$

可以用双指针求这个东西

首先有一个性质 $gcd(a,b)=gcd(a,a+b)$ ,这个就不再证明了

考虑右边的每一个点,用 $S_i$ 表示 =与该点连接的左边的点的集合

若 $S_i=S_j$ ,直接合并这两个点

若 $S_i\cap S_j=\varnothing$ ,直接求 $gcd(c_i,c_j)$

若 $S_i \cap S_j \ne varnothing$ ,那么要求的就是 $gcd(c_i,c_j,c_i+c_j)=gcd(c_i,c_j)$

直接用hash维护集合计算即可

打表找规律

直接找是否存在相邻的数大于k

简单推一下就行

比较简单的贪心,或者说模拟?

扩展欧拉定理的应用

01trie的应用

直接模拟就行了

先把所有的值给a[1],最后再一个一个还回去

考虑分成 $[1,2^k],[n-2^k+1,n]$

最大生成树,将所有集合与元素看成点,若存在环,就一定是Rainbow Cycles

可以得出,答案一定是交点的数目+(长度为1e6)的线段数+1,用扫描线求即可