CodeForces 1304C Air Conditioner
显然对于能够取到的温度区间 \([l,r]\),在 \(t\) 秒后能够取到的温度区间为 \([l-t,r+t]\)。
从头开始,每次遇到顾客就取一次交集,只要最后不为空集即为 YES
,否则为 NO
。
CodeForces 1325D Ehab the Xorcist
考虑到加和比异或和多出的部分即为进位。对每一个 bit 记录一个数表示 \(1\) 的个数,先将异或和的每一位填进去,再算出加和与异或和的差 \(d\)。对于 \(d\) 的每一个 \(1\),原位置低一位的位置填入两个 \(1\),最后任意组合出数组即可。注意当异或和大于加和或者 \(d\) 的最低位为 \(1\) 时一定不合法。
CodeForces 1338B Edge Weight Assignment
先考虑最小值:将某个叶子拉起作为根,如果剩下的叶子到根的距离均为偶数时,那么可以将同一个数都填在路上,答案为 \(1\);否则需要拿出两个 bit,并且这两个 bit 为 \(1\) 的道路集合有交集,答案为 \(3\)。
再考虑最大值:我们可以将每个非叶子节点的周围所有道路权值的某个 bit 赋值为 \(1\),这样可以保证进出这个节点后这个 bit 仍为 \(0\)。对于所有叶子的父节点来说,会有 \(\deg-1\) 条路的权值相同,即会给总种数减去 \(\deg-2\)。计算所有叶子父亲的 \(\deg-2\) 之和 \(s\),答案即为 \(n-s-1\)。
CodeForces 1385D a-Good String
对于所有长度为 \(2^k\le n,k\in\mathbf{N}\) 的字符串记录变为某个字符的操作数最小值 \(f_{c,k,i}\) 和成为某个字符-优的操作数最小值 \(g_{c,k,i}\),显然有:
\[f_{c,k,i}=\min(f_{c+1,k-1,i}+g_{c,k-1,i+2^{k-1}},g_{c,k-1,i}+f_{c,k-1,i+2^{k-1}})
\]
\[g_{c,k,i}=g_{c,k-1,i}+g_{c,k-1,i+2^{k-1}}
\]
从 \(k=0\) 开始递推即可。