Educational Codeforces Round #106 ABCD 题解
A. Domino on Windowsill
题意
你有一个$2\times{n}$的格子。第一行前$k1$个格子是白色，第二行前$k2$个格子是白色。其余的格子是黑色。
现在你用$1\times{2}$的牌，其中$w$张是白色，$b$张是黑色。可以横着摆也可以竖着摆，但是只能摆在对应的颜色上。
问是能不能把这些牌摆完。
题解
竖着摆就可以了。多出来的部分才尝试横着摆。
代码
B. Binary Removals
题意
给你一个01构成的字符串$s$。现在要你移除一些字符使得这个串有序，也就是1一定在0后面。但是不能连续移除相邻的两个字符。问你能不能做到？
题解
枚举最后一个0的位置。然后尝试照着要求移除。
要注意的是，要枚举最后一个0的位置是在-1，也就是全是1的情况。以及最后一个0的位置是$|s|$的情况，也就是全是0的情况。
代码
C. Minimum Grid Path
题意
有一张$n\times{n}$的方格图。你要从$(0,0)$走到$(n,n)$。现在你只愿意最多转$n-1$弯，于是你最多能在走出$n$段路。对于每一段路你可以走任意长度-$length$。对于第$i$段路，其开销为$c_i\cdot{length_i}$。问最小开销。
题解
由于起步是往左还是往右走并没有区别，所以我们假设第一步是往右走。
于是立刻可以发现，偶数段的路都是往右，奇数段都是往上。于是我们想到贪心。对于往右和往上，我们都尽可能使$c_i$最小的段尽可能长。
硬要说的话，可以给出如下dp，但状压一下发现就一点也不dp：$$dp[i]=(\sum_{j=0}^{i}c_j)+(\min\limits_{0<j<=i,j\%2=0}{c_j})\times{times_0}+(\min\limits_{0<j<=i,j\%2=1}{c_j})\times{times_1}$$
其中，$times$表示对于当前方向在所有的$c$都走1步之后，剩下的距离。然后我们把这个剩下的距离分别给当前各方向的最小$c$。
代码
D. The Number of Pairs
题意
给你三个数$c$，$d$和$x$。问你有多少组满足下述条件的$a$，$b$：$$c \cdot lcm(a, b) - d \cdot gcd(a, b) = x$$
题解
首先，应当注意到$lcm(a,b)=gcd(a,b)\times{f}$。
于是立刻对原条件进行变形得到：$$c \cdot f \cdot gcd(a, b) - d \cdot gcd(a, b) = x$$
显然$gcd(a,b)\neq 0$，于是有:$$c \cdot f - d = \frac x {gcd(a,b)}$$
到此就非常清楚了。枚举这个$gcd(a,b)$，求出对应的$f$，然后根据$\frac f {gcd(a,b)}$的所有质因数的数目（记为$count$），算出所有的可能数。这个可能数为：$2^{count}$。
最后，需要注意的是：这个题目需要预处理出这个$count$。不然会TLE。