感觉这场前三题都简单,复盘一下赛时的脑回路QAQ,c二分wa了四发赛后才过的血亏
A
题意:问是否能找到一个数x,有\(b_i = a_i⊕x\) ,使得\(b\)数组的总异或和为0。
思路:赛时模拟样例可以发现先把a数组的总异或和求出来假设为x,然后由异或性质可知相同为0,不同为1,可知这个x可能就是答案。然后再根据题意造个b数组验证一下即可。
B
题意:假定一次操作可以将字符串中的任意一个字母删掉,然后把这个字母放到字符串最前面。问能否通过一次操作,求出给定字符串操作后有最小字典序的结果。
思路:我们可以先把字符串中每个字母最后一次在字符串中出现的次数用map记录一下,然后再用一个a数组记录26个字母是否出现过。要求最小字典序的字符串,直接贪心的把字典序小的放到前面就可以。所以可以遍历a数组,相当于从字典序最小的a开始找每个字母最后一次出现的位置,如果找到了,直接取这个字母最后一次出现的下标,记录一下这个字母,然后用erase删除之后输出即可。
C
题意:给n条过原点的直线和m个抛物线,问能否为每一条抛物线匹配一条不和他相交的直线,可以为不同抛物线匹配同一条直线。
思路:根据直线方程\(y=kx\)和抛物线公式\(y=ax^2+bx+c\)联立可得公式\(ax^2+(b-k)x+c = 0\)。由高中知识可得当判别式\((b-k)^2-4ac<0\)时直线和抛物线没有交点。二分查找存直线的斜率数组,找到一个满足该条件的值即可