CF725 题解

[toc]

AC代码

A. Stone Game

分类讨论一下。

B. Friends and Candies

超过平均数的需要被选中。

C. Number of Pairs

简单的容斥，记 $f(k)$ 表示 $a_i+a_j\geq l$ 的对数，那么答案就是 $f(l)-f(r+1)$ ，对于每个询问二分查询即可。

D. Another Problem About Dividing Numbers

给定三个正整数 $a,b,k$ ，你需要恰好执行以下操作 $k$ 次使得 $a,b$ 变成相等的，一次操作指在以下两项中选择一项：

• 选择一个正整数 $c>1$ ，并且 $0\equiv a \pmod{c}$ ，将 $a$ 替换为 $\frac{a}{c}$ 。
• 选择一个正整数 $c>1$ ，并且 $0\equiv b \pmod{c}$ ，将 $b$ 替换为 $\frac{b}{c}$ 。

或者判断这无法做到。

$10^4$ 次询问，$a,b,k\leq 10^9$ 。

$k=1$ 时，显然要么 $0\equiv a\pmod{b}$ ，要么 $0\equiv b\pmod{a}$ ，注意 $a\neq b$ 。

$k>1$ 时，显然 $a,b$ 都可以在一步操作内变为 $1$ ，因此我们需要关注的是最多几次操作才能让 $a,b$ 都变为 $1$ ，如果这个最多的操作次数 $\geq k$ 则有解，否则无解。

这个子问题实质上就是一个数的质因子幂次和，分解质因数即可，注意暴力分解的时间复杂度可能较高，应该先筛出 $O(\sqrt{n})$ 以内的质数在分解质因数，时间复杂度 $O(T\frac{\sqrt{n}}{\log n})$ 。

E. Funny Substrings

有两种操作：给字符串赋值和将两个字符串连接起来。询问最后得到的字符串中有几个 haha 子串。

$操作次数\leq 50$ 。

由于我们只需要关注 haha 子串，因此实际上每次连接字符串之后，我们只需要保留新字符串的前三位和后三位，用map模拟即可。

F. Interesting Function

询问 $l$ 到 $r$ 的过程中，数位变化了几次，比如 $99$ 到 $100$ 就有三个数位变化，$109$ 到 $110$ 就有两个数位变化。

$10^4$ 次询问，$l,r\leq 10^9$ 。

数位进行了 $k$ 次变化，就说明是从 $d(10^{k-1}-1)$ 变化到了 $d\cdot10^{k-1}$ ，对于每个 $k$ 进行统计即可。

G. Gift Set

你有 $x$ 个红色糖果，$y$ 个蓝色糖果，现在你想要将糖果组成套装，一个套装要么由 $a$ 个红色糖果和 $b$ 个蓝色糖果组成，要么由 $b$ 个红色糖果和 $a$ 个蓝色糖果组成。询问最多能组成几个套装。

$10^4$ 次询问，$x,y,a,b\leq 10^9$ 。

假设第一种套装有 $X$ 套，第二种有 $Y$ 套，那么很明显我们需要在最大化 $X+Y$ 的基础上满足：

从高中数学的角度来看，这就是一个线性规划，画出图像后，本题很明显可以通过二分解决。

设 $X+Y=k$ ，上式就转化为了：

不妨假设 $a>b$ ，由此，我们可以推出 $X$ 的可行域为 $[\frac{ak-y}{a-b},\frac{x-bk}{a-b}]$ ，最后检查一下可行域内是否存在一组非负整数解 $(X,Y)$ 即可二分 $k$ 的值解决本题。