【题解】Codeforces Round 861（CF1808）A - E1

标签：CF1808 这个 861 题解 个数 E1 对应 dp mod

我忘记了今天有阳间 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)

题目分析：

显然可以想到设 \(dp[i][j]\) 表示前 \(i\) 个数和模 \(k\) 为 \(j\) 的方案数，但是我们好像不大能限制可行方案这个条件。
其实我们的可行方案的条件可以转化为：

\[\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\) 的时候限制这个数必须被插入就好了，也就是可以直接用 \(x\) 去初始化 \(dp\) 数组。

标签：CF1808,这个,861,题解,个数,E1,对应,dp,mod
From： https://www.cnblogs.com/linyihdfj/p/17270178.html