其他-Paddling On CF

如何在野外生存和划水

#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\) ,没问题。

上一篇:[2019.3.17]BZOJ1109 [POI2007]堆积木Klo


下一篇:混合整数线性规划——切割平面