A.We Need the Zero
算法本质
思维
题目大意
给长度n的数组a[]，必须进行一次以下操作，使得操作后的a[]的元素异或和为0：
- 选择值
x，使得a[i] ^= x
输出x（不行输出-1）
思路推演
异或运算有交换律，所以操作后的a[]元素异或和为：a[1] ^ a[2] ^ ... ^ a[n] ^ x ^ x ^ ... ^ x（n个x）
如果n为偶数，则可以消去所有x，反之会留下一个x。
根据前面的异或和值调整x的值即可。（n偶数且前面异或和不为0，输出-1）
B.The String Has a Target
算法本质
思维
题目大意
给长度n的字符串s，必须进行一次以下操作，最小化s字典序：
- 调整某个字符至最前面
输出操作后的s
思路推演
显然，我们需要选择一个最小的字符放到最前面。
相同的字符，我们用靠后的字符收益更大。
B.Place for a Selfie
算法本质
思维、数学、模拟
题目大意
有n条过原点的直线设为y1 = kx
有m条开口向上的抛物线设为y2 = ax^2 + bx + c (a>0)
对于每条抛物线，找到一条不与其相交的直线，输出其斜率（无则-1）
思路推演
因为抛物线开口向上，模拟了一会即可发现：
- 抛物线、直线斜率都为
k的y值为两者最接近的点，若y2 > y1则两者一定不可交
随后带入式子，可以推出以下结论：(k-b)^2 < 4ac则两者一定不可交。
所以我们要找到距离b最小的k，用二分找b附近的2个k，挨个试验即可。
D.A Wide, Wide Graph
算法本质
思维
题目大意
给定n个节点的树，设每两点间的距离为树上距离。
现将n个点都隔离出来（初始无边），规定距离>=k的两点建立新边，f(k)为当前情况下连通块数目。
k=1~n，输出所有的f(k)。
思路推演
对于点i，当
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)