Educational Codeforces Round 106 个人题解

2021-03-19 13:55 作者:俊杰_Charles 0人读过 | 我要投稿

比赛链接：https://codeforces.com/contest/1499/

官方题解：https://codeforces.com/blog/entry/88812

难度：Edu

A. Domino on Windowsill

题意：给一个 $2%5Ctimes%20n$ 的格子图，第一排前 $k_1$ 个格子是白色，后面是黑色；第二排前 $k_2$ 个格子是白色，后面是黑色。有 $w$ 个白色 $2%5Ctimes1$ 骨牌， $b$ 个黑色 $2%5Ctimes1$ 骨牌，白色骨牌只能放在白色格子上，黑色骨牌只能放在黑色格子上，且骨牌间不能重叠，问能否将所有骨牌放到格子上。

题解：求白色区域和黑色区域分别最多能放多少骨牌，与输入比较即可。

B. Binary Removals

题意：给一个 $01$ 串，问能否去掉一些位置，任意两个位置不相邻，使得最终串是单调不降的。

题解：找一个分界线，分界线左边的 $1$ 全部去掉，右边的 $0$ 全部去掉。如果答案存在，那么就存在一条分界线，其左边不存在相邻的 $1$ 且右边不存在相邻的 $0$ 。

C. Minimum Grid Path

题意：从 $(0%2C0)$ 走到 $(n%2Cn)$ ，只能向右或向上走，且走出的折线每段长度都为整数。若最终路线由 $k$ 条线段组成，第 $i$ 条长度为 $l_i$ ，那么总花费为 $%5Csum_%7Bi%3D1%7D%5Ekc_il_i$ ，其中 $c_i$ 为第 $i$ 条线段的单位长度花费，由输入给定。在 $k%5Cle%20n$ 的条件下，求最小花费是多少。

题解：由对称性，不妨设最开始向右走，此时如果向右的线段有 $x$ 条，那么向上的线段就有 $x$ 或 $x-1$ 条。此时我们可以尝试解决子问题，即当向右的线段有 $x$ 条时的最小花费是多少，向上的线段同理。由于这 $x$ 条线段的单位长度花费是确定的，我们只需要让单位长度花费最小的线段尽量长，其他线段长度为 $1$ 即可。遍历 $x$ 的过程需要维护最小值与花费和，时间复杂度 $O(n)$ 。

D. The Number of Pairs

题意：给定 $c%2Cd%2Cx$ ，求有多少对正整数 $(a%2Cb)$ ，使得 $c%5Ccdot%5Ctext%7Blcm%7D(a%2Cb)%E2%88%92d%5Ccdot%5Cgcd(a%2Cb)%3Dx$ 。

题解：令 $%5Cgcd(a%2Cb)%3Dg$ ， $a%3Dpg$ ， $b%3Dqg$ ，可知 $p$ 和 $q$ 互质， $%5Ctext%7Blcm%7D(a%2Cb)%3Dpqg$ 。原式化为 $cpqg-dg%3Dx$ ，即 $pq%3D%5Cfrac%7B%5Cfrac%7Bx%7D%7Bg%7D%2Bd%7D%7Bc%7D$ 。由此可知， $g$ 一定为 $x$ 的因数。枚举 $g$ ，可以确定 $pq$ 的值，然后算出有多少对 $p$ 和 $q$ 满足条件即可。令 $pq%3Dy$ ，此时则需要解决 $y$ 能够分解为多少对互质数的乘积，可以推出答案与 $y$ 的不同质因子个数有关，一个数不同质因子个数可以通过欧拉筛进行预处理，最终时间复杂度 $O(x%2BT%5Csqrt%7Bx%7D)$ 。