2022 年新疆预赛

思路

绝对值的符号表示 $|u|={\max }_{\epsilon =\pm 1}\epsilon u$；有限个符号选择可逐个用柯西界住。环路回到原符号需偶数次翻转。

想法从哪来：三个变量时把最大与最小排好序，绝对差和就是两倍跨度；长环却不能任意重排，因为相邻关系会变。改用每个绝对值等于两种符号线性式的最大值，把绝对值和写成某一组符号下的线性函数。循环整理后每个变量的系数是相邻符号之差，只有零或正负二；柯西上界因此只由符号切换次数决定。环上切换总数必须是偶数，奇数个位置不可能全部交替，正好比偶环少一次。取一组只留一个不切换位置的符号，再让变量向量沿系数向量单位化，可同时验证平方和约束与上界取等。

第一问可按大小排序化为最大值与最小值之差。第二问使用绝对值的符号表示，把问题转成奇数环上符号变化次数的最大值。