CodeForces-1913A Rating Increase
依题意模拟。
CodeForces-1913B Swap and Delete
交换免费就是能任意重排,从头开始尽量填相反的,剩下只能删去了。
CodeForces-1913C Game with Multiset
从大到小能减则减一定更优。
CodeForces-1913D Array Collapse
认为两次操作覆盖到同一元素是操作有交,发现这等价于取并区间操作一次,没有被操作的可以视作对自己操作,那么就是划分若干区间,每个区间只保留最小值,求本质不同方案数。
设 \(f_i\) 表示以 \(i\) 为最后一个区间的最小值的方案数,枚举上一个区间的最小值 \(j\),充要条件是 \(\min(p_i,p_j)=\min_{k=j}^i \{p_k\}\)。
若 \(p_i<p_j\),即 \(pos_i\) 为序列中第一个小于 \(i\) 的位置,则 \(j\in [pos_i+1,i-1]\),可以前缀和转移。
若 \(p_i>p_j\),那么 \(p_j\) 是 \([j,i]\) 的最小值,发现这就是当前单调栈内所有元素,维护一个和即可。
CodeForces-1913E Matrix Problem
首先 \(\sum A_i=\sum B_j\),考虑左部点为行,右部点为列的二分图,假设先把所有 \(1\) 翻成 \(0\),这样这些位置翻成 \(0\) 的费用是 \(-1\),其他位置是 \(1\),跑一个最小费用最大流即可。
如果担心出负圈可以权值都加 \(1\),最后答案再减去最大流。注意无解也要靠最大流是否等于 \(\sum A_i\) 判断。