T1 Promotion Counting

algorithm: segtree, BIT

水题,树状数组差分即可。

T2 rabbit

algorithm: network-flow, greedy

乱搞。 将数据用桶装起来,枚举胡萝卜或干草,与另一个分别相减。

网络流?不会(好像是最小割)。

T3 【2024年SD省队集训 day2】反转了 (flip)

algorithm: PST, divide-and-conquer

先考虑朴素算法,若当前前缀和右端点为 \(i\),则反转的肯定为 \([1,i]\) 间最小的 \(k\) 个数,用主席树计算,时间复杂度 \(O(n^2log \ n)\)

发现有决策单调性,第 \(k+1\) 次反转的最优右端点 一定大于 等于第 \(k\) 次反转的右端点。

证明:https://lnw143.github.io/blog/gmoj/p8081/#%E5%8D%95%E8%B0%83%E6%80%A7%E8%AF%81%E6%98%8E

考虑分治,设函数 solve(l,r,L,R)

每次把求 \(k = \frac{l+r}{2}\) 的答案,暴力跑 \([L,R]\) 区间,求出答案。

T4 【GDOI2020模拟】 亚特兰大 (atoranta)

暂缺