【题解】Codeforces Round 861(CF1808)A - E1

发布时间 2023-03-29 20:33:45作者: linyihdfj

我忘记了今天有阳间 CF,所以就开打的很晚,所以只是说一下做法,代码实现....还是算了吧。
但是我也看了,我的思路其他的人都有写,所以这个做法正确性没问题。

A.Lucky Numbers

题目分析:

加不超过 \(100\) 次,一定会有 \(0,9\) 同时出现的情况,所以直接暴力做没问题。

C.Unlucky Numbers

题目分析:

可以考虑暴力枚举这个数里最大的数位(\(y\))和最小的数位(\(x\)),然后只需要判断只使用 \([x,y]\) 内组成的数是否有存在在 \([l,r]\) 内的。
一种做法就是数位 \(dp\),分别限制一下上下界或者差分一下判断数量,但是这太麻烦了。
我们其实可以考虑直接用 \([x,y]\) 组成大于等于 \(l\) 的最小的数,如果这个数小于等于 \(r\) 则证明有解。
这个解法很显然是正确的。

D.Petya, Petya, Petr, and Palindromes

题目分析:

显然对于一个区间其的贡献就是对应位置上的数不相同的数量。
可以发现对于某一个位置来说,不同的长度为 \(k\) 的子区间只是让它对称过去对应的数的位置不一样罢了,所以就考虑对于每一个数单独计算贡献。
假设我们可以维护出这个数能对应的区间 \([l,r]\),那么我们的答案就是 这个区间上与这个数不同的数的个数(不是种类),而这个不好求,可以转化为总共 对应的数的个数 - 相同的数的个数。
对于相同的数的个数我们可以对于每一个数维护一个数组,然后直接在数组上二分 \([l,r]\) 对应数组中的哪一段,这一段内的数的数量就是我们要的相同的数。
而对于 \([l,r]\) 来说,肯定随着我们下标的递增而单调不降,所以双指针维护就好了。
注意因为一个数只会对应与它下标奇偶性相同的位置,所以并不能直接以我们得到的区间长度为最终的结果,应该加一些细节。

E1.Minibuses on Venus (easy version)

题目分析:

我们的可行方案的条件可以转化为:

\[\begin{aligned} &\exists x\in A,S - x = x \mod k \\ \to &\exists x \in A,S = 2\times x \mod k \end{aligned} \]

也就是说我们可以直接枚举 \(S\% k\) 的值,然后对于 \(S = 2 \times x \mod k\)\(x\) 显然只有一个值,只需要在 \(dp\) 的时候限制这个数必须被插入就好了。