Make It Zero
挺简单的一道题,偶数长度的数组操作两次就可以,如果是奇数长度,则额外操作两次。写的时候,把 \(n\) 错写成 \(n-1\),找 BUG 花了一倍的时间。
1 | public static void solve() { |
2D Traveling
\(a\) 和 \(b\) 的最短距离有两种情况,一个是 \(a\) 和 \(b\) 的曼哈顿距离,另一个是 \(a\) 和 \(b\) 经过 \(k\) 的曼哈顿距离,该情况只要求 \(k\) 个点中距离 \(a\) 和距离 \(b\) 最近的距离就行。比赛时遇到个坑点,两个 Long.MAX_VALUE
相加会溢出,所以初始时除以二。
1 | public static void solve() { |
Fill in the Matrix
比赛时代码很乱,赛后总是可以优化成比较简单的形式。分类讨论,\(n\) 和 \(m\) 的大小关系,可以直接得出最大美丽值,需要注意特判 \(m=1\) 的情况。然后就是构造,当 \(n\leq m-1\) 时,让一个从 \(0\) 开始的数组循环左移来构造行,这样可以保证得到最大美丽值;当 \(n>m-1\) 时,前 \(m-1\) 行与之前一样构造,之后多余的行只需要和最后一行相同即可(保证不会影响美丽值)。
1 | public static void solve() { |
Candy Party (Easy Version)
找 BUG 花了半个小时,将判断 hi
是否是二的幂写成 hi % 2 != 0
,修改为 Long.bitCount(hi) != 1
后通过,也可以写成 (hi & hi - 1) != 0
。因为每个人都需要发送和接收糖果,计算每个人和平均糖果数的差值 \(x\),如果 \(x\) 的二进制位不是由连续的 \(1\) 组成,那么就无解,否则总是有唯一的 \(lo\) 和 \(hi\)(都是二的幂),使得 \(hi-lo=|x|\)。这样可以计算出每个人发送和接收多少糖果,如果最后相互抵消,则存在满足题目要求的交换方案。
1 | public static void solve() { |
Candy Party (Hard Version)
考虑什么人可以不发送或者不接收糖果,必定是持有糖果数与平均糖果数的差值为二的幂的人,它们比原来多出一种选择,就是只执行一次发送或接收。具体操作见代码,有点说不清。最后大概是从高位到低位遍历,如果当前位不满足条件,就将低一位的差值与平均糖果数为二的幂的数分解。
1 | public static void solve() { |