如何在野外生存和划水

#542 (Div. 2)

A. Be Positive

统计正数和负数个数。

B. Two Cakes

题意： 给定 \(2n\) 个数的序列， \([1,n]\) 每个数都出现了 \(2\) 次，从最左边开始两个人都要求依次从小到大取走数字，求最小移动距离。

贪心。 \(x_i, y_i\) 表示数字 \(i\) 的两个位置，如果选 \((x_i,x_{i+1})\) 的话，另一个人就要选 \((y_i,y_{i+1})\) 。两种情况选最小的。

C. Connect

搜索 \(S, T\) 能到的地方，枚举两个位置， \(O(n^4)\) 。

D1/D2. Toy Train

考虑每个点至少经过的次数 \(C_i\) ，记录最后一次经过后至少还需要走的路程 \(A_i\) 。

\(x\) 点为起点的答案就是 \(max\{dis(x,i)+(n-1)C_i+A_i\}\) 。

E. Wrong Answer

hdhd 大佬瞬间说出，如果 \(k \le 1e6\) ，直接构造 \(a_i=-k\) 即可，贪心程序此时会输出 \(0\) ，虽然这根本不是可行方案。

如果 \([l,r]\) 的区间和非负，右边还有一个非负数，那肯定 \([l,r+1]\) 不会更差，因为长度增加，区间和不减。

构造 \(a_1=-1,a_2 \ge 1,a_3,a_4 \cdots ,a_n \ge 0\) ，期望正解是选 \([1,n]\) ，贪心程序答案是选 \([2,n]\) 。

设 \(a_2+a_3+ \cdots a_n=t\) ， \((t-1)n - t(n-1) = k \Rightarrow t = k+n\) ，除了 \(a_1\) 外每个数的大小是 \(\dfrac{t}{n-1}\) ，大约 \(5 \times 10^5 \le 10^6\) ，没问题。