地址: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$个字符串后,对剩余的字符串进行排序,问下标为中位数的那个字符串是什么? *题解: 先把字符串转为十进制,删除每一个数的时候发现。 -如果当前数的个数为偶数,如果要删去的数小于中位数,那么中位数向右移一位; -当前数的个数为奇数,如果要删去的数大于中位数,那么中位数向左移一位。