Educational Codeforces Round #106 ABCD 题解

A. Domino on Windowsill

题意

你有一个$2\times{n}$的格子。第一行前$k1$个格子是白色,第二行前$k2$个格子是白色。其余的格子是黑色。

现在你用$1\times{2}$的牌,其中$w$张是白色,$b$张是黑色。可以横着摆也可以竖着摆,但是只能摆在对应的颜色上。

问是能不能把这些牌摆完。

题解

竖着摆就可以了。多出来的部分才尝试横着摆。

代码

Submission #113408558 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Binary Removals

题意

给你一个01构成的字符串$s$。现在要你移除一些字符使得这个串有序,也就是1一定在0后面。但是不能连续移除相邻的两个字符。问你能不能做到?

题解

枚举最后一个0的位置。然后尝试照着要求移除。

要注意的是,要枚举最后一个0的位置是在-1,也就是全是1的情况。以及最后一个0的位置是$|s|$的情况,也就是全是0的情况。

代码

Submission #113411656 - Codeforces
Codeforces. Programming competitions and contests, programming community

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$。

代码

Submission #113420040 - Codeforces
Codeforces. Programming competitions and contests, programming community

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。

代码

Submission #113424991 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论