2020-2021:teams:manespace:cf_round_644_div3
目录
地址：https://codeforces.com/contest/1360
A Minimal Square
- 题意：给你两个相同的边长分别为$a$ 与$b$的矩形，求能将俩矩形都包含的最小矩形面积
- 题解：即求$min\{max\{2b,a\},max\{2a,b\}\} ^2$
B Honest Coach
- 题意：将 $n$ 个数分为两组，要求一组的最大值减去另一组的最小值的绝对值最小。
- 题解：先将序列按照升序排序 在相邻两个数之间取差
C Similar Pairs
- 题意：给出 $n$ 个数 且$n$为偶数，要求两个数之间进行配对，要求是 $a$$i$, $a$$j$ 同奇偶或者 | $a$$i$ - $a$$j$ | =1。问这 $n$ 个数能否完成配对？
- 题解：由于$n$是偶数，那么当数列中奇数的个数为偶数时，偶数的个数也为偶数，显然这种情况下是一定可以的，那么当数列中奇数的个数为奇数时，我们只需要找到一组 | $a$$i$ - $a$$j$ | =1即可，由于 $a$$i$, $a$$j$一定是一个是奇数，一个是偶数的，那么减去这一组之后，奇数的个数和偶数的个数都变为了偶数，回到了第一中情况。
D Buying Shovels
- 题意：给你 $n$和 $k$，要求在 $[1,k]$ 中找到一个数 $x$，使得 $n$ $mod$ $x = 0$，并且 $\frac{n}{x} $ 最小。
- 题解：在 $[1,k]$ 中找$n$的最大公约数
E Polygon
- 题意：有一个$n \times n$矩阵，矩阵的最上边和最左边有一排大炮，可以无限制的打出一个$1$，$1$遇到$1$或矩阵的边界就停下，并且他停下的那一格变为了$1$，给出打完后的矩阵，问是否是合法的？
- 题解：看每一个$1$的右边和下边一格是否是$1$或边界，有一个不满足就是不合法的。
F Spy-string
- 题意：给出$n$个字符串，问是否存在一个基串去与这$n$个字符串比较，最多只有一个位置的字符不一样？
- 题解：以第一个字符串为基串，然后去改变他每个位置上的字符（每次只能改变一个位置），和其他的比较，看是否合法。
G A/B Matrix
- 题意：是否存在一个$n \times m$的矩阵，使得每一行有$a$个$1$,每一列有$b$个$1$
- 题解：首先判断是否有 $ a \times n \neq b \times m$ ，若有，则矩阵不可能构造出来。否则，令每行$a$个$1$，下一行在在上一行最后一个$a$的下一列开始构造，如此反复，即可构造成功。
H Binary Median
- 题意：有$2^m$个长度为$m$的$01$字符串，在去掉$n$个字符串后，对剩余的字符串进行排序，问下标为中位数的那个字符串是什么？
- 题解： 先把字符串转为十进制，删除每一个数的时候发现。
- 如果当前数的个数为偶数，如果要删去的数小于中位数，那么中位数向右移一位；
- 当前数的个数为奇数，如果要删去的数大于中位数，那么中位数向左移一位。
2020-2021/teams/manespace/cf_round_644_div3.txt · 最后更改: 2020/05/27 22:51 由 quantumbolt
