0805 模拟赛()

T1

不懂,不会。

T2

每面贡献独立,并且 \(a,b\) 的选法只有 \(O(n)\) 种,所以贡献类似于 \(f_i+f_j-4ij\),这不斜率优化了。但是我还是写李超树,因为我不会斜率优化 /cf

T3

说的还不够多吗?

zero2.out

一堆固定的正数,加上一堆明显大得多的负数,那猜想每个负数只会用一次。

事实确实如此,为保证这点,负数必须大于正数之和的一半。此时使用了这个负数对答案的贡献是,用正数组合出之的方案数。这样就是个背包了!

所以随便手动调整一下正数集合不就完事了?但是我非常愚蠢,没想到可以直接把 里面的正数集合复制过来用。

zero2.out
————————

T1

不懂,不会。

T2

每面贡献独立,并且 \(a,b\) 的选法只有 \(O(n)\) 种,所以贡献类似于 \(f_i+f_j-4ij\),这不斜率优化了。但是我还是写李超树,因为我不会斜率优化 /cf

T3

说的还不够多吗?

zero2.out

一堆固定的正数,加上一堆明显大得多的负数,那猜想每个负数只会用一次。

事实确实如此,为保证这点,负数必须大于正数之和的一半。此时使用了这个负数对答案的贡献是,用正数组合出之的方案数。这样就是个背包了!

所以随便手动调整一下正数集合不就完事了?但是我非常愚蠢,没想到可以直接把 里面的正数集合复制过来用。

zero2.out