2020-2021:teams:legal_string:jxm2001:other:结论_2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:other:结论_2 [2020/10/13 16:44] jxm2001 [3、球盒问题] |
2020-2021:teams:legal_string:jxm2001:other:结论_2 [2021/05/23 09:22] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 41: | 行 41: | ||
| 于是可以 $O(nm)$ 得到答案。 | 于是可以 $O(nm)$ 得到答案。 | ||
| + | |||
| + | ===== 4、字符串变化 ===== | ||
| + | |||
| + | 给定串 $s_1,s_2$，保证 $s_1,s_2$ 中每种字符数量相同。每次允许交换 $s_1$ 中相邻的两个字符，问至少需要经过多少次操作才能得到 $s_2$。 | ||
| + | |||
| + | 假设有两个相邻的相同字母，则不应该交换这两个字符。于是交换过程中 $s_1$ 中同种字符的相对顺序不应该改变。 | ||
| + | |||
| + | 于是对同一种字符，$s_1$ 中的每个字符的最终位置应该按顺序与该字符在 $s_2$ 中的位置一一对应。 | ||
| + | |||
| + | 于是可以求出 $s_1$ 中所有字符在 $s_2$ 中的最终位置，然后接下来的操作等效于冒泡排序，于是操作数等于逆序对数。 | ||
| + | |||
| + | ===== 5、二进制表示 ===== | ||
| + | |||
| + | 假定有 $a_i\gt 0$ 个 $2^i(0\le i\le n)$，则可以表示出 $\sum_{i=0}^n a_i2^i$ 内的所有数。 | ||
| + | |||
| + | ===== 6、石子游戏 ===== | ||
| + | |||
| + | 以下两个条件等价： | ||
| + | |||
| + | - 每次可以拿 $S=\{a_1,a_2\cdots a_k\}$ 个石头的游戏等价于每次可以拿 $[\min S,\max S]$ 个石头的游戏。 | ||
| + | - 对任意 $a_i,a_j\in S$，若 $a_i+\min S\lt a_j$，则存在 $a_k\in S$，使得 $a_i\lt a_k\lt a_j$。 | ||
| + | |||
| + | 详细见 [[https://wiki.buaaacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:contest:cf_feb21#multiple_games|证明]] | ||
| + | |||
| + | ===== 7、线性表示 ===== | ||
| + | |||
| + | 当 $a,b$ 互素时，$ax+by(x,y\ge 0)$ 不能表示的正数等价于所有形如 $ab-an-bm(n,m\ge 1)$ 的正数。 | ||
| + | |||
| + | 一方面，考虑 $ab-a-b=a(b-1)-b=b(a-1)-a$ 显然不能表示为 $ax+by(x,y\ge 0)$。 | ||
| + | |||
| + | 当 $k$ 不能表示为 $ax+by(x,y\ge 0)$ 时，显然 $k-a,k-b$ 均不能表示为 $ax+by(x,y\ge 0)$。 | ||
| + | |||
| + | 于是所有形如 $ab-an-bm(n,m\ge 1)$ 的正数均不能表示为 $ax+by(x,y\ge 0)$。 | ||
| + | |||
| + | 另一方面，考虑任意 $ax+by(x,y\ge 0)$ 不能表示的正数，这个数一定表示为 $ax'+by'$，调整 $x'$ 使得 $0\le x'\lt b$，于是有 $y'\lt 0$。 | ||
| + | |||
| + | 于是有 $ax'+by'=ab+a(x'-b)+by'$，令 $n=b-x',m=-y'$，于是有 $n,m\ge 1$。 | ||
| + | |||
| + | 故任意 $ax+by(x,y\ge 0)$ 不能表示的正数一定可以表示为 $ab-an-bm(n,m\ge 1)$。证毕。 | ||
2020-2021/teams/legal_string/jxm2001/other/结论_2.1602578662.txt.gz · 最后更改: 2020/10/13 16:44 由 jxm2001
