这是我的第一篇题解。以后每攒 5 道题会发一篇。除了需要特别注意的部分,尽量避免直接放代码。
坚持下去。
CF 1444 A Division
给定一对数 $p$ 和 $q$,求尽可能大的 $x$,使 $x$ 可整除 $p$,而 $q$ 不能整除 $x$。
$1 \leq p \leq 10^{18}, 2 \leq q \leq 10^{9}$
首先,如果 $q$ 不能整除 $p$,那么答案就是 $p$ 自己。其次,$x$ 一定是 $p$ 去掉若干质因数得到的。
去掉了几种质因数呢?明确一个概念:整除关系代表除数拥有被除数所有种类的质因数,且次数都不大于被除数。那么不可整除就代表除数至少一个质因数是被除数没有的,或者次数大于除数。这里既然只能扣除,那么扣除多种得到不可除的情况,一定能转化成只扣除一种,而转化后得到的答案 $x$ 显然较大。所以我们可以对每一种质因数分别去掉若干个,得到的结果再取最大。
大框架是对 $q$ 的分解质因数,1e9 的数据分解下来还是很小的。对每个质因数,从 $p$ 里扣掉它直到结果满足题设(可能一个都不扣,当 $p$ 没有这个数时,即开头提到的情况),再和上一个结果取最大。这些可以压到分解质因数的循环里去做。
CF 1451 C String Equality
给定两个长度为 $n$ 的小写字符串 $a$ 和 $b$,以及一个整数 $k \leq n$。对 $a$ 有以下两种操作:
- 交换相邻的两个字符
- 选定长为 $k$ 的一个区间,当区间内各字符相等时,将它们都变成字典序下一个字母。对 z 不能如此操作。
对给定的输入,输出是否能通过以上两种操作使两个字符串相等。
$2 \leq n \leq 10^6, 1 \leq k \leq n$
第一个操作代表我们可以把 $a$ 的字符任意组合。原来散开的相等字符都可以排在一起,然后进行变化。从 a 到 z 的变化是不可逆的,那么从 a 开始,对每个 $a$ 和 $b$ 都有的字符,留下和 $b$ 中同样多的,剩下的全部转化到字典序下一个字符。如果这样的操作一直到 z 都可行,则是可以让两个字符串相等的,否则不可以。
转化的条件是先保留和 $b$ 同样多的字符,且每次只能以 $k$ 个为一组,统一转化。
CF 859 C Pie Rules
甲和乙玩取数(拿派)游戏,规则如下:
有一个决定权,初始在乙手上。数列是固定顺序的,对于每个数,拥有决定权的人可以把这个数给一个玩家,同时把决定权给另一个玩家。双方都想让自己拿到的数总值最大。
假设双方都按最优方案,求最终分别拿到的数值总和。
一直要把决定权留给自己的话好吃的派就都是别人的了
一道 dp 题。
既然每个人都会按最优方案选(只要决定权在自己手上),那么只从状态来考虑,在每个位置能行使决定权的人是状态转移的推力。于是考虑用 dp[i]
记录在第 $i$ 个位置拿到决定权的人能获得的最大总值。再看方向,由于在每个位置拿到决定权后,后续取数存在一个确定的最优,那么从后往前 d 是较好的想法。于是 dp[i]
记录在第 $i$ 个位置拿到决定权的人,之后能获得的最大总值。
那么初始状态是 dp[n] = n
,目标状态是 dp[1]
(根据题设,这是乙的)。接下来考虑状态转移方程。
对每个拿到决定权的人,他之后能拿到的最大值与是否交出决定权相关。若不交出,他能拿到的值和下一个位置相等;交出,则能拿到的值是 当前位置 + 下一个位置开始的后缀和 - 下一个位置
,即 当前位置开始的后缀和 - 下一个位置
。两者取最大即可。
实际上 dp[i]
记录的是在第 $i$ 位置拿到决定权的人之后能获得的最大。
CCPC 2020 秦皇岛站 G Good Number
给定 $n$ 和 $k$,有 $i \in [1, n]$ 且 $\lfloor \sqrt[k]{i}\rfloor | i$,求 $i$ 的个数。
$1\leq n, k \leq 10^9$
由于是向下取整,考虑按 $[i^k, (i + 1)^k)$ 将 $[1, n]$ 分段,段内开次方向下取整都会得到 $i$,那么段内所有可以被 $i$ 整除的数就是 Good Number。最后一段显然有可能不全。敲一下快速幂就好了。注意考虑超过 long long
的情况。
POJ 3279 FlipTile
$M \times N$ 的黑白棋棋盘,每次翻一个棋子时,与它四连通的棋子也会翻转。给定棋盘尺寸和棋子状态,以棋盘的形式输出全部翻转为白色的方案,每个位置的数代表该位置的翻转次数,要求翻转次数最小且字典序最小。不能完成时输出 “IMPOSSIBLE”。
$1 \leq M, N \leq 15$
搜索题。显然一个位置翻转奇数次等价于翻转一次,偶数次等价于不翻转。按行来考虑,每行的一个位置要被翻转当且仅当它上一行对应位置是黑色,然后枚举第一行的翻转状态即可。注意搜到了一个方案不能停,要比较总翻转次数和字典序,保留当前最符合题设的答案。
当时被这道题卡了挺久,主要在记录当前最优和第一个枚举状态这些小地方,一度想要放弃 kuangbin 的题集(一遇到 POJ 的题就难受,各种 WA)。所幸撑住了。继续。